组合数学 (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
Line 16: Line 16:
:<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>q+q+r=0</math>, <math>p\neq 0</math> and <math>s\neq t</math>. Solve the recurrence relation.
==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>.

Revision as of 09:41, 26 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 a 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{ q+q+r=0 }[/math], [math]\displaystyle{ p\neq 0 }[/math] and [math]\displaystyle{ s\neq t }[/math]. Solve the recurrence relation.

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