3
$\begingroup$

Problem statement:

Show that the number of r-combinations of specification $2^m1^{n-2m}$ is $$\sum_k {{m}\choose {k}}{{n-m-k}\choose{r-2k}}$$

I have found the generating function which is $(1+t+t^2)^m(1+t)^{n-2m}$, but I cannot proceed further to find the general coefficient.

I know the combinatorial proof for this question, I am specifically wanting to practice using generating functions. Any hint will also suffice.

I have tried using the geometric series formula and then Taylor expansion but could not proceed further.

Edit: The particular specification given here means there are objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct.

$\endgroup$
  • 2
    $\begingroup$ Actually, I am not sure what you mean by "r-combinations of specification $2^m1^{n-2m}$" (This may very well be due to my limited knowledge). Can you please pose the combinatorial question in words? $\endgroup$ – Anubhab Ghosal Jan 14 at 14:35
  • $\begingroup$ @AnubhabGhosal 'r-combinations' means combinations of r elements and the particular specfication given here means objects of m kind with 2 of each kind and (n-2m) remaining objects that are distinct. $\endgroup$ – Shubhraneel Pal Jan 14 at 14:40
  • $\begingroup$ What do you mean when you say "objects of m kind with 2 of each kind"? Do you mean that there are 2m objects where each object has an identical partner? $\endgroup$ – Cardioid_Ass_22 Jan 14 at 14:52
  • $\begingroup$ @Cardioid_Ass_22 yes $\endgroup$ – Shubhraneel Pal Jan 14 at 14:54
  • $\begingroup$ Maybe use $1+t+t^2=(1-t^3)/(1-t)$? $\endgroup$ – marty cohen Jan 14 at 14:59
3
$\begingroup$

Here we use the coefficient of operator $[x^r]$ which denotes the coefficient of $x^r$ of a series. This way we can write for instance \begin{align*} \binom{n}{r}=[x^r](1+x)^n \end{align*}

We obtain for non-negative integers $n\geq 2m$ and $r\geq 0$: \begin{align*} \color{blue}{\sum_{k=0}^m}&\color{blue}{\binom{m}{k}\binom{n-m-k}{r-2k}}\\ &=\sum_{k=0}^m\binom{m}{k}[x^{r-2k}](1+x)^{n-m-k}\tag{1}\\ &=[x^r](1+x)^{n-m}\sum_{k=0}^m\binom{m}{k}\left(\frac{x^2}{1+x}\right)^k\tag{2}\\ &=[x^r](1+x)^{n-m}\left(1+\frac{x^2}{1+x}\right)^m\tag{3}\\ &\,\,\color{blue}{=[x^r](1+x)^{n-2m}\left(1+x+x^2\right)^m} \end{align*} and we conclude \begin{align*} \sum_{r=0}^\infty\left(\sum_{k=0}^m\binom{m}{k}\binom{n-m-k}{r-2k}\right)x^r =(1+x)^{n-2m}\left(1+x+x^2\right)^m \end{align*}

Comment:

  • In (1) we apply the coefficient of operator.

  • In (2) we factor out terms independent of $k$ by using the linearity of the coefficient of operator and applying the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$.

  • In (3) we apply the binomial theorem.

$\endgroup$
0
$\begingroup$

On one hand $$(1+t+t^2)^m=\sum_{i=0}^m\binom{m}{i}(1+t)^i(t^2)^{m-i}=\sum_{i=0}^m\binom{m}{i}\Biggl(\sum _{j=0}^i\binom{i}{j}t^j1^{i-j}\Biggr)t^{2m-2i}=\\\sum_{i=0}^m\sum _{j=0}^i\binom{m}{i}\binom{i}{j}t^{j+2m-2i}$$

On the other $$(1+t)^{n-2m}=\sum_{k=0}^{n-2m}\binom{n-2m}{k}t^k1^{n-2m-k}=\sum_{k=0}^{n-2m}\binom{n-2m}{k}t^k$$

