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

From EtoneWiki
Jump to: navigation, search

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

Contents

Problem 1

  1. k种不同的明信片,每种明信片有无限多张,寄给n个人,每人一张,有多少种方法?
  2. k种不同的明信片,每种明信片有无限多张,寄给n个人,每人一张,每个人必须收到不同种类的明信片,有多少种方法?
  3. k种不同的明信片,每种明信片有无限多张,寄给n个人,每人收到r张不同的明信片(但不同的人可以收到相同的明信片),有多少种方法?
  4. 只有一种明信片,共有m张,寄给n个人,全部寄完,每个人可以收多张明信片或者不收明信片,有多少种方法?
  5. k种不同的明信片,其中第i种明信片有mi张,寄给n个人,全部寄完,每个人可以收多张明信片或者不收明信片,有多少种方法?

Problem 2

Find the number of ways to select 2n balls from n identical blue balls, n identical red balls and n identical green balls.

Problem 3

  • Give a combinatorial proof for the following identity:

\sum_{k=1}^n k{n\choose k}=n\cdot 2^{n-1}.
  • Give a closed form for \sum_{k=1}^n k^2{n\choose k} and prove it.

Problem 4

  • 一个长度为n的“山峦”是如下由n个"/"和n个"\"组成的,从坐标(0,0)(0,2n)的折线,但任何时候都不允许低于x轴。例如下图:
   /\
  /  \/\/\    /\/\
 /        \/\/    \/\/\
 ----------------------
长度为n的“山峦”有多少?
  • 一个长度为n的“地貌”是由n个"/"和n个"\"组成的,从坐标(0,0)(0,2n)的折线,允许低于x轴。长度为n的“地貌”有多少?

Problem 5

A 2\times n rectangle is to be paved with 1\times 2 identical blocks and 2\times 2 identical blocks. Let f(n) denote the number of ways that can be done. Find a recurrence relation for f(n), solve the recurrence relation.

Problem 6

  • sn表示长度为n,没有2个连续的1的二进制串的数量,即
    s_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-1, x_ix_{i+1}\neq 11\}|
sn
  • tn表示长度为n,没有3个连续的1的二进制串的数量,即
    t_n=|\{x\in\{0,1\}^n\mid \forall 1\le i\le n-2, x_ix_{i+1}x_{i+2}\neq 111\}|
    1. 给出计算tn的递归式,并给出足够的初始值。
    2. 计算tn的生成函数T(x)=\sum_{n\ge 0}t_n x^n,给出生成函数T(x)的闭合形式。

注意:只需解生成函数的闭合形式,无需展开。

Problem 7

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

Personal tools