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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
Created page with "== 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> identic..."
 
imported>Etone
No edit summary
Line 1: Line 1:
== Problem 1 ==
== 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.
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 an algebraic proof for the problem.
* Give an algebraic proof for the problem.
== Problem 3==
李雷和韩梅梅竞选学生会主席,韩梅梅获得选票 <math>p</math> 张,李雷获得选票 <math>q</math> 张,<math>p>q</math>。我们将总共的 <math>p+q</math> 张选票一张一张的点数,有多少种选票的排序方式使得在整个点票过程中,韩梅梅的票数一直高于李雷的票数?等价地,假设选票均匀分布的随机排列,以多大概率在整个点票过程中,韩梅梅的票数一直高于李雷的票数。
==Problem 4==
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 5 ==
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>
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.

Revision as of 13:04, 17 September 2017

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.

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

Problem 3

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

Problem 4

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 5

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.