# Counting strategies

02 Apr 2019

## Binomial coefficient

${\displaystyle {\begin{array}{rcl}(1{+}x)^{4}&=&{\tbinom {4}{0}}x^{0}+{\tbinom {4}{1}}x^{1}+{\tbinom {4}{2}}x^{2}+{\tbinom {4}{3}}x^{3}+{\tbinom {4}{4}}x^{4}\\&=&1+4x+6x^{2}+4x^{3}+x^{4},\end{array}}}$

where

$${\binom {n}{k}} = \text{n choose k} = {\frac {n!}{k!(n-k)!}}$$ .

## Ball picking

Consider an infinite repository containing balls of $n$ different types. Then the following table summarizes the number of distinct ways in which $k$ balls can be picked for four common definitions of “distinct.”

• $n$ types
• pick $k$ times
• count number of possible outcomes
category number of possible outcomes
ordered sampling with replacement $n^k$
ordered sampling without replacement $P(n,k)={n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}$
unordered sampling without replacement $\binom{n}{k}$
unordered sampling with replacement $\binom{n + k - 1}{k}$

The last case can be considered k icecream scoops with (n - 1) moves to the next type.

## Story proof

(proof by interpretation)

### example 1

$\binom{n}{k} = \binom{n}{n-k}$

Chooseing $k$ people out of $n$ people is also picking the other $n-k$ people not to choose.

### example 2

$n{\binom{n-1}{k-1}} = k{\binom{n}{k}}$

To pick a leader from a group of $k$ members,

• we can choose a leader and make a club of $k-1$ members out of $n - 1$ people. Or,
• we can make a club of $k$ members and choose a leader out of a group.

### example 3 - Vandermonde Identity

${\binom{m+n}{k}} = {\sum_{j=0}^{k}\binom{m}{j}}{\binom{n}{k-j}}$