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

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
*每道题目的解答都要有<font color="red" size=5>完整的解题过程</font>。中英文不限。
*9月25日上课时交给老师,或者将电子版发给助教(email: ichenhm@gmail.com)。


== Problem 1 ==
== Problem 1 ==
Line 30: Line 31:
== Problem 6 ==
== Problem 6 ==
Let <math>f(n,r,s)</math> denote the number of subsets <math>S</math> of <math>[2n]</math> consisting of <math>r</math> odd and <math>s</math> even integers, with no two elements of <math>S</math> differing by <math>1</math>. Give a combinatorial proof that <math>f(n,r,s)=\binom{n-r}{s}\binom{n-s}{r}</math>.
Let <math>f(n,r,s)</math> denote the number of subsets <math>S</math> of <math>[2n]</math> consisting of <math>r</math> odd and <math>s</math> even integers, with no two elements of <math>S</math> differing by <math>1</math>. Give a combinatorial proof that <math>f(n,r,s)=\binom{n-r}{s}\binom{n-s}{r}</math>.
*'''Hint''': Note that <math>\left({{n-r-s+1}\choose s}\right)=\binom{n-r}{s}</math> and <math>\left({{n-r-s+1}\choose r}\right)=\binom{n-s}{r}</math>.

Latest revision as of 09:55, 18 September 2019

  • 每道题目的解答都要有完整的解题过程。中英文不限。
  • 9月25日上课时交给老师,或者将电子版发给助教(email: ichenhm@gmail.com)。

Problem 1

Suppose that we have [math]\displaystyle{ n }[/math] identical red balls and [math]\displaystyle{ m }[/math] distinct blue balls. Find the number of ways to select [math]\displaystyle{ r }[/math] balls from these [math]\displaystyle{ n+m }[/math] balls, in each of the following cases:

  1. [math]\displaystyle{ r\leq m,\ r\leq n }[/math];
  2. [math]\displaystyle{ n\leq r\leq m }[/math];
  3. [math]\displaystyle{ m\leq r\leq n }[/math].

Problem 2

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

Problem 3

In each of the following cases, first answer what the [math]\displaystyle{ a_n }[/math]'s are, and then try to give the closed forms for the generating functions [math]\displaystyle{ A(x)=\sum_{n\ge 0}a_n x^n }[/math].

  1. [math]\displaystyle{ a_n }[/math] is the number of ways of distributing [math]\displaystyle{ n }[/math] identical objects into 4 distinct boxes;
  2. [math]\displaystyle{ a_n }[/math] is the number of ways of distributing [math]\displaystyle{ n }[/math] identical objects into 4 distinct boxes so that no box is empty;
  3. [math]\displaystyle{ a_n }[/math] is the number of ways of distributing [math]\displaystyle{ n }[/math] identical objects into 4 identical boxes so that no box is empty;
  4. [math]\displaystyle{ a_n }[/math] is the number of ways of distributing [math]\displaystyle{ n }[/math] identical objects into 4 identical boxes.

Problem 4

Let [math]\displaystyle{ (a_n) }[/math] be a sequence of numbers satisfying the recurrence relation:

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

with initial condition [math]\displaystyle{ a_0=1 }[/math] and [math]\displaystyle{ a_1=p }[/math], where [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] are distinct nonzero constants. Solve the recurrence relation.

Problem 5

Consider the decimal expansion [math]\displaystyle{ 1/9899=0.0001010203050813213455\cdots }[/math]

Why do the Fibonacci numbers 1,1,2,3,5,8,13,21,34,55 appear?

Problem 6

Let [math]\displaystyle{ f(n,r,s) }[/math] denote the number of subsets [math]\displaystyle{ S }[/math] of [math]\displaystyle{ [2n] }[/math] consisting of [math]\displaystyle{ r }[/math] odd and [math]\displaystyle{ s }[/math] even integers, with no two elements of [math]\displaystyle{ S }[/math] differing by [math]\displaystyle{ 1 }[/math]. Give a combinatorial proof that [math]\displaystyle{ f(n,r,s)=\binom{n-r}{s}\binom{n-s}{r} }[/math].

  • Hint: Note that [math]\displaystyle{ \left({{n-r-s+1}\choose s}\right)=\binom{n-r}{s} }[/math] and [math]\displaystyle{ \left({{n-r-s+1}\choose r}\right)=\binom{n-s}{r} }[/math].