2
$\begingroup$

Here is my question:

Consider a multiset $\{n\cdot a, n\cdot b, 1,2,3, \ldots, n+1\}$ of size $3n+1$. Determine the number of $n$-combinations.

I know from my textbook that if you have a $n$-combination multiset of $k$ types, then the answer is $\binom{ n-k-1} {k-1}$ but I am unsure what is $k$ and what is $n$ here. Any help is appreciated.

$\endgroup$
  • $\begingroup$ Why do you think that $n$-combination formula, which I think should be $\binom{n+k-1}{k-1}$, is applicable? $\endgroup$ – Thomas Andrews Sep 27 '12 at 19:45
1
$\begingroup$

As Thomas Andrews said in the comments, the formula that you have in mind is actually $\binom{n+k-1}{k-1}$, but it doesn’t apply here. Here you simply have to find a way to divide up the $n$-combinations into chunks that can easily be counted and then add up the results.

First count the $n$-combinations that have $k$ of their members from the set $\{1,\dots,n+1\}$. There are $\binom{n+1}k$ ways to choose those $k$ members. The rest of the $n$-combination is completely determined by the number of $a$’s, which may be anything from $0$ through $n-k$; this is a total of $n-k+1$ possibilities, so there are $(n-k+1)\binom{n+1}k$ $n$-combinations with $k$ of their members in the set $\{1,\dots,n+1\}$. The final answer is the sum of these totals over the possible values of $k$,

$$\sum_{k=0}^n(n-k+1)\binom{n+1}k\;.$$

If you manipulate the term $(n+1-k)\binom{n+1}k$ properly, you can transform it to a term of the form $c\binom{d}k$, where $c$ and $d$ don’t depend on $k$, and then evaluate the sum quite easily. I’ve included a hint for the manipulation that you need, but I’ve left it spoiler-protected to give you a chance to work it out on your own. Mouse-over to make it visible.

The manipulation that you need is of the form $\displaystyle(m-k)\binom{m}k=m\binom{m-1}k$, which you can check by writing out the binomial coefficients in factorial form.

$\endgroup$
  • $\begingroup$ @yuan: Yes, I know; I used that in my answer. $\endgroup$ – Brian M. Scott Jul 23 '13 at 5:17

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.