Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer 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.

share|improve this answer
    
@yuan: Yes, I know; I used that in my answer. –  Brian M. Scott Jul 23 '13 at 5:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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