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

From EtoneWiki
Jump to: navigation, search
  • 每道题目的解答都要有完整的解题过程。中英文不限。
  • 第四题有一处笔误。已改正,见红色字体。

Problem 1

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

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

Problem 2

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

Problem 3

A rectangle is to be paved with identical blocks and identical blocks. Let denote the number of ways that can be done. Find a recurrence relation for , solve the recurrence relation.

Problem 4

Let be a sequence of numbers satisfying the recurrence relation:

with initial condition and , where are constants such that , and . Solve the recurrence relation.

Problem 5

假设我们班上有n+2个人,其中两个人是DNA完全相同的双胞胎。我们收上n+2份作业后,将这些作业打乱后发回给全班同学,每人一份。要求每个人不可以收到自己那一份作业或者与自己DNA相同的人的作业。令表示满足这个要求的发回作业的方式,问:

  • 计算是多少;
  • 时,随机重排并发回作业后,满足上述要求的概率是多少。

Problem 6

Let be a permutation of . Recall that a cycle of permutation of length is a tuple such that and . Thus a fixed point of is just a cycle of length 1.

  • Fix . Let be the number of permutations of having no cycle of length . Compute this and the limit .

Bonus problem

Give a dynamical programming algorithm that given as input a bipartite graph where , returns the number of perfect matchings in within time .