Interesting Combinatorics Problems

44 分钟读完

在多大学习的最后一学期有幸和 KiKi 女神同课 MAT344 (不是 cs 有点遗憾),这也是我辅修数学的收官课。这学期 MAT344 的难度较往年提升了不少,Midterm 的画风跟水课完全不沾边。每周 lecture 学生的平均出勤率少于 50%,所以也不难想象 midterm 是有多惨烈了,部分愣头青还去了 math dept 投诉……

compaints

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

言归正传:MAT344 这学期的两个 instructor 都非常认真负责,其中 Zachary Wolske 是我 223/224 的 TA,135 的 course instructor (TA coordinator),就在这样的大环境下,KiKi 和我 midterm 之后奋起直追,希望最后能收获我们满意的结果(final还没出分)。

Struggles and blocks

1. Combination Property

(nk)=(n1k1)+(n1k)\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

2. Binomial Theorem

(x+y)n=k=0n(nk)xnkyk(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”?

(112,2,2,1,1,1,1,1)=11!2!2!2!\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(n1)g(n3)+2g(n4)g(n) = 3g(n-1) - g(n-3) + 2g(n-4)

5. Another Combination Property

(n0)+(n+11)+...+(n+kk)=(n+k+1k)\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]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:

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

The coefficient of $x^n$ is

(4)n(-4)^n

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

Generating function:

n=013xn=1+x+x2+...+x13\sum_{n=0}^{13} x^n = 1 + x + x^2 + ... + x^{13}

Therefore, the sequence corresponding to this generating function is

an={1,0n130,n14a_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

an={0,0n2n35+n65+2,n3a_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:

bn=3bn1+3bn2b_n = 3b_{n-1} + 3b_{n-2}

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

Answer:

bn=(125221)(3212)n+(12+5221)(3+212)nb_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$.

分类:

更新时间:

返回顶部 ↑

留下评论