组合数学 (Fall 2019)/Problem Set 1

• 每道题目的解答都要有完整的解题过程。中英文不限。
• 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].