组合数学 (Fall 2015)/Problem Set 2: Difference between revisions
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].