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

From TCS Wiki
Jump to navigation Jump to search
Gispzjz (talk | contribs)
Gispzjz (talk | contribs)
Line 1: Line 1:
== Problem 1 ==
== Problem 1 ==
Let <math>D_n</math> denote the number of derangements of <math>\{1,2,\ldots,n\}</math>.
* Give a ''' combinatorial''' proof that <math>D(n)=nD(n-1)+(-1)^n</math>.
* For a permutation <math>p_1,p_2,...,p_n</math>, for <math>1\leq i<n</math>, we call position<math>i</math> ascent if <math>p_i<p_{i+1}</math>. Let <math>\mathcal{E}_n</math> denote the set of permutations whose first ascent is in an even position (where we always count <math>n</math> as an ascent). For instance, <math>\mathcal{E}(3)=\{213, 312\}</math> and <math>\mathcal{E}(4)=\{2134, 2143, 3124, 3142, 3241, 4123, 4132, 4231, 4321\}</math>. Set <math>E(n)=|\mathcal{E}(n)|</math>. Show that <math>E(n)=nE(n-1)+(-1)^n</math>. Hence (since <math>E(1)=D(1)=0</math>) we have <math>E(n)=D(n)</math>.
* Give a bijection between the permutations being counted by <math>E(n)</math> and the derangements of <math>[n]</math>.


== Problem 2 ==
== Problem 2 ==

Revision as of 13:08, 13 April 2023

Problem 1

Problem 2

Problem 3

Let [math]\displaystyle{ S=\{P_1,...,P_n\} }[/math] be a set of properties, and let [math]\displaystyle{ f_k }[/math] (respectively, [math]\displaystyle{ f_{\geq k} }[/math]) denote the number of objects in a finite set [math]\displaystyle{ U }[/math] that satisfy exactly [math]\displaystyle{ k }[/math] (respectively, at least [math]\displaystyle{ k }[/math]) of the properties. Let [math]\displaystyle{ A_i }[/math] denote the set of objects that satisfy [math]\displaystyle{ P_i }[/math] in [math]\displaystyle{ U }[/math], for any [math]\displaystyle{ I\subseteq\{1,...,n\} }[/math], we denote [math]\displaystyle{ A_I=\bigcap_{i\in I}A_i }[/math] with the convention that [math]\displaystyle{ A_\emptyset=U }[/math]. Show that

  • [math]\displaystyle{ f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i }[/math]
  • [math]\displaystyle{ f_{\geq k}=\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}g_i. }[/math]

where [math]\displaystyle{ g_i=\sum_{I\subseteq\{1,...,n\},|I|=i }|A_I|. }[/math]

Problem 4

For any [math]\displaystyle{ k }[/math]-size subset [math]\displaystyle{ A }[/math] of vertices set [math]\displaystyle{ \{1,2,\dots,n\} }[/math], there are [math]\displaystyle{ T_{n,k} }[/math] forests on the [math]\displaystyle{ n }[/math] vertices with exactly [math]\displaystyle{ k }[/math] connected components that each element of [math]\displaystyle{ A }[/math] is in a different component.

  • Prove [math]\displaystyle{ T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,k+i-1} }[/math].
  • Prove [math]\displaystyle{ T_{n,k}=k\cdot n^{n-k-1} }[/math].