| 민 ¶
Generating Function ¶
~cpp 3 n(2 배) . 2*1 를 . n 빈 는 모 를 .(Generating Function )
~cpp n 노 (막대는 A, B, C). A막대 는 C 는데 리는 를 ( A B만, B C만 동능. 노 는 만 는 .
Induction ¶
~cpp 마(i=1~n)i*(Hi) = n*(n+1)/2*(Hn) -(n-1)*n/4 명
Contradixtion ¶
~cpp
Generating Function ¶
From Concrete Mathematics, Chapter 7. Generating Function
1. (Warm up) An eccentric collector of 2 x n domino tilings pays $4 for each vertical domino and $1 for each horizontal domino. How many tiling are worth exactly $m by this criterion? For example, when m = 6 there are three solutions.
2. (Warmp up) What is Sigma( Hn / 10^n ) ( n >= 0 )?
3. (Basic)Solve the recurrence
From Discrete mathematics
5. Let us use a generating function to find a formula for s<sub>n</sub>, where s<sub>0</sub> = s<sub>1</sub> = 1, and s<sub>n</sub> = -s<sub>n-1</sub> + 6s<sub>n-2</sub> for n ≥ 2.
6~8 Give a generating fuction for the sequence {a<sub>n</sub>}.
6. Let a<sub>r</sub> be the number of ways to select r balls from 3 red balls, 2 green balls, and 5 white balls.
7. Let a<sub>r</sub> be the number of ways r cents worth of postage can be placed on a letter using only 5c, 12c, and 25c stamps. The positions of the stamps on the letter do not matter.
8. Let a<sub>r</sub> be the number of ways to pay for an item costing r cents with pennies, nickels, and dimes.
G(0) = 1
G(n) = G(n-1) + 2G(n-2) + 3G(n-3) + ... + nG(0), for n > 0
4. (Homework exercises) How many spanning trees are in an n-wheel( a graph with n "outer" verices in a cycle, each connected to an (n+1)st "hub" vertex), when n >= 3?
G(n) = G(n-1) + 2G(n-2) + 3G(n-3) + ... + nG(0), for n > 0
6. Let a<sub>r</sub> be the number of ways to select r balls from 3 red balls, 2 green balls, and 5 white balls.
Induction ¶
1. (i=1~k)i*2<sup> i-1 </sup> = 2<sup>k</sup> (k-1) + 1. Prove it.
Contradixtion ¶
~cpp
