Multinomial theorem with imposed conditions

Question

The number of ways in which 12 identical balls can be grouped in four marked non-empty sets $P, Q, R, S$ such that $n(P) < n(Q)$ is?

The answer to the above problem is the number of positive integral solutions of the expression $$P + Q + R + S = 12$$ when $P<Q$. I know that with no conditions imposed, the number of solutions is $^{12-1}C_{4-1} = ^{11}C_3$. How would one account for the condition when $P<Q$? Please explain the concept in detail in addition to providing a solution to the problem (which is given just as an example).

Answer 1

Let $a,b,c,d\ge0$. Then set $|P|=a+1$, $|Q|=a+b+2$, $|R|=c+1$, $|S|=d+1$ where $2a+b+c+d+5=12$. We want to count the non-negative solutions to $$ 2a+b+c+d=7\tag1 $$ Considering the coefficients of $x^n$ in $$ \overbrace{\left(1+x^2+x^4+x^6+\dots\right)\vphantom{{x^2}^3}}^a\overbrace{\left(1+x+x^2+x^3+\dots\right)^3}^{b,c,d}\tag2 $$ $(1)$ gives a generating function of $$ \begin{align} &\frac1{1-x^2}\left(\frac1{1-x}\right)^3\\ &=\frac1{1+x}\left(\frac1{1-x}\right)^4\\ &=\frac12\left(\frac1{1-x}+\frac1{1+x}\right)\left(\frac1{1-x}\right)^3\\ &=\frac12\left(\frac1{1-x}\right)^4+\frac14\left(\frac1{1-x}+\frac1{1+x}\right)\left(\frac1{1-x}\right)^2\\ &=\frac12\left(\frac1{1-x}\right)^4+\frac14\left(\frac1{1-x}\right)^3+\frac18\left(\frac1{1-x}+\frac1{1+x}\right)\frac1{1-x}\\ &=\frac12\left(\frac1{1-x}\right)^4+\frac14\left(\frac1{1-x}\right)^3+\frac18\left(\frac1{1-x}\right)^2+\frac1{16}\left(\frac1{1-x}+\frac1{1+x}\right)\tag3 \end{align} $$ Therefore, $$ \begin{align} &\left[x^n\right]\frac1{1-x^2}\left(\frac1{1-x}\right)^3\\[3pt] &=\textstyle\frac12(-1)^n\binom{-4}{n}+\frac14(-1)^n\binom{-3}{n}+\frac18(-1)^n\binom{-2}{n}+\frac1{16}(-1)^n\binom{-1}{n}+\frac1{16}\binom{-1}{n}\\[3pt] &=\frac12\binom{n+3}{n}+\frac14\binom{n+2}{n}+\frac18\binom{n+1}{n}+\frac1{16}+\frac1{16}(-1)^n\\ &=\frac{4(n+3)(n+2)(n+1)+6(n+2)(n+1)+6(n+1)+3+3(-1)^n}{48}\\ &=\frac{(4n+14)(n+3)(n+1)+3\left(1+(-1)^n\right)}{48}\tag4 \end{align} $$ For $n=7$, we get $$ \frac{42\cdot10\cdot8}{48}=70\tag5 $$

Answer 2

So first of all, the solution without that condition is $\binom{12-1}{4-1}$. Since the sets are all non - empty.

Notice that $Q-P$ is a positive integer as well. The number of solutions with condition imposed is the number of positive integer solutions of

$2P+(Q-P)+R+S=12$

Since the number is small, You can count solutions for $2P=2,4,6,8$.

$2P=2,\ \ (Q-P)+R+S=10$ there are $\binom{10-1}{3-1}=36$ solutions

$2P=4,\ \ (Q-P)+R+S=8$ there are $\binom{8-1}{3-1}=21$ solutions

$2P=6,\ \ (Q-P)+R+S=6$ there are $\binom{6-1}{3-1}=10$ solutions

$2P=8,\ \ (Q-P)+R+S=4$ there are $\binom{4-1}{3-1}=3$ solutions

Total $70$ solutions

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} &\bbox[5px,#ffd]{\sum_{P = 1}^{\infty}\sum_{Q = 1}^{\infty} \sum_{R = 1}^{\infty}\sum_{S = 1}^{\infty}\bracks{P < Q} \bracks{z^{12}}z^{P + Q + R + S}} \\[5mm] = &\ \bracks{z^{8}}\sum_{P = 0}^{\infty}z^{P} \sum_{Q = 0}^{\infty}z^{Q}\bracks{Q > P} \sum_{R = 0}^{\infty}z^{R}\sum_{S = 0}^{\infty}z^{S} \\[5mm] = &\ \bracks{z^{8}}\pars{1 - z}^{-2}\sum_{P = 0}^{\infty}z^{P} \sum_{Q = P + 1}^{\infty}z^{Q} = \bracks{z^{8}}\pars{1 - z}^{-2}\sum_{P = 0}^{\infty}z^{P}\, {z^{P + 1} \over 1 - z} \\[5mm] = &\ \bracks{z^{7}}\pars{1 - z}^{-3}\sum_{P = 0}^{\infty}z^{2P} = \bracks{z^{7}}\pars{1 - z}^{-3}\,{1 \over 1 - z^{2}} \\[5mm] = &\ \bracks{z^{7}}\pars{1 - z}^{-4}\pars{1 + z}^{-1} = \sum_{k = 0}^{7}\bracks{z^{7}}\pars{1 - z}^{-4}\pars{-1}^{k}z^{k} \\[5mm] = &\ \sum_{k = 0}^{7}\pars{-1}^{k}\bracks{z^{7 - k}}\pars{1 - z}^{-4} = -\sum_{k = 0}^{7}\pars{-1}^{k}\bracks{z^{k}}\pars{1 - z}^{-4} \\[5mm] = &\ -\sum_{k = 0}^{7}\pars{-1}^{k}{-4 \choose k}\pars{-1}^{k} = -\sum_{k = 0}^{7}\pars{-1}^{k}{k + 3 \choose 3} = \bbx{\Large 70} \\ & \end{align}