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

Under constructed

• 每道题目的解答都要有完整的解题过程。中英文不限。

Problem 1

Suppose that there are [math]\displaystyle{ n }[/math] red balls and another [math]\displaystyle{ m }[/math] balls which are distinct and not red. Balls with the same color are indistinguishable. Determine 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

Find the generating function for the sequence [math]\displaystyle{ (a_n) }[/math] in each of the following cases: [math]\displaystyle{ a_n }[/math] is the number of ways of distributing [math]\displaystyle{ n }[/math] identical objects into:

1. 4 distinct boxes;
2. 4 distinct boxes so that no box is empty;
3. 4 identical boxes;
4. 4 identical boxes so that no box is empty.

Problem 4

Let [math]\displaystyle{ (a_n) }[/math] be a sequence of numbers satisfying the recurrence relation: [math]\displaystyle{ a_n=p a_{n-1}-(p-q)q a_{n-2} }[/math] with [math]\displaystyle{ a_0= }[/math] and [math]\displaystyle{ a_1= }[/math], where <math>p<\math> and <math>q<\math> are distinct nonzero constants. Solve the recurrence relation.

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 S differing by 1. Give a bijective proof that <math>f(n,r,s)=\binom{n-r}{s}\binom{n-s}{r}<\math>.