组合数学 (Fall 2023)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Roundgod (talk | contribs)
Roundgod (talk | contribs)
Line 1: Line 1:
== Problem 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 solution.
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>
* <math>T_1\subseteq T_2\subseteq \cdots \subseteq T_k.</math>
* The <math> T_i</math>s are pairwise disjoint.
* The <math> T_i</math>s are pairwise disjoint.

Revision as of 07:12, 16 March 2023

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

Let [math]\displaystyle{ p }[/math] be a prime and [math]\displaystyle{ a }[/math] be a positive integer. Show combinatorially that [math]\displaystyle{ a^p-a }[/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.