组合数学 (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 2

Give a combinatorial proof to show that, for [math]\displaystyle{ 0 \leq k \leq n }[/math],

[math]\displaystyle{ \binom{n}{2} = \binom{k}{2} + k(n-k) + \binom{n-k}{2}. }[/math]

Hint: [math]\displaystyle{ \binom{n}{2} }[/math] is the number of edges in a complete graph on [math]\displaystyle{ n }[/math] vertices.

Problem 3

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

Hint: Count the number of ways to choose a subset of size [math]\displaystyle{ 2x+1 }[/math] from [math]\displaystyle{ \{0,1,2,\dots,n\} }[/math] by considering the middle element of the subset.

Problem 4

Let [math]\displaystyle{ f(n,j,k) }[/math] represent the number of ways to decompose [math]\displaystyle{ n }[/math] into the sum of [math]\displaystyle{ k }[/math] non-negative numbers [math]\displaystyle{ n = a_1 + a_2 + \dots + a_k }[/math], such that each [math]\displaystyle{ a_i }[/math] is less than [math]\displaystyle{ j }[/math].

We have the following formula for [math]\displaystyle{ f(n,j,k) }[/math]:

[math]\displaystyle{ f(n,j,k) = \sum_{r+sj=n} (-1)^s \binom{k+r-1}{r}\binom{k}{s}, }[/math]

where the sum is taken over all pairs of [math]\displaystyle{ (r,s)\in \mathbb{N} }[/math].

• Provide a proof using generating functions.
• Provide a proof using the inclusion-exclusion principle.

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]. (Hint: The formula proven in Problem 3 might be useful.)

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