# Interesting Combinatorics Problems

44 分钟读完

KiKi 女神在 midterm 之前的出勤率低于 50%，而之后的出勤率可谓超神，达到了 99.99%，你猜她唯一没来的那次是因为什么？（睡过了，逃。。）你们再猜，为什么她 midterm 前后出勤率竟有如此大的差距？(Hint: 不是因为 midterm 考砸了)

## Struggles and blocks

### 1. Combination Property

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

### 2. Binomial Theorem

$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$

### 3. Multinomial Coefficient

How many distinct rearrangements can be made using all of the letters of “BOOKKEEPING”?

$\binom{11}{2,2,2,1,1,1,1,1} = \frac{11!}{2! \cdot 2! \cdot 2!}$

### 4. Recursive Formula

Give a recursive formula for the function $g(n)$ that counts the number of ternary strings of length $n$ that do not contain $2002$ as a substring.

$g(n) = 3g(n-1) - g(n-3) + 2g(n-4)$

### 5. Another Combination Property

$\binom{n}{0} + \binom{n+1}{1} + ... + \binom{n+k}{k} = \binom{n+k+1}{k}$

### 6. Degree Sequence

A degree sequence of a graph is a list of the degrees of each vertex. Consider the following lists of six positive integers:

$A = [3,2,2,1,1,1] \\ B = [5,5,5,4,3,2] \\ C = [5,5,4,4,3,3] \\ D = [4,4,2,2,2,2] \\ E = [3,3,3,3,3,3]$

Determine which sequence(s):

(a) cannot be the degree sequence of a graph:
Answer: $B$ cannot be the degree sequence of any graph, because the first three vertices are connected to every other vertex in the graph – in particular, vertex 6. This means that vertex 6 should have degree at least $3$, which it doesn’t.

(b) must be the degree sequence of an eulerian graph:
Answer: $D$ must be the degree sequence of a Eulerian graph because every vertex has even degree.

(c) must be the degree sequence of a hamiltonian graph:
Answer: Degree sequences $C$ and $E$ must be that of a Hamiltonian graph because this graph has six vertices and every vertex has degree at least $\frac{6}{2}$. By Dirac’s theorem, it must have a Hamiltonian circuit.

(d) could be the degree sequence of a tree:
Answer: $A$ could be the degree sequence of a tree because the sum of the degrees is equal to $10$, so the number of edges is $5$, which is equal to the number of vertices minus $1$.

(e) could be the degree sequence of a graph, but cannot be a planar graph:
Answer: None of the graphs satisfy this condition.

### 7. Generating functions

Find the coefficient of $x^n$ in each of the generating functions below.

(a) $\frac{1}{1+4x}$

Generating function:

$\frac{1}{1-(-4x)} = 1 - 4x + 16x^2 - 64x^3 + ... = \sum_{n=0}^{\infty} (-4x)^n$

The coefficient of $x^n$ is

$(-4)^n$

(b) $\frac{1-x^{14}}{1-x}$

Generating function:

$\sum_{n=0}^{13} x^n = 1 + x + x^2 + ... + x^{13}$

Therefore, the sequence corresponding to this generating function is

$a_n = \begin{cases} 1, & 0 \le n \le 13\\ 0, & n \ge 14 \end{cases}$

(c) $(1+x^3) \cdot (x^3 + x^4 + x^5 + …) \cdot (1 + x^5 + x^{10} + …)$

The general expression of the coefficient ($a_n$) corresponding to $x^n$ is

$a_n = \begin{cases} 0, & 0 \le n \le 2\\ \lfloor \frac{n - 3}{5} \rfloor + \lfloor \frac{n - 6}{5} \rfloor + 2, & n \ge 3 \end{cases}$

### 8. Recurrence Relation

Solve the following linear, homogeneous, degree-2 recurrence relation:

$b_n = 3b_{n-1} + 3b_{n-2}$

where $b_1 = 4$ and $b_2 = 15$.

$b_n = \left(\frac{1}{2} - \frac{5}{2\sqrt{21}}\right) \cdot \left(\frac{3-\sqrt{21}}{2}\right)^n + \left(\frac{1}{2} + \frac{5}{2\sqrt{21}}\right) \cdot \left(\frac{3+\sqrt{21}}{2}\right)^n$
where $n \ge 0$ and $n \in \Z$.