Now, let's look at the sum representation we found for $(1+t+t^2)^m$ first (since it's the scarier looking one) and try to simplify it. Suppose we can rewrite this sum as $$\sum_pa_pt^p$$ That would be very convenient as this is a nice single sum rather than a double sum. To do that, we need to find $a_p$ in general. Looking at the original double sum we can see that we can find $a_p$ by finding all pairs of $j$ and $i$ such that $j\leq i$ and $j+2m-2i=p$- then, calculate for each pair, $\binom{m}{i}\binom{i}{j}$, and sum all of these binomial products up. Suppose for our (fixed) $p$ we also fixed $i$ at some value between $0$ and $m$. Well, in that case $j$ could take on at most one value- that would be $p+2i-2m$. We say "at most" because $j$ also needs to be $\leq i$, i.e., $p+2i-2m\leq i\implies i\leq 2m-p$. Don't forget though that $j$ also has to be $\geq 0$- this means $p+2i-2m\geq 0\implies i\geq m-\frac{p}{2}$ ($j$ will always be an integer so we won't worry about that). So if we vary $i$ between $0$ and $m$, $i$ contributes to the coefficient, $a_p$, iff $m-\frac{p}{2}\leq i\leq 2m-p$, and when that is the case, $i$ contributes exactly $\binom{m}{i}\binom{i}{p+2i-2m}$ to $a_p$.

In other words, $$a_p=\sum_{i=m-\lfloor\frac{p}{2}\rfloor}^{2m-p}\binom{m}{i}\binom{i}{p+2i-2m}$$

What are the possible values $p$ can take? Well, for each $p$ there must exist $i$ and $j$ in the original double sum's index so that $p=j+2m-2i$ so $p=j+2m-2i\leq i+2m-2i=2m-i\leq 2m$. Also $p=j+2m-2i\geq 0+2m-2i=2m-2i\geq 2m-2m=0$. So $p$ ranges from $0$ to $2m$.

Overall we have that $$(1+t+t^2)^m=\sum_{p=0}^{2m}a_pt^p$$ where, for each $p$ $$a_p=\sum_{i=m-\lfloor\frac{p}{2}\rfloor}^{2m-p}\binom{m}{i}\binom{i}{p+2i-2m}$$

Time to tackle the big boi.

Now we need to find a nice single sum representation for $(1+t+t^2)^m(1+t)^{n-2m}$. Well, we have a nice(ish) single sum for each of the terms individually- let's try smashing them together.

$$(1+t+t^2)^m(1+t)^{n-2m}=\Biggl(\sum_{p=0}^{2m}a_pt^p\Biggr)\Biggl(\sum_{k=0}^{n-2m}\binom{n-2m}{k}t^k\Biggr)=\sum_{p=0}^{2m}\sum_{k=0}^{n-2m}a_p\binom{n-2m}{k}t^{p+k}$$

Now, we run the same trick again and suppose that this double sum has some single sum expression like $$\sum_qb_qt^q$$

To find $b_q$ here, we need find pairs of $p$ and $k$ such that $p+k=q$, $0\leq p\leq 2m$, and $0\leq k\leq n-2m$. Now, suppose we fix some $p$ between $0$ and $2m$. Then $k$, again, has at most one value, i.e, $q-p$, and this one value is only valid if $0\leq k\leq n-2m \implies 0\leq q-p \leq n-2m \implies q-n-2m\leq p\leq q$. This gives us that $$b_q=\sum_{p=q-n-2m}^qa_p\binom{n-2m}{q-p}$$

Again, we can refer to the initial double sum to see that $p+k$ will always vary between $0$ and $n$, so $q$ varies between $0$ and $n$.

This all means: $$(1+t+t^2)^m(1+t)^{n-2m}=\sum_{q=0}^nb_qt^q$$

where, for each $q$ $$b_q=\sum_{p=q-n-2m}^qa_p\binom{n-2m}{q-p}$$

The $b_q$ are the coefficients we desire. To simplify (it's really just making things messier) plug in the general single sum expression for $a_p$ $$b_q=\sum_{p=q-n-2m}^q\Biggl(\sum_{i=m-\lfloor\frac{p}{2}\rfloor}^{2m-p}\binom{m}{i}\binom{i}{p+2i-2m}\Biggr)\binom{n-2m}{q-p}=\\\sum_{p=q-n-2m}^q\sum_{i=m-\lfloor\frac{p}{2}\rfloor}^{2m-p}\binom{m}{i}\binom{i}{p+2i-2m}\binom{n-2m}{q-p}$$

After some checking now, I'm pretty sure the working is correct but given the number of mistakes I made writing this, there's still a good chance I messed up somewhere. Regardless, this is basically how you can find the coefficients in general. You'll always end up with a double sum, like the final expression for $b_q$, so you'll probably need to pull out some nifty binomial identities or something to simplify it down to the single sum your question asks for. Or just look at Markus' way simpler answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.