组合数学 (Fall 2016)/Problem Set 1: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。 == Problem 1 == Find the number of ways to select <math>2n</math> bal..."
 
imported>Etone
No edit summary
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
*每道题目的解答都要有<font color="red" >完整的解题过程</font>。中英文不限。
 
*<font color="red" size=5>第四题有一处笔误。已改正,见红色字体。</font>


== Problem 1 ==
== Problem 1 ==
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.
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.
* Give a combinatorial proof for the problem.
* Give a combinatorial proof for the problem.
* Give a algebraic proof for the problem.  
* Give an algebraic proof for the problem.


== Problem 2==
== Problem 2==
Line 15: Line 17:
Let <math>a_n</math> be a sequence of numbers satisfying the recurrence relation:
Let <math>a_n</math> be a sequence of numbers satisfying the recurrence relation:
:<math>p a_n+q a_{n-1}+r a_{n-2}=0</math>
:<math>p a_n+q a_{n-1}+r a_{n-2}=0</math>
with initial condition <math>a_0=s</math> and <math>a_1=t</math>, where <math>p,q,r,s,t</math> are constants such that <math>q+q+r=0</math>, <math>p\neq 0</math> and <math>s\neq t</math>. Solve the recurrence relation.
with initial condition <math>a_0=s</math> and <math>a_1=t</math>, where <math>p,q,r,s,t</math> are constants such that <math>{\color{red}p}+q+r=0</math>, <math>p\neq 0</math> and <math>s\neq t</math>. Solve the recurrence relation.
 
== Problem 5==
假设我们班上有n+2个人,其中两个人是DNA完全相同的双胞胎。我们收上n+2份作业后,将这些作业打乱后发回给全班同学,每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令<math>T_n</math>表示满足这个要求的发回作业的方式,问:
* 计算<math>T_n</math>是多少;
* 在<math>n\to\infty</math>时,随机重排并发回作业后,满足上述要求的概率是多少。
 
==Problem 6==
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.
* 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>.
 
==Bonus problem ==
Give a '''dynamical programming''' algorithm that given as input a bipartite graph <math>G(U,V,E)</math> where <math>|U|=|V|=n</math>, returns the number of perfect matchings in <math>G</math> within time <math>n 2^{O(n)}</math>.

Latest revision as of 14:36, 27 September 2016

  • 每道题目的解答都要有完整的解题过程。中英文不限。
  • 第四题有一处笔误。已改正,见红色字体。

Problem 1

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.

  • Give a combinatorial proof for the problem.
  • Give an algebraic proof for the problem.

Problem 2

李雷和韩梅梅竞选学生会主席,韩梅梅获得选票 [math]\displaystyle{ p }[/math] 张,李雷获得选票 [math]\displaystyle{ q }[/math] 张,[math]\displaystyle{ p\gt q }[/math]。我们将总共的 [math]\displaystyle{ p+q }[/math] 张选票一张一张的点数,有多少种选票的排序方式使得在整个点票过程中,韩梅梅的票数一直高于李雷的票数?等价地,假设选票均匀分布的随机排列,以多大概率在整个点票过程中,韩梅梅的票数一直高于李雷的票数。

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{ a_n }[/math] be a sequence of numbers satisfying the recurrence relation:

[math]\displaystyle{ p a_n+q a_{n-1}+r a_{n-2}=0 }[/math]

with initial condition [math]\displaystyle{ a_0=s }[/math] and [math]\displaystyle{ a_1=t }[/math], where [math]\displaystyle{ p,q,r,s,t }[/math] are constants such that [math]\displaystyle{ {\color{red}p}+q+r=0 }[/math], [math]\displaystyle{ p\neq 0 }[/math] and [math]\displaystyle{ s\neq t }[/math]. Solve the recurrence relation.

Problem 5

假设我们班上有n+2个人,其中两个人是DNA完全相同的双胞胎。我们收上n+2份作业后,将这些作业打乱后发回给全班同学,每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令[math]\displaystyle{ T_n }[/math]表示满足这个要求的发回作业的方式,问:

  • 计算[math]\displaystyle{ T_n }[/math]是多少;
  • [math]\displaystyle{ n\to\infty }[/math]时,随机重排并发回作业后,满足上述要求的概率是多少。

Problem 6

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

Bonus problem

Give a dynamical programming algorithm that given as input a bipartite graph [math]\displaystyle{ G(U,V,E) }[/math] where [math]\displaystyle{ |U|=|V|=n }[/math], returns the number of perfect matchings in [math]\displaystyle{ G }[/math] within time [math]\displaystyle{ n 2^{O(n)} }[/math].