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

Problem 1

Give [math]\displaystyle{ n,m,k }[/math], find the number of integer solutions to the following equation: [math]\displaystyle{ a_1+a_2+...+a_n=m, \forall 1\leq i\leq n, 0\leq a_i\lt k }[/math]. You should give a formula and explain your answer.

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] an 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].

Problem 5

Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with [math]\displaystyle{ n=12 }[/math] and dihedral equivalence.

For example, with [math]\displaystyle{ n=6 }[/math] and dihedral equivalence, there are [math]\displaystyle{ 8 }[/math] distinct configurations: [math]\displaystyle{ 000000,000001,000011,000101,001001,000111,001011,010101 }[/math].