组合数学 (Fall 2023)/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 number 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 solution.

• [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

Let [math]\displaystyle{ p }[/math] be a prime and [math]\displaystyle{ a }[/math] be a positive integer. Show combinatorially that [math]\displaystyle{ a^p-p }[/math] is divisible by [math]\displaystyle{ p }[/math]. (A combinatorial proof would consist of exhibiting a set [math]\displaystyle{ S }[/math] with [math]\displaystyle{ a^p-a }[/math] elements and a partition of [math]\displaystyle{ S }[/math] into pairwise disjoint subsets, each with [math]\displaystyle{ p }[/math] elements)

Problem 3

Fix [math]\displaystyle{ 1\leq k\leq n }[/math]. How many integer sequences [math]\displaystyle{ 1\leq a_1\lt a_2\lt \cdots\lt a_k\leq n }[/math] satisfy [math]\displaystyle{ a_i\equiv i\pmod 2 }[/math] for all [math]\displaystyle{ i }[/math]? Prove your answer.

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

• Let [math]\displaystyle{ f(n) }[/math] be the number of ways to choose a subset [math]\displaystyle{ S\subseteq [n] }[/math]and a permutation [math]\displaystyle{ \pi\in P_n }[/math] such that [math]\displaystyle{ \pi(i)\notin S }[/math] whenever [math]\displaystyle{ i\in S }[/math]. Show that [math]\displaystyle{ f(n)=F_{n+1}n! }[/math].

Problem 5

Let [math]\displaystyle{ n-r=2k }[/math]. Show that the number [math]\displaystyle{ f(n,r,s) }[/math] of compositions of [math]\displaystyle{ n }[/math] with [math]\displaystyle{ r }[/math] odd parts and [math]\displaystyle{ s }[/math] even parts is given by [math]\displaystyle{ \binom{r+s}{r}\binom{r+k-1}{r+s-1} }[/math]:

• Give a generating function poof.

• Give a bijective proof.