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.

  • 0
    Why do you think that $n$-combination formula, which I think should be $\binom{n+k-1}{k-1}$, is applicable?2012-09-27

1 Answers 1

1

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.

  • 0
    @yuan: Yes, I know; I used that in my answer.2013-07-23