组合数学 (Spring 2026)/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

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 3

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 4

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 2 might be useful.)

Problem 5

There are [math]\displaystyle{ n }[/math] positions labeled [math]\displaystyle{ 1,2,\dots,n }[/math]. For each position [math]\displaystyle{ i }[/math], you may either leave it empty or fill it with a positive integer not exceeding [math]\displaystyle{ i }[/math]. Count the number of ways to fill exactly [math]\displaystyle{ k }[/math] positions such that all chosen integers are distinct. Prove your answer by establishing a bijection.