DMAT_L8

The twelve fold way

Placement of $m$ balls in $n$ boxes.

Unrestricted

• labeled, labeled: $n^m$
• unlabeled, labeled: $\left(\genfrac{}{}{0ex}{}{n+m-1}{n-1}\right)$
• labeled, unlabeled: ${\sum }_{i=1}^{n}S(m,i)$.
• unlabeled, unlabeled: $P_n={\sum }_{i=1}^{n}P(m,i)$. where $P(m,i)$ is the number of ways to split $m$ into $i$ parts. No closed for $P_n$.

Generating function for $P_n$:

$$\sum _{n\ge 0}{P}_n{x}^n=\prod _{j=1}^{\infty }\left(\frac{1}{1-x^j}\right)$$

Generating function for (unlabeled, labeled): $(1+x+x^2+\dots {)}^n=\frac{1}{(1-x{)}^n}=(1-x{)}^{-n}$.

Injective

• labeled, labeled: $(n{)}_m$
• unlabeled, labeled : $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$
• labeled, unlabeled: 0 or 1
• unlabeled, unlabeled: 0 or 1

Surjective

• labeled, labeled: $S(m,n)n!$
• unlabeled, labeled: $\left(\genfrac{}{}{0ex}{}{m-1}{n-1}\right)$
• labeled, unlabeled: $S(m,n)$
• unlabeled, unlabeled: $P(m,n)$.

---

Linear Recurrence relations and generating functions

A few notes:

• For linear recurrence relations, if we can find any solutions, we can take linear combinations of them to generate new solutions. For example, If $F$ and $G$ satisfy a recurrence relation, $H_n=a{F}_n+b{G}_n$ also satisfies it.

Number of subsets

Let $F(n)=$ number of subsets of $[n]$.

$F(n)=2F(n-1)$ for all $n\ge 1$.
$F(0)=1$.

Let $\varphi (x)\equiv {\sum }_{n\ge 0}F(n)x^n$. This is called a generating function.

$$2x\varphi (x)=\sum _{n\ge 1}F(n)x^n=\varphi (x)-1$$

so, $\varphi (x)=\frac{1}{1-2x}=1+2x+(2x{)}^2+(2x{)}^3+\dots$

Observe that $\varphi$ has a radius of convergence of $\frac{1}{2}$, so our manipulations are justified by analysis. This does not always need to be the case.

The Fibonacci sequence

Let $F(n)$ be the Fibonacci sequence. There are several methods to solve for the explicit formula for $F(n)$.

Method 1: Exponential ansatz

Try a solution of the form $F_n={\alpha }^n$. This gives us the characteristic equation ${\alpha }^2-\alpha -1$, the roots of which are $\alpha =\frac{1}{2}(1\pm \sqrt{5})$. Thus, a general solution would be of the form

$$F_n=a{\left(\frac{1+\sqrt{5}}{2}\right)}^n+b{\left(\frac{1-\sqrt{5}}{2}\right)}^n.$$

Use the initial conditions of $F_0=0$ and $F_1=1$ to solve for $a$ and $b$.

Method 2: Matrix diagonalization

https://austinrochford.com/posts/2014-04-23-diagonalization-fibonacci.html

Express the recurrence as a matrix product:

$$\left(\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right)=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{F}_n\\ F_{n-1}\end{array}\right).$$

Let $X$ be the coefficient matrix of the recurrence. Then,

$$\left(\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right)=X^n\left(\begin{array}{c}1\\ 0\end{array}\right).$$

It would be beneficial to diagonalize $X$, since powers of a diagonal matrix are easy to compute. The characteristic polynomial of $X$ is the same as the characteristic equation we obtained in the previous method, so $\varphi ,\psi =\frac{1}{2}(1\pm \sqrt{5})$ are the eigenvalues of $X$. We can find and normalize the eigenvectors corresponding to these eigenvalues to obtain the change of basis matrix

$$P=\left(\begin{array}{cc}{\vec{v}}_{\phi }& {\vec{v}}_{\psi }\end{array}\right)=\frac{1}{\sqrt[4]{5}}\left(\begin{array}{cc}\sqrt{\phi }& -\sqrt{-\psi }\\ \sqrt{-\psi }& \sqrt{\phi }\end{array}\right),$$

