Skip to content

3.10 Counting maps

Let \(X\) be the set of balls and \(Y\) be the set of baskets

\(f:X\to Y\) determine a way of distributing balls into the baskets

The cardinality of function

Let \(X,Y\) be two finite sets, then \(|\{f:X\to Y\}|=|Y|^{|X|}\). Notation: \(Y^X=\{f:X\to Y\}\)

Proof

Let \(|Y|=y\) and \(|X|=x\). Then \(y^x=|\underbrace{(Y\times...\times Y)}_{x \text{ times}}|\). Assume \(X=\{a_1,...,a_x\}\).

Given \((f(a_{1}),...,f(a_{x}))\in Y^{X}\), then \(f:X\to Y\) produce \((f(a_1),...,f(a_x))\in \underbrace {Y\times ...\times Y}_{x\text{ times}}\)

Given \((y_{1},...,y_{x})\in\underbrace{Y\times...\times Y}_{x\text{ times}}\), thus define \(f:X\to Y\) by \(a_1\mapsto y_i\), then \((f(a_{1}),...,f(a_{x}))\in Y^{X}\)

Thus we have \(\varphi:Y^{X}\to Y\times...\times Y\) and \(\psi:Y\times...\times Y\to Y^{X}\), then \(\varphi\circ \psi=Id\) and \(\psi\circ\varphi=Id\)

Thus \(Y\times...\times Y\) and \(Y^{X}\) are in bijections. Then we can use multiplication principle

Recall: the same problem arises when counting words composed of letters of a fixed alphabet.

The cardinality of subsets(Important particular case)

If \(Y=\{0,1\}\), for any finite \(X\) we have \(|\{f:X\to Y\}|=2^{|X|}\)

Every function \(f:X\to \{0,1\}\) defines a subset of \(X\)

Given \(f:X\to \{0,1\}\) define \(A_f=f^{-1}(\{1\})=\{x\in X:f(x)=1\}\subseteq X\)

Given \(A\subseteq X\), we define \(f_A:X\to\{0,1\}\) where \(\begin{cases} x\mapsto0,x\notin A \\ x\mapsto1,x\in A \end{cases}\)

We have just proven \(|\{A\subseteq X\}|=2^{|X|}\)

Translation to the language of balls and baskets.

Baskets are numbered.

Balls are the same, their number is not fixed, and there is at most one ball per basket.image​

The cardinality of injective function

The number of injective functions from \(X\) to \(Y\): \(|\{f : X \to Y \mid f \text{ is injective} \}|\) where \(f\) is injective \((f(x) = f(y) \implies x = y)\)

Baskets are labeled. Balls are also labeled. The number of balls is fixed. At most one ball per basket.

Proposition:

Let X and Y be two finite sets. Then \(|\{f : X \to Y \mid f \text{ is injective} \}| = \frac{(|Y|)!}{(|Y| - |X|)!}\)

Definition of \(n!\): set \(0!=1\) and define \((n+1)!=(n+1)n!\)

Proof

\(X=\{a_1,...,a_x\}\)

There are \(|Y|\) possible choices for \(f(a_1)=y_1\)

There are \(|Y|-1\) possible choices for \(f(a_2)=y_2\)

....

There are \(|Y|-\left|X\right|+1\) possible choices for \(f(a_{x})=y_{x}\)

We conclude that \(|\{f:X\to Y\mid f\text{ is injective}\}|=\left|Y\right|\left(\left|Y\right|-1\right )\ldots\left(\left|Y\right|-\left|X\right|+1\right)=\frac{(|Y|)!}{(|Y|-|X|)!}\)

If \(|X|>|Y|\), then \(|\{f:X\to Y\mid f\text{ is injective}\}|=0\)

It justifies \((-n)!=\infty,\forall n\in\N\)​

A piece of notation

Let \(a\) be a number \(n\) is a natural number.

Set \((a)_n =\begin{cases} 1, & n = 0 \\a(a-1) \dots (a-n+1), & n \geq 1\end{cases}\)
This is called the "falling factorial" or the "Pochhammer symbol" .

\(\left|\{f:X\to Y\mid f\text{ is injective}\}\right|=\left(\left|Y\right|\right)_{\left|X\right|}\) and \(\left|\{f:\emptyset\to Y\mid f\text{ is injective}\}\right|=1.\)

Important Particular Case

\(\# Y = \# X \quad (\text{or } X = Y).\)

If \(f: X \to Y\) is injective, then is \(f: X \to Y\) bijective?

In this case, we have:

\(\# \{ f: X \to Y \} = (\# Y)! = (\# X)!\)image​

‍

Binomial coefficients

Baskets are different. Balls are identical, and their number is fixed. No more than 1 ball per a basket.image​

We want to count: \(|\{A\subseteq X:|A|=k\}|\)

Inductive way

Let \(|X|=n\in \N\cup \{0\}\) and denote \(\left|\left\lbrace A\subseteq X:|X|=n,|A|=k\right\rbrace\right|=\binom{n}{k}\) this is binomial coefficients

Obvious remarks: \(\binom00=1\), then \(\binom{n}{0}=\binom{n}{n}=1,\forall n\in\mathbb{N}\) and \(\binom{n}{k}=0\) if either \(k<0\) or \(k>n\)

Proposition

\(\forall n\geq 1\) and any \(k=1,...,n-1\) we have \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\)

Proof

Consider \(X=\{a_1,...,a_n\}\), we need to count all possible \(k\)-element subsets of \(X\)

image​

image​

Proposition

\(\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}=\frac{\left(n\right)_{k}}{k!}\)

Proof

\((n)_{k}=\left\lbrace f:X\to Y:f\text{ is injective}\right\rbrace\) and \(|Y|=n,|X|=k\)image​

Let \(\varphi:\left\lbrace f:X\to Y:f\text{ is injective}\right\rbrace\to\left\lbrace A\subseteq Y\right\rbrace\) where \(f\mapsto Imf\)

Every element \(A\subset Y\) has the same number \(|X|!=k!\), preimages under this map

Then use division principle, \(\binom{n}{k}=\frac{\left(n\right)_{k}}{k!}=\frac{n!}{k!\left(n-k\right)!}\)​

Exercise

\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\) holds for any value of \(n\), not necessarily a natural number.

Proposition

Let \(n\in\N\), then \(\sum_{k=0}^{n}\binom{n}{k}=2^{n}\)​

Proof

Right hand is \(\left|\left\lbrace A\subseteq X:|X|=n,A\text{ is not fixed}\right\rbrace\right|\)

Left hand is \(\sum_{k=0}^{n}\left|\lbrace A\subseteq X:|X|=n,|A|\text{ is exactly k}\rbrace\right|\), then addition principle asserts the equality

‍