2
$\begingroup$

Say I want to find the number of different ways of unordered sampling k elements from n distinguishable elements with replacement, and a common way is to use the method of stars and bars. Although this is artful and easy to understand, I want to know whether there are other methods to solve this problem, and if there are, what are those methods? And the more direct, the rawer, the better!

BTW, I have searched in a few textbooks on this problem, and it seems all of them are using the above method.

$\endgroup$
3
$\begingroup$

If you multiply out $(1+x+x^2+\ldots)^n$ distributively then you get a term $x^{k_1}x^{k_2}\>\cdots\> x^{k_n}$ for each independent sampling of a term in each of the factors. Collecting terms according to increasing powers of $x$ we obtain a formal series $\sum_{k\geq0} a_k\>x^k$, whereby $a_k$ counts the number of samplings $(k_1,k_2,\ldots,k_n)$ with $k_1+k_2+\ldots+k_n=k$.

Now $$(1+x+x^2+\ldots)^n={1\over (1-x)^n}=\sum_{k=0}^\infty{-n\choose k} (-x)^k$$ (binomial series). It follows that $$a_k=(-1)^k{-n\choose k}={n+k-1\choose k}\ .$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your nice solution using generating function! $\endgroup$ – Daniel Aug 16 '16 at 13:56

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.