组合数学 (Spring 2013)/Problem Set 1: Difference between revisions
imported>Etone (Created page with "<font color="red" size=5>每道题目的解答都要有完整的解题过程。中英文不限。</font> == Problem 1 == #有<math>k</math>种不同的明信片，每种明信…") |
imported>Etone No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 9: | Line 9: | ||
== Problem 2 == | == Problem 2 == | ||
Find the number of ways to select <math>2n</math> balls from <math>n</math> identical blue balls, <math>n</math> identical red balls and <math>n</math> identical green balls. | |||
==Problem 3== | |||
=Problem 3= | |||
A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation. | A <math>2\times n</math> rectangle is to be paved with <math>1\times 2</math> identical blocks and <math>2\times 2</math> identical blocks. Let <math>f(n)</math> denote the number of ways that can be done. Find a recurrence relation for <math>f(n)</math>, solve the recurrence relation. | ||
=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>. | ||
Latest revision as of 11:47, 20 March 2013
每道题目的解答都要有完整的解题过程。中英文不限。
Problem 1
- 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，有多少种方法？
- 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人一张，每个人必须收到不同种类的明信片，有多少种方法？
- 有[math]\displaystyle{ k }[/math]种不同的明信片，每种明信片有无限多张，寄给[math]\displaystyle{ n }[/math]个人，每人收到[math]\displaystyle{ r }[/math]张不同的明信片（但不同的人可以收到相同的明信片），有多少种方法？
- 只有一种明信片，共有[math]\displaystyle{ m }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
- 有[math]\displaystyle{ k }[/math]种不同的明信片，其中第[math]\displaystyle{ i }[/math]种明信片有[math]\displaystyle{ m_i }[/math]张，寄给[math]\displaystyle{ n }[/math]个人，全部寄完，每个人可以收多张明信片或者不收明信片，有多少种方法？
Problem 2
Find the number of ways to select [math]\displaystyle{ 2n }[/math] balls from [math]\displaystyle{ n }[/math] identical blue balls, [math]\displaystyle{ n }[/math] identical red balls and [math]\displaystyle{ n }[/math] identical green balls.
Problem 3
A [math]\displaystyle{ 2\times n }[/math] rectangle is to be paved with [math]\displaystyle{ 1\times 2 }[/math] identical blocks and [math]\displaystyle{ 2\times 2 }[/math] identical blocks. Let [math]\displaystyle{ f(n) }[/math] denote the number of ways that can be done. Find a recurrence relation for [math]\displaystyle{ f(n) }[/math], solve the recurrence relation.
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].