next up previous contents
Next: Some more identities Up: Selection and Binomial Coefficients Previous: Selection and Binomial Coefficients   Contents


The number of ways of choosing $ m$ objects out of $ n$ objects is
  ordered unordered
no repeats $ n^{\underline{m}}$ $ \binom{n}{m}$
repeats $ n^m$ $ \binom{n-m+1}{m}$
The only entry that needs justification is $ \binom{n-m+1}{m}$. But there is a one-to-one correspondance betwen the set of ways of choosing $ m$ out of $ n$ unordered with possible repeats and the set of all binary strings of length $ n + m - 1$ with $ m$ zeros and $ n-1$ ones. For suppose there are $ m_i$ occurences of element $ i$, $ m_i \ge 0$. Then

$\displaystyle \sum_{i=1}^n m_i = m \leftrightarrow
\underbrace{0 \dots 0}_{m_1} 1 \underbrace{0 \dots 0}_{m_2} 1 \dots 1
\underbrace{0 \dots 0}_{m_n}.

There are $ \binom{n-m+1}{m}$ such strings (choosing where to put the $ 1$'s).

root 2002-06-10