and since $P$ is an orthogonal matrix, $P^{-1}=P^T$. This gives us

$$\begin{array}{rl}{F}_n& =\left(\begin{array}{cc}0& 1\end{array}\right)X^n\left(\begin{array}{c}1\\ 0\end{array}\right)\\ & =\left(\begin{array}{cc}0& 1\end{array}\right)P{D}^n{P}^{-1}\left(\begin{array}{c}1\\ 0\end{array}\right)\\ & =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}0& 1\end{array}\right)\left(\begin{array}{cc}\sqrt{\phi }& -\sqrt{-\psi }\\ \sqrt{-\psi }& \sqrt{\phi }\end{array}\right)\left(\begin{array}{cc}{\phi }^n& 0\\ 0& {\psi }^n\end{array}\right)\left(\begin{array}{cc}\sqrt{\phi }& \sqrt{-\psi }\\ -\sqrt{-\psi }& \sqrt{\phi }\end{array}\right)\left(\begin{array}{c}1\\ 0\end{array}\right)\\ & =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\sqrt{-\psi }& \sqrt{\phi }\end{array}\right)\left(\begin{array}{cc}{\phi }^n& 0\\ 0& {\psi }^n\end{array}\right)\left(\begin{array}{c}\sqrt{\phi }\\ -\sqrt{-\psi }\end{array}\right)\\ & =\frac{1}{\sqrt{5}}\left(\begin{array}{cc}\sqrt{-\psi }& \sqrt{\phi }\end{array}\right)\left(\begin{array}{c}\sqrt{\phi }{\phi }^n\\ -\sqrt{-\psi }{\psi }^n\end{array}\right)\\ & =\frac{1}{\sqrt{5}}\left(\sqrt{-\psi \phi }{\phi }^n-\sqrt{-\phi \psi }{\psi }^n\right)\\ & =\frac{1}{\sqrt{5}}\left({\varphi }^n-{\psi }^n\right).\end{array}$$

Method 3: Generating functions

Let $\psi (x)={\sum }_{n\ge 0}F(n)x^n$.

$$x\psi (x)=\sum _{n\ge 0}F(n)x^{n+1}$$ $$x^2\psi (x)=\sum _{n\ge 0}F(n)x^{n+2}$$ $$\psi (x)-x\psi (x)-x^2\psi (s)=1$$

So, $\psi (x)=\frac{1}{1-x-x^2}$.

Let

$$\frac{1}{1-x-x^2}=\frac{1}{(1-\alpha x)(1-\beta x)}=\frac{a}{1-\alpha x}+\frac{b}{1-\beta x}$$

where $\alpha =\frac{1+\sqrt{5}}{2}$ and $\beta =\frac{1-\sqrt{5}}{2}$.

We know $a+b=1$ and $a\beta +b\alpha =0$.
We can solve for $a$ and $b$: $a=\frac{1}{\sqrt{5}}$, $b=-\frac{1}{\sqrt{5}}$.
Thus, we have $F(n)=a{\alpha }^n+b{\beta }^n$.

Info

Once we have found the power series above, we can use the theory of power series to show that $\psi$ converges for $|x|<\frac{1}{\alpha }$, so our manipulations are justified analytically. But, there exists a theory of formal power series, according to which it is legitimate to do such manipulations without any regard to questions of convergence. If the sequence specified by a recurrence relation grows no faster than exponentially, its generating function will have non-zero radius of convergence, and analytical techniques can be used on it. However, if the growth is faster than exponential, the series must be treated formally.

Derangements

$D_n$ is the number of derangements of size $n$.

$D_0=1$, $D_1=0$, $D_2=1$, $D_n=(n-1)(D_{n-1}+D_{n-2})$

Note that $D_n-n{D}_{n-1}=(-1)(D_{n-1}-(n-1)D_{n-2})=(-1{)}^n$.

Thus, $\frac{D_{n_{}}}{n!}-\frac{D_{n-1}}{(n-1)!}=\frac{(-1{)}^n}{n!}$, $n\ge 1$.

Thus,

$$\frac{D_n}{n!}=\sum _{i=0}^n\frac{(-1{)}^i}{i!}$$