Find $n$ if $\sum_{p=1}^{n}\sum_{q=p}^{n}(^nC_q)(^qC_p)=211$

Question

Find $n$ if $\sum_{p=1}^{n}\sum_{q=p}^{n}(^nC_q)(^qC_p)=211$

I found a similar question here that makes me wonder if there is a typo in the question I am asking.

If I take the question at face value and try expanding it, I get, for $p=1$

$(^nC_1)(^1C_1)+(^nC_2)(^2C_1)+(^nC_3)(^3C_1)+...$

for $p=2$,

$(^nC_2)(^2C_2)+(^nC_3)(^3C_2)+...$

Answer 1

Consider what happens if you start the sum at $p=0$ instead. Try to think of a combinatorial problem that the summation answers

Example combinatorial problem:

"Suppose I have $n$ distinctly labeled balls, all originally painted white. In how many ways can I paint them either as white, pink, and/or pink with blue polka dots?" If you approach the problem directly? If you approach the problem by applying a layer of pink paint to some number of them, and of those painted pink applying a layer of polka dots on top to some. Now, modify the problem so as to ensure you have at least some polka dotted balls at the end to account for starting the sum at $p=1$ instead of at $p=0$.

$~$

Approaching indirectly:

Break into cases, picking how many will be polkadotted in the end, noting it must be at least one. Break into cases based on how many need a pink layer of paint. Pick which get a layer of pink paint and of those pick which further get polkadots. This gives $\sum\limits_{p=1}^n\sum\limits_{q=p}^n\binom{n}{q}\binom{q}{p}$

Approaching directly:

To each ball assign as either white, pink, or polkadotted. Remove from the count the scenario of all exclusively being white and/or pink. $3^n-2^n$

$~$

Finding an $n$ that works

$3^5-2^5 = 211$

Answer 2

We are looking for $n$ which are solutions to \begin{align*} \color{blue}{\sum_{p=1}^n\sum_{q=p}^n\binom{n}{q}\binom{q}{p}=211}\tag{1} \end{align*}

Here is a starter. We can considerably simplify the binomial sum which makes it easier to look for solutions $n$.

We obtain \begin{align*} \color{blue}{\sum_{p=1}^n}\color{blue}{\sum_{q=p}^n\binom{n}{q}\binom{q}{p}} &=\sum_{p=1}^n\binom{n}{p}\sum_{q=p}^n\binom{n-p}{q-p}\tag{2}\\ &=\sum_{p=1}^n\binom{n}{p}\sum_{q=0}^{n-p}\binom{n-p}{q}\tag{3}\\ &=\sum_{p=1}^n\binom{n}{p}2^{n-p}\tag{4}\\ &=\sum_{p=0}^n\binom{n}{p}2^{n-p}-2^n\tag{5}\\ &\,\,\color{blue}{=3^n-2^n}\tag{6} \end{align*} Now we have simplified (1) to the equation \begin{align*} \color{blue}{3^n-2^n=211} \end{align*} which can be checked for small $n$.

Comment:

• In (2) we use the binomial identity \begin{align*} \binom{n}{q}\binom{q}{p}&=\frac{n!}{q!(n-q)!}\,\frac{q!}{p!(q-p)!}\\ &=\frac{n!}{p!(n-p)!}\,\frac{(n-p)!}{(n-q)!(q-p)!}=\binom{n}{p}\binom{n-p}{n-q} \end{align*}

• In (3) we shift the index of the inner sum and start with $q=0$. We compensate this by substituting in the summand $q\to q+p$.

• In (4) we apply the binomial theorem to the inner sum.

• In (5) we add the term with index $p=0$ and subtract $2^n$ for compensation.

• in (6) we apply the binomial theorem again.