DMAT_L6

Picking objects

Say you have to pick $k$ objects from $n$ objects.

With replacement Without replacement Order matters n^{k} n (n - 1) \dots (n - k + 1) Order doesn’t matter (k - 1 n + k - 1) (k n)

Counting functions

Let $f : A \to B$ , $∣ A ∣ = m$ , $∣ B ∣ = n$ .

Total number of functions $f$ is $n^{m}$ .
Total number of injections is $n (n - 1) (n - 2) \dots (n - m + 1)$ .

One way to calculate the total number of surjections is to first consider the sizes of the preimage sets of every $b \in B$ . Define $∣ f^{- 1} (b_{i}) ∣ = β_{i}$ , $1 \leq i \leq n$ . We know that $β_{i} > 0$ for all $i$ , and $\sum β_{i} = m$ . Let $(β_{1}, β_{2}, \dots, β_{n})$ be a solution to $\sum β_{i} = m$ . Then, the number of functions satisfying $∣ f^{- 1} (b_{i}) ∣ = β_{i}$ is $\frac{m !}{β _{1} ! β _{2} ! \dots β _{n} !}$ . Thus, the total number of surjections is

β_{i} > 0, \sum β_{i} = m \sum \frac{m !}{β _{1} ! β _{2} ! \dots β _{n} !} . (1)

Notice that if we remove the $β_{i} > 0$ restriction, the formula basically gives the total number of functions from $A$ to $B$ , courtesy the multinomial theorem:

\sum β_{i} = m \sum \frac{m !}{β _{1} ! β _{2} ! \dots β _{n} !} = (n)^{m} .

Evaluating $(1)$ directly is not easy. We could instead use the inclusion-exclusion principle to isolate all the cases when $β_{i} = 0$ for some $i$ (functions that are not surjective), and subtract it away from $n^{m}$ . The number of non-surjective functions is

= (1 n) (n - 1)^{m} - (2 n) (n - 2)^{m} + (3 n) (n - 3)^{m} - \dots + (- 1)^{n} (n - 1 n) (1)^{m} i = 1 \sum n - 1 (- 1)^{i + 1} (i n) (n - i)^{m}

Subtracting it away from $n^{m}$ , we get (Note that setting the upper limit to $n$ or $n - 1$ is the same)

Total number of surjections = n^{m} - i = 1 \sum n - 1 (- 1)^{i + 1} (i n) (n - i)^{m} = n^{m} + i = 1 \sum n - 1 (- 1)^{i} (i n) (n - i)^{m} = i = 0 \sum n (- 1)^{i} (i n) (n - i)^{m}

Incidentally, the Sterling number of the second kind, which counts the number of ways to partition a set of size $m$ into $n$ non-empty subsets, is given by

S (m, n) = \frac{1}{n !} i = 0 \sum n (- 1)^{i} (i n) (n - i)^{m}

Basic properties of the binomial coefficient

(r n) + (r + 1 n) = (r + 1 n + 1)

r = o \sum n (r n) = 2^{n}

(k k) + (k k + 1) + (k k + 2) + \dots + (k k + n) = (k + 1 k + n + 1)

(r n) = \frac{n}{r} (r - 1 n - 1)

(r n _{1}) (0 n _{2}) + (r - 1 n _{1}) (1 n _{2}) + \dots + (0 n _{1}) (r n _{2}) = (r n _{1} + n _{2})

(k n) - (k - 1 n) + \dots \mp (1 n) \pm 1 = (k n - 1)

^ easy proof by induction

NoNotes

Graph View

DMAT_L6

Picking objects

Counting functions

Basic properties of the binomial coefficient

Table of Contents

Backlinks