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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "==Problem 4== Let <math>\pi</math> be a permutation of <math>[n]</math>. Recall that a cycle of permutation <math>\pi</math> of length <math>k</math> is a tuple <math>(a_1,a_2..."
 
imported>Etone
No edit summary
Line 1: Line 1:
== Problem 1==
Prove the following identity:
*<math>\sum_{k=1}^n k{n\choose k}= n2^{n-1}</math>.
(Hint: Use double counting.)
==Problem 4==
==Problem 4==
Let <math>\pi</math> be a permutation of <math>[n]</math>.
Let <math>\pi</math> be a permutation of <math>[n]</math>.
Recall that a cycle of permutation <math>\pi</math> of length <math>k</math> is a tuple <math>(a_1,a_2,\ldots,a_k)</math> such that <math>a_2=\pi(a_1), a_3=\pi(a_2),\ldots,a_k=\pi(a_{k-1})</math> and <math>a_1=\pi(a_k)\,</math>. Thus a fixed point of <math>\pi</math> is just a cycle of length 1.
Recall that a cycle of permutation <math>\pi</math> of length <math>k</math> is a tuple <math>(a_1,a_2,\ldots,a_k)</math> such that <math>a_2=\pi(a_1), a_3=\pi(a_2),\ldots,a_k=\pi(a_{k-1})</math> and <math>a_1=\pi(a_k)\,</math>. Thus a fixed point of <math>\pi</math> is just a cycle of length 1.
* Fix <math>k\ge 1</math>. Let <math>f_k(n)</math> be the number of permutations of <math>[n]</math> having no cycle of length <math>k</math>. Compute this <math>f_k(n)</math> and the limit <math>\lim_{n\rightarrow\infty}\frac{f_k(n)}{n!}</math>.
* Fix <math>k\ge 1</math>. Let <math>f_k(n)</math> be the number of permutations of <math>[n]</math> having no cycle of length <math>k</math>. Compute this <math>f_k(n)</math> and the limit <math>\lim_{n\rightarrow\infty}\frac{f_k(n)}{n!}</math>.

Revision as of 09:02, 2 November 2015

Problem 1

Prove the following identity:

  • [math]\displaystyle{ \sum_{k=1}^n k{n\choose k}= n2^{n-1} }[/math].

(Hint: Use double counting.)

Problem 4

Let [math]\displaystyle{ \pi }[/math] be a permutation of [math]\displaystyle{ [n] }[/math]. Recall that a cycle of permutation [math]\displaystyle{ \pi }[/math] of length [math]\displaystyle{ k }[/math] is a tuple [math]\displaystyle{ (a_1,a_2,\ldots,a_k) }[/math] such that [math]\displaystyle{ a_2=\pi(a_1), a_3=\pi(a_2),\ldots,a_k=\pi(a_{k-1}) }[/math] and [math]\displaystyle{ a_1=\pi(a_k)\, }[/math]. Thus a fixed point of [math]\displaystyle{ \pi }[/math] is just a cycle of length 1.

  • Fix [math]\displaystyle{ k\ge 1 }[/math]. Let [math]\displaystyle{ f_k(n) }[/math] be the number of permutations of [math]\displaystyle{ [n] }[/math] having no cycle of length [math]\displaystyle{ k }[/math]. Compute this [math]\displaystyle{ f_k(n) }[/math] and the limit [math]\displaystyle{ \lim_{n\rightarrow\infty}\frac{f_k(n)}{n!} }[/math].