组合数学 (Fall 2023)/Problem Set 2

Problem 2

Let [math]\displaystyle{ D_n }[/math] denote the number of derangements of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math].

• Give a combinatorial proof that [math]\displaystyle{ D(n)=nD(n-1)+(-1)^n }[/math].
• For a permutation [math]\displaystyle{ p_1,p_2,...,p_n }[/math], for [math]\displaystyle{ 1\leq i\lt n }[/math], we call position[math]\displaystyle{ i }[/math] ascent if [math]\displaystyle{ p_i\lt p_{i+1} }[/math]. Let [math]\displaystyle{ \mathcal{E}_n }[/math] denote the set of permutations whose first ascent is in an even position (where we always count [math]\displaystyle{ n }[/math] as an ascent). For instance, [math]\displaystyle{ \mathcal{E}(3)=\{213, 312\} }[/math] and [math]\displaystyle{ \mathcal{E}(4)=\{2134, 2143, 3124, 3142, 3241, 4123, 4132, 4231, 4321\} }[/math]. Set [math]\displaystyle{ E(n)=|\mathcal{E}(n)| }[/math]. Show that [math]\displaystyle{ E(n)=nE(n-1)+(-1)^n }[/math]. Hence (since [math]\displaystyle{ E(1)=D(1)=0 }[/math]) we have [math]\displaystyle{ E(n)=D(n) }[/math].
• Give a bijection between the permutations being counted by [math]\displaystyle{ E(n) }[/math] and the derangements of [math]\displaystyle{ [n] }[/math].

Problem 3

Let [math]\displaystyle{ S=\{P_1,...,P_n\} }[/math] be a set of properties, and let [math]\displaystyle{ f_k }[/math] (respectively, [math]\displaystyle{ f_{\geq k} }[/math]) denote the number of objects in a finite set [math]\displaystyle{ U }[/math] that satisfy exactly [math]\displaystyle{ k }[/math] (respectively, at least [math]\displaystyle{ k }[/math]) of the properties. Let [math]\displaystyle{ A_i }[/math] denote the set of objects that satisfy [math]\displaystyle{ P_i }[/math] in [math]\displaystyle{ U }[/math], for any [math]\displaystyle{ I\subseteq\{1,...,n\} }[/math], we denote [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math] with the convention that [math]\displaystyle{ A_\emptyset=U }[/math]. Show that

• [math]\displaystyle{ f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i }[/math]

• [math]\displaystyle{ f_{\geq k}=\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}g_i. }[/math]

where [math]\displaystyle{ g_i=\sum_{I\subseteq\{1,...,n\},|I|=i }|A_I|. }[/math]

Problem 4

For any [math]\displaystyle{ k }[/math]-size subset [math]\displaystyle{ A }[/math] of vertices set [math]\displaystyle{ \{1,2,\dots,n\} }[/math], there are [math]\displaystyle{ T_{n,k} }[/math] forests on the [math]\displaystyle{ n }[/math] vertices with exactly [math]\displaystyle{ k }[/math] connected components that each element of [math]\displaystyle{ A }[/math] is in a different component.

• Prove [math]\displaystyle{ T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,k+i-1} }[/math].
• Prove [math]\displaystyle{ T_{n,k}=k\cdot n^{n-k-1} }[/math].