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

Problem 1

Let [math]\displaystyle{ 0\leq l\leq k\leq n }[/math]. Show that [math]\displaystyle{ \binom{n}{k}\binom{k}{l} = \binom{n}{l}\binom{n-l}{k-l} }[/math].

Problem 2

Prove the following claims related to Cayley's formula:

• The number of rooted labelled forests with [math]\displaystyle{ n }[/math] vertices is given by [math]\displaystyle{ (n+1)^{n-1} }[/math].

• The number of unrooted labelled forests with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ k }[/math] connected components such that [math]\displaystyle{ 1,\dots,k }[/math] belong to distinct components is given by [math]\displaystyle{ kn^{n-k-1} }[/math].

• The number of unrooted labelled trees with [math]\displaystyle{ n }[/math] vertices of degrees [math]\displaystyle{ d_1,d_2,\dots,d_n }[/math] respectively is given by [math]\displaystyle{ \binom{n-2}{d_1-1,d_2-1,\dots,d_n-1}=\frac{(n-2)!}{(d_1-1)!(d_2-1)!\cdots(d_n-1)!} }[/math].

Problem 3

There are [math]\displaystyle{ n }[/math] parking spaces [math]\displaystyle{ 1, 2,...,n }[/math] available for [math]\displaystyle{ n }[/math] drivers. Each driver has a favorite space, driver [math]\displaystyle{ i }[/math] space [math]\displaystyle{ f (i) }[/math], [math]\displaystyle{ 1 ≤ f (i) ≤ n }[/math]. The drivers arrive one by one. When driver [math]\displaystyle{ i }[/math] arrives he tries to park his car in space [math]\displaystyle{ f (i) }[/math]. If it is taken he moves down the line to take the first free space greater than [math]\displaystyle{ f (i) }[/math], if any. Example: [math]\displaystyle{ n = 4, f = 3221 }[/math]; then driver [math]\displaystyle{ 1 → 3, 2 → 2, 3 → 4, 4 → 1 }[/math], but for [math]\displaystyle{ f = 2332 }[/math] we have [math]\displaystyle{ 1 → 2, 2 → 3, 3 → 4, 2 →? }[/math]. Let [math]\displaystyle{ p(n) }[/math] be the number of sequences [math]\displaystyle{ f }[/math] that allow each driver to park his car; [math]\displaystyle{ f }[/math] is then called a parking sequence. Prove:

• [math]\displaystyle{ f }[/math] is a parking sequence if and only if [math]\displaystyle{ \#\{i : f (i) ≤ k\} ≥ k }[/math].
• [math]\displaystyle{ p(n) = (n + 1)^{n−1} }[/math]. This looks like the number of rooted labelled forests with [math]\displaystyle{ n }[/math] vertices. Can you find a bijection?

Problem 4

Solve the following two existence problems:

• You are given [math]\displaystyle{ n }[/math] integers [math]\displaystyle{ a_1,a_2,\dots,a_n }[/math], such that for each [math]\displaystyle{ 1\leq i\leq n }[/math] it holds that [math]\displaystyle{ i-n\leq a_i\leq i-1 }[/math]. Show that there exists a nonempty subsequence (not necessarily consecutive) of these integers, whose sum is equal to [math]\displaystyle{ 0 }[/math]. (Hint: Consider [math]\displaystyle{ b_i=a_i-i }[/math])

• You are given two multisets [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math], both with [math]\displaystyle{ n }[/math] integers from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ n }[/math]. Show that there exist two nonempty subsets [math]\displaystyle{ A'\subseteq A }[/math] and [math]\displaystyle{ B'\subseteq B }[/math] with equal sum, i.e. [math]\displaystyle{ \sum\limits_{x\in A'}x=\sum\limits_{y\in B'}y }[/math] (Hint: Replace the term multiset by sequence, the term subset by consecutive subsequence, and the statement is still true. )

Problem 5

Suppose [math]\displaystyle{ n \geq 4 }[/math], and let [math]\displaystyle{ H }[/math] be an [math]\displaystyle{ n }[/math]-uniform hypergraph with at most [math]\displaystyle{ \frac{4^{n−1}}{3^n} }[/math] (hyper)edges. Prove that there is a coloring of the vertices of [math]\displaystyle{ H }[/math] by four colors so that in every (hyper)edge all four colors are represented.

Problem 6

Let [math]\displaystyle{ D=(V,E) }[/math] be a simple directed graph with minimum outdegree [math]\displaystyle{ \delta }[/math] and maximum indegree [math]\displaystyle{ \Delta }[/math]. Prove:

For any positive integer [math]\displaystyle{ k }[/math], if [math]\displaystyle{ \mathrm{e}(\Delta \delta+1)(1-\frac{1}{k})^{\delta}\lt 1 }[/math], then [math]\displaystyle{ D }[/math] contains a (directed,simple) cycle of length [math]\displaystyle{ 0\pmod k. }[/math]

Hint: Let [math]\displaystyle{ f:V\rightarrow \{0,1,\dots,k-1\} }[/math] be a random coloring of [math]\displaystyle{ V }[/math] obtained by choosing uniformly and independently at random for each [math]\displaystyle{ v\in V }[/math]. Try to use Lovász Local Lemma to show something interesting!