-Enumerative Combinatorics - July 31, 2006
CONTENTS
CONTENTS e
1. A. B. C. D.
2. a, b, c (ab)c a(bc)
(ab)c a(bc)
a, b, c, d ((ab)c)d (a(bc))d a((bc)d) a(b(cd)) (ab)(cd)
3. (Catalan number) C n = n C 1 = 1, C 2 = 1, C 3 = 2, C 4 = 5, C 5 = 14, C 6 = 42, C 7 = 132, C 8 = 429...
Eugène Charles Catalan (1814-1894)
4. * (ab)c = ab c a(bc) = abc (ab)(cd) = ab cd
(ab)c = ab c a b c a(bc) = abc a b c (ab)(cd) = ab cd a b c d
5. ab c d abc d ab cd abc d abcd ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd)) b, c, d, e,...
C n n C 4 = 5
(((ab)c)d)e ((a(bc))d)e ((ab)(cd))e (a((bc)d))e (a(b(cd)))e ((ab)c)(de) (a(bc))(de) ab c d e abc d e ab cd e abc d abcd e ab c de abc de ab cd e abc d e abcd e ab cde abc de abcd e abcde (ab)((cd)e) a(((bc)d)e) a((b(cd))e) (ab)(c(de)) a((bc)(de)) a(b((cd)e)) a(b(c(de))) C 5 = 14
6. ab cd ab c d abcd abc d abc d (ab)(cd) (a(bc))d (a(b(cd)) a((bc)d) (a(bc))d
6. ab cd ab c d abcd abc d abc d (ab)(cd) (a(bc))d (a(b(cd)) a((bc)d) (a(bc))d
C n (n + 1) C 4 = 5
7. C 1 = 1, C 2 = 1, C 3 = 2, C 4 = 5, C 5 = 14, C 6 = 42, C 7 = 132, C 8 = 429... C 1 = 1, C 2 = 1, C 2 = 1, C 1 = 1, 1 1 + 1 1 = 2 = C 3
C 1 = 1, C 2 = 1, C 3 = 2, C 3 = 2, C 2 = 1, C 1 = 1, 1 2 + 1 1 + 2 1 = 5 = C 4 C 1 = 1, C 2 = 1, C 3 = 2, C 4 = 5, C 4 = 5, C 3 = 2, C 2 = 1, C 1 = 1, 1 5 + 1 2 + 2 1 + 5 1 = 14 = C 5 C 1 = 1, C 2 = 1, C 3 = 2, C 4 = 5, C 5 = 14, C 5 = 14, C 4 = 5, C 3 = 2, C 2 = 1, C 1 = 1, 1 14+1 5+2 2+5 1+14 1 = 42 = C 6
C 4 C 1 C 3 C 2 C 2 C 3 C 4 C 1 C 5 = C 4 C 1 + C 3 C 2 + C 2 C 3 + C 1 C 4
8.
x 2 + 5x + 3 x 1 + 2x + 3x 2 + 4x 3 +......
y = C 1 x + C 2 x 2 + C 3 x 3 +... = x + x 2 + 2x 3 + 5x 4 + 14x 5 + 42x 6 +... x n x n C n
y 2 = (x + x 2 + 2x 3 + 5x 4 + 14x 5 + 42x 6 +...) (x + x 2 + 2x 3 + 5x 4 + 14x 5 + 42x 6 +...) = x 2 + (1 1 + 1 1)x 3 + (1 2 + 1 1 + 2 1)x 4 +(1 5 + 1 2 + 2 1 + 5 1)x 5 +... = x 2 + 2x 3 + 5x 4 + 14x 5 + 42x 6 +... = y x y 2 y + x = 0 y
1 ± 1 4x 2 y = 1 1 4x 2 C 1 = 1, C 2 = 1, C 3 = 2, C 4 = 5, C 5 = 14, C 6 = 42, C 7 = 132, C 8 = 429...
a n a 0 + a 1 x + a 2 x 2 +... C n a + bn ar n 1 1 4x 2 a 1 x + a 1 rx bx (1 x) 2 1 n! n! 1 n ex mc n (1 + x) m
9. (1 + x) 2 = 1 + 2x + x 2 (1 + x) 3 = 1 + 3x + 3x 2 + x 3 (1 + x) 4 = 1 + 4x + 6x 2 + 4x 3 + x 4 (1 + x) 5 = 1 + 5x + 10x 2 + 10x 3 + 5x 4 + x 5 (1 + x) 6 = 1 + 6x + 15x 2 + 20x 3 + 15x 4 + 6x 5 + x 6
(1 + x) m = m C 0 + m C 1 x + m C 2 x 2 + m C 3 x 3 + m C 4 x 4 +... m C n m n mc n = m! (n!)(m n)! 5C 2 = 5! (2!)(5 2)! = 5 4 3 2 1 (2 1)(3 2 1) = 120 2 6 = 10
1 1 4x 2 m 1 4x = (1 4x) 1/2 (1 4x) 1/2 = 1 2x 2x 2 4x 3 10x 4 28x 5... = 1 ( 2 C 1 ) x 1 3 ( 4C 2 ) x 2 1 5 ( 6C 3 ) x 3 1 7 ( 8C 4 ) x 4...
C n = 1 n (2n 2C n 1 ) C 4 = 1 4 ( 6C 3 ) = 1 4 6 5 4 3 2 1 (3 2 1)(3 2 1) = 20 4 = 5
10. 0. 3 = 0.3333333333333333333333333333333333333333... π = 3.1415926535897932384626433832795028841971...
1 rx a 0. 9 = 0.9999999999999999999999999999999999999999... = 9 10 + 9 100 + 9 1000 + 9 10000 + 9 100000 + 9 1000000 9 + 10000000 + 9 100000000 +... 9 = 10 1 10 1 = 1 (0. 9 = 1) a = 1, r = 1, x = 1 1 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 + 1 1 +... = 1 + ( 1) + ( 1) 2 + ( 1) 3 + ( 1) 4 +... = 1 2
1 + 2 + 3 + 4 + 5 +... = 1 12
11. n! 1 ex e x = 1 + x 1! + x2 2! + x3 3! + x4 4! +... x = 1 e 1 = 1 + 1 1! + 1 2! + 1 3! + 1 4! +... π
e = 2.7182818284590... e = 2. 71828182845904523536028747135266249775724709369995 95749669676277240766303535475945713821785251664274 27466391932003059921817413596629043572900334295260 59563073813232862794349076323382988075319525101901 15738341879307021540891499348841675092447614606680 82264800168477411853742345442437107539077744992069 55170276183860626133138458300075204493382656029760 67371132007093287091274437470472306969772093101416...
12. e πi + 1 = 0 i = 1, i 2 = 1 π e i 0
e πi = 1 e x 1 n! 1 = 1 + πi 1! + (πi)2 + (πi)3 + (πi)4 +... ( 2! ) 3! ( 4! = 1 π2 2! + π4 π 4!... + i 1! π3 3!... )
13.
1 2 (AbBa) 2 6 = 3 6 1 6 (AbBcCa, AcBaCb) 24 9 = 24 12 24 4 + 24 1 ( AbBcCdDa, AbBdCaDc, AcBaCdDb, AcBdCbDa, AdBaCbDc, AdBcCaDb, AbBaCdDc, AcBdCaDb, AdBcCbDa ) 44 120 = 60 120 20 120 + 5 120 1 120
m 1 1 1 + 1 2 1 3! + 1 4!... + ( 1)m 1 m! e 1 = 1 e 1 e m = 7 1 e m 1 e ( m 1 m ) m ( = 1 1 ) m 1 m e
14. 8 1 e A. B. C. D.
( ) 246 (2002/11)