组合数学_学习笔记(二)

Combinatorial Mathematics
(TsinghuaX: 60240013x)

Linear Homogeneous Recurrence Relation

Fibonacci Rabbits

Fibonacci number
Fibonacci prime

Area of the rectangle = Sum of multiple quadrates

Expressions of Fibonacci Numbers

Linear Homogeneous Recurrence Relation

Def If sequence {an} satisifies:

C1,C2,…,Ck and d0,d1,…,dk−1 are constants, Ck≠0, so this expression is called a kth-order linear homogeneous recurrence relation of {an}.
Fibonacci Recurrence
Characteristic Polynomial
Characteristic polynomial has k
1. distinct real roots
2. Characteristic polynomial C(x) has multiple roots
3. Characteristic polynomial C(x) has conjugate complex roots
Summary

Applications

• There’s a point P on the plane. It’s the cross of n fields D1,D2,…Dn. Color these n fields with k colors. We require the color of two adjacent areas to be different.
  Calculate the number of arrangements.

  Let an be the number of arrangement to color these areas. There are 2 situations:

  1. D1 and Dn−1 have the same color
     Dn has k−1 choices, which is all colors except the one used by D1 and Dn−1;
     the arrangements for Dn−2 to D1 are one-to-one correspondent to the arrangements for n−2 areas.
     
     (k−1)an−2
  2. D1 and Dn−1 have different colors.
     Dn has k−2 choices; the arrangements from D1 to Dn−1 are one-to-one correspondent to the arrangements for n−1 areas.
     
     (k−2)an−1
     

  ∴an=(k−2)an−1+(k−1)an−2,a2=k(k−1),a3=k(k−1)(k−2).
  a1=0,a0=k
  x2−(k−2)x−(k−1)=0
  x1=k−1,x2=−1.
  an=A(k−1)n+B(−1)n
  

  {A+B=k,(k−1)A−B=0.
  {A=1,B=k−1.
  
  ∴an=(k−1)n+(k−1)(−1)n,n≥2.
  a1=k.

Magical Sequences

Catalan Numbers

• One stack (of infinite size) has the “push” sequence: 1,2,3,...n. How many ways can the numbers be popped out?

  Partition the n sequences into two sub-sequences.
  f(n)=f(k−1)∗f(n−k)

• Binary Tree
  How many different shapes can a binary tree with n nodes have?

  The root will obviously contain one node.
  Assume T(i,j) stands the left subtree of the root containing I nodes, and right subtree with j nodes.
  Not counting the root, there are n−1 nodes that could be structured as:

C(n)=C(0)∗C(n−1)+C(1)∗C(n−2)+⋯+C(n−2)∗C(1)+C(n−1)∗C(0)
C(n)=∑n−1i=0CiCn−i−1

Actually,

Proof using generating functions,

Dyck Language
Hands across the table

Exponential Generating Functions

Binomial Theorem
(1+x)n=∑∞k=0C(n,k)xk=∑∞k=0C(n,k)k!k!xk=∑∞k=0P(n,k)xkk!

• 3a1,2a2,3a3
  How many combinations of length 4?
  Key: 70
  Hint: 4!(43!+32!2!+32!)=70

For a seq a0,a,a2⋯, construct:

G(x) is known as the exponential generating function of a0,a1,a2,…

• Using the digits 1, 2, 3 and 4, construct a five digit number where 1 doesn’t appear more than 2 times, but has to appear at least once; 2 can’t appear more than once; 3 can appear up to 3 times but can also not appear in the number; 4 can only appear an even number of times. How many numbers can satisfy these conditions?

  Hint:
  An r digit number that satisfies the condition is ar; the exponential generating function for the seq a0,a1,…,a10 is:
  

  There are 215 5-digit numbers that satisfy the conditions.

• With digits 1,3,5,7,9, how many n-digit numbers are there, where 3 and 7 appear an even number of times, and 1,5,9 don’t have any conditions.

  Hint:
  Assume an r-digit number that satisfies the conditions is ar. Then, the exponential generating function of the seq of a1,a2,...,a3 is:

  

Derangements

之前浅显的学习笔记
A derangement is a permutation of the elements of a set such that none of the elements appear in their original position.

Suppose the derangement of n elements in a sequence 1,2,…n is Dn, for every ith number, it has to switch with the other n−1 numbers, followed by a derangement of the other n−2 elements. We will have a total of (n−1)Dn−2 number of derangements.
For the other part, not considering the number i, there is a derangement of the other n−1 elements to be done, followed by switching i with the other numbers yielding a total of (n−1)Dn−1 number of derangements.
D(n)=(n−1)(Dn−1+Dn−2),D0=0,D2=1
∴Dn=1

Stirling Numbers

Stirling numbers of the first kind

n people group dancing, divided into m disjoint circular groups.
s(n,0)=0,s(1,1)=1
s(n+1,m)=s(n,m−1)+n∗s(n,m)

• The n+1st person can dance alone, and the others form m−1 groups.
• The n+1st person joins a group, and will have n choices for groups, while the other n people have s(n,m) ways of forming groups.

Stirling numbers of the second kind

Definition: The number of ways n non-identical balls in m identical boxes where none of the boxes are empty is known as the Stirling number of the second kind.

Theorem: Stirling number of the second kind S(n,m) has the following properties:

• S(n,0)=0
• S(n,1)=1
• S(n,2)=2n−1−1
  Proof:
  Assume there are n non-identical balls b1,b2,...,bn, from which we pick b1. Now for the other n−1 balls, there are two possibilities, either they can be in the same box as b1 or a box that doesn’t contain b1. But it can only satisfy one of these conditions, therefore there are 2n−1−1 ways of placing the balls.
• S(n,n)=1

Theorem: Stirling number of the second kind satisfies the following recurrence relation.
S(n,m)=m∗S(n−1,m)+S(n−1,m−1)(n>1,m≥1).

Proof: Suppose there are n non-identical balls b1,b2,…,bn, from which we pick a ball b1.
Placing n balls into m boxes where no box is empty can be classified into two possibilities.
1. b1 is placed on its own in a box, therefore, the count is S(n−1,m−1)
2. b1 is not the only ball in its box. This is equivalent to placing n−1 balls in m boxes, where no box is empty. This yields the count S(n−1,m). Out of these boxes, b1 can be placed in any of these m boxes, so the total number of ways in this possibility equals to m∗S(n−1,m).

A generating function is a clothesline on which we hang up a sequence of numbers.
— — Herbert Wilf

Summary of placing balls into boxes problem