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

From TCS Wiki
Jump to navigation Jump to search
Roundgod (talk | contribs)
Roundgod (talk | contribs)
 
(13 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Problem 1 ==
== Problem 1 ==


Give <math>n,m,k</math>, find the number of '''integer''' solutions to the following equation: <math> a_1+a_2+...+a_n=m, \forall 1\leq i\leq n, 0\leq a_i<k</math>. You should give a formula and explain your answer.


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


Give <math>n,m,k</math>, find the number of '''integer''' solutions to the following equation: <math> a_1+a_2+...+a_n=m, \forall 1\leq i\leq n, 0\leq a_i<k</math>. You should give a formula and explain your answer.
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> an 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 3 ==
== Problem 3 ==


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


<math>f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i</math>
* <math>f_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}g_i</math>
and
<math>f_{\geq k}=\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}g_i.</math>
* <math>f_{\geq k}=\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{k-1}g_i.</math>


where  
where  
<math>g_i=\sum_{I\subseteq\{1,...,n\},|I|=i }|A_I|.</math>
<math>g_i=\sum_{I\subseteq\{1,...,n\},|I|=i }|A_I|.</math>
== Problem 4 ==
For any <math>k</math>-size subset <math>A</math> of vertices set <math>\{1,2,\dots,n\}</math>, there are <math>T_{n,k}</math> forests on the <math>n</math> vertices with exactly <math>k</math> connected components that each element of <math>A</math> is in a different component.
* Prove <math>T_{n,k}=\sum_{i=0}^{n-k}\binom{n-k}{i}T_{n-1,k+i-1}</math>.
* Prove <math>T_{n,k}=k\cdot n^{n-k-1}</math>.
== Problem 5 ==
Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads.  (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with <math> n=12 </math> and dihedral equivalence.
For example, with <math> n=6 </math> and dihedral equivalence, there are <math>8</math> distinct configurations: <math>000000,000001,000011,000101,001001,000111,001011,010101</math>.

Latest revision as of 13:27, 13 April 2023

Problem 1

Give [math]\displaystyle{ n,m,k }[/math], find the number of integer solutions to the following equation: [math]\displaystyle{ a_1+a_2+...+a_n=m, \forall 1\leq i\leq n, 0\leq a_i\lt k }[/math]. You should give a formula and explain your answer.

Problem 2

Let [math]\displaystyle{ D_n }[/math] denote the number of derangements of [math]\displaystyle{ \{1,2,\ldots,n\} }[/math].

  • Give a combinatorial proof that [math]\displaystyle{ D(n)=nD(n-1)+(-1)^n }[/math].
  • For a permutation [math]\displaystyle{ p_1,p_2,...,p_n }[/math], for [math]\displaystyle{ 1\leq i\lt n }[/math], we call position [math]\displaystyle{ i }[/math] an ascent if [math]\displaystyle{ p_i\lt p_{i+1} }[/math]. Let [math]\displaystyle{ \mathcal{E}_n }[/math] denote the set of permutations whose first ascent is in an even position (where we always count [math]\displaystyle{ n }[/math] as an ascent). For instance, [math]\displaystyle{ \mathcal{E}(3)=\{213, 312\} }[/math] and [math]\displaystyle{ \mathcal{E}(4)=\{2134, 2143, 3124, 3142, 3241, 4123, 4132, 4231, 4321\} }[/math]. Set [math]\displaystyle{ E(n)=|\mathcal{E}(n)| }[/math]. Show that [math]\displaystyle{ E(n)=nE(n-1)+(-1)^n }[/math]. Hence (since [math]\displaystyle{ E(1)=D(1)=0 }[/math]) we have [math]\displaystyle{ E(n)=D(n) }[/math].
  • Give a bijection between the permutations being counted by [math]\displaystyle{ E(n) }[/math] and the derangements of [math]\displaystyle{ [n] }[/math].

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

Problem 5

Identify necklaces of two types of colored beads with their duals obtained by switching the colors of the beads. (We can now distinguish between the two colors, but we can't tell which is which.) Count the number of dintinct configurations with [math]\displaystyle{ n=12 }[/math] and dihedral equivalence.

For example, with [math]\displaystyle{ n=6 }[/math] and dihedral equivalence, there are [math]\displaystyle{ 8 }[/math] distinct configurations: [math]\displaystyle{ 000000,000001,000011,000101,001001,000111,001011,010101 }[/math].