View source for 组合数学 (Fall 2023)/Problem Set 1

== Problem 1 ==

Fix positive integers <math>n</math> and <math>k</math>. Let <math>S</math> be a set with <math>|S|=n</math>. Find the number of <math>k</math>-tuples <math>(T_1,T_2,\dots,T_k)</math> of subsets <math>T_i</math> of <math>S</math> subject to each of the following conditions separately. Briefly explain your answer.
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* <math> T_1\cup T_2\cup \cdots T_k=S</math>.

== Problem 2 ==
Let <math>p</math> be a prime integer and <math>a</math> be a positive integer. Show '''combinatorially''' that <math>a^p-a</math> is divisible by <math>p</math>. (A combinatorial proof would consist of exhibiting a set <math>S</math> with <math>a^p-a</math> elements and a partition of <math>S</math> into pairwise disjoint subsets, each with <math>p</math> elements)

== Problem 3 ==

Fix <math>1\leq k\leq n</math>. How many integer sequences <math>1\leq a_1<a_2<\cdots<a_k\leq n</math> satisfy <math>a_i\equiv i\pmod 2</math> for all <math>i</math>? Prove your answer.

== Problem 4 ==

For any integer <math>n\geq 1</math>, let <math>F_n</math> denote the <math>n</math>-th Fibonacci number. 

* Show that <math>F_{n+1}=\sum\limits_{k=0}^{n}\binom{n-k}{k}</math>.

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

== Problem 5 ==

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

* Give a generating function poof.

* Give a bijective proof.