组合数学 (Spring 2025)/Problem Set 1

Problem 1

Fix positive integers [math]\displaystyle{ n }[/math] and [math]\displaystyle{ k }[/math]. Let [math]\displaystyle{ S }[/math] be a set with [math]\displaystyle{ |S|=n }[/math]. Find the numbers of [math]\displaystyle{ k }[/math]-tuples [math]\displaystyle{ (T_1,T_2,\dots,T_k) }[/math] of subsets [math]\displaystyle{ T_i }[/math] of [math]\displaystyle{ S }[/math] subject to each of the following conditions separately. Briefly explain your answer.

• [math]\displaystyle{ T_1\subseteq T_2\subseteq \cdots \subseteq T_k. }[/math]
• The [math]\displaystyle{ T_i }[/math]s are pairwise disjoint.
• [math]\displaystyle{ T_1\cup T_2\cup \cdots T_k=S }[/math].

Problem 3

Fix [math]\displaystyle{ n, j, k }[/math]. How many integer sequences are there of the form [math]\displaystyle{ 1\leq a_1\lt a_2\lt \dots\lt a_k\leq n }[/math], where [math]\displaystyle{ a_{i+1} - a_i \geq j }[/math] for all [math]\displaystyle{ 1\leq i\leq k-1 }[/math]?

Problem 4

Fix [math]\displaystyle{ n, x }[/math], show combinatorially that [math]\displaystyle{ \sum_{m=0}^{n} \binom{m}{x}\binom{n-m}{x} = \binom{n+1}{2x+1}. \lt strong\gt Hint:\lt /strong\gt Count the number of ways to choose a subset of size \lt math\gt 2x+1 }[/math] from [math]\displaystyle{ \{0,1,2,\dots,n\} }[/math] by considering the middle element of the subset. For each possible middle element [math]\displaystyle{ m }[/math], how many ways can you choose [math]\displaystyle{ x }[/math] elements from [math]\displaystyle{ \{0,1,\dots,m-1\} }[/math] and [math]\displaystyle{ x }[/math] elements from [math]\displaystyle{ \{m+1,m+2,\dots,n\} }[/math]? </math>

Problem 5

For any integer [math]\displaystyle{ n\geq 1 }[/math], let [math]\displaystyle{ F_n }[/math] denote the [math]\displaystyle{ n }[/math]-th Fibonacci number.

• Show that [math]\displaystyle{ F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k} }[/math].

• Show that the number of ordered pairs [math]\displaystyle{ (S,T) }[/math] of subsets of [math]\displaystyle{ [n] }[/math] satisfying [math]\displaystyle{ s \gt |T| }[/math] for all [math]\displaystyle{ s \in S }[/math] and [math]\displaystyle{ t \gt |S| }[/math] for all [math]\displaystyle{ t \in T }[/math] is equal to [math]\displaystyle{ F_{2n+2} }[/math].

Problem 6

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=10 }[/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].