MTH 482 - Spring 2014
Old Assignments
I will not collect homework (except problems marked Hand In), but the next daily quiz will be based on it. You may also hand in problems marked Extra Credit, preferably within a week of the HW date. Each problem you give up on is a lost opportunity to learn: only look at the solution after a serious effort.
I will give an extra point to the first person pointing out a significant typo or other error on this page. Corrections and recent revisions are in red. Future assignments, which are tentative and may be revised, are marked in gray.
On this page, I will denote the binomial coefficient (n choose k) as (n | k), and the multi-set number (n multi-choose k) as ((n | k)). Use the standard vertical notation on your papers. Also, the set of the first k positive integers is denoted [k] = {1,2,...,k}.
3 kinds of buttons, sew any 6 of them onto the 6 positions. A choice of buttons corresponds to entry #1, a function f : [6]→{B,W,R}, where each position i is taken to its button-color f(i). The example (B,W,W,W,B,B) corresponds to f with f(1) = B, f(2) = W, f(3) = W, f(4) = W, f(5) = B, f(6) = B. The number of such f is nk = 36.
3 kinds of buttons, sew on any 6 of them so that every color appears. Entry #3, functions f : [6]→{B,W,R} where all 3 outputs appear, meaning f is surjective. The number of such f is surj(6,3) = 36 − (3 | 1) 26 + (3 | 2) 16.
Give each position one of 3 kinds of buttons or leave empty, which is like a 4th color denoted by −. Entry #1: f : [6]→{B,W,R,−}. The number is 46.
6 distinct buttons (1,2,...,6) are rearranged into new positions. This is a function f : [6]→[6], where the button originally at i gets new position f(i). This function must be both surjective and injective (i.e. bijective) since each position gets one and only one button. This is counted either by entry #2, giving 66 = 6! ; or by entry #3, giving surj(6,6) = 66 − (6 | 1)56 + (6 | 2)46 − (6 | 3)36 + (6 | 4)26 − (6 | 5).
These two expressions look very different, but they must give the same number, since f : [6]→[6] is injective if and only if it is surjective (this is known as the Pigeonhole Principle). Try them on Wolfram Alpha, entering (n | k) as binom(n,k), and nk as n^k. Indeed, they are both 720.
Sew on 3 Black buttons, leaving 3 positions empty (−). An arrangement corresponds to entry #5, classes of injective functions f : [3]→[6], where it does not matter which input goes to a given output. Thus, we may picture indistinguishable [3] as three identical balls or buttons {•,•,•} tossed into 6 labeled bins or positions, with at most one in each bin. The example: (B,−,B,B,−,−) corresponds to the three values f(1) = f(•) = 1, f(2) = f(•) = 3, f(3) = f(•) = 4. The number of such f is (n | k) = (6 | 3) = (6)(5)(4) / 3! .
Same as (e) allowing several buttons at each position. Entry #4, functions f : {•,•,•}→[6] with no restriction. The number is ((6 | 3)) = (6)(7)(8) / 3! .
Sew on 10 Black buttons, allowing several at each position, but no positions empty. Entry #6, f : {•,•,•,•,•,•,•,•,•,•}→[6] with every output appearing, meaning f is surjective. The number is ((6 | 10−6)) = (9 | 5) = (9 | 4) = (9)(8)(7)(6) / 4! .
For (b), each 45-degree diagonal of the square of ((n | k))'s is a row of the ordinary Pascal triangle. Why on earth is that??
The Tranformation Principle says that if there is a reversible transformation (a one-to-one correspondence, an invertible mapping, a bijection) between all objects of one type and all objects of another, then there is the same number of objects of each type. In our case, we wish to transform an arrangement of type a(k,n) into a smaller arrangement of similar type.
Transform each arrangement of balls by removing one ball from the nth bin. If this empties the nth bin, we drop this bin and get k−1 balls in n−1 bins with no bin empty, of type a(k−1, n−1). We can reconstruct the original arrangement by restoring the nth bin with a single ball.
If the transformation does not empty the nth bin, we get k−1 balls in n bins with no bin empty, of type a(k−1, n). We can reconstruct the original arrangement by tossing one more ball in the nth bin.
Thus the arrangements of type a(k,n) are reversibly transformed into all those of the types (k−1, n−1) and a(k−1, n), so the Transformation Principle gives:
a(k,n) = a(k−1, n−1) + a(k−1, n).
Example a(5,3) = a(4,2) + a(4,3). The transformation takes any 5 balls in 3 non-empty bins and removes one ball from the third bin, giving either 4 balls in 2 non-empty bins if the third bin is emptied, or otherwise 4 balls in 3 non-empty bins. This is reversed by restoring one more ball to the third bin.
a(5,3) | a(4,2) | a(4,3) | |
•••|•|• | •••|• | ||
••|••|• | ••|•• | ||
••|•|•• | ••|•|• | ||
•|•••|• | •|••• | ||
•|••|•• | •|••|• | ||
•|•|••• | •|•|•• |
p≤n(k) ?=? p≤n–1(k) + p≤n(k–1).
Entry #3. There are surj(4,2) = 14 surjective functions f : [4]→[2]. Writing as f = (f(1),..., f(4)), they are:
(1,1,1,2) (1,1,2,1) (1,2,1,1) (2,1,1,1) (1,1,2,2) (1,2,1,2) (1,2,2,1)
(2,2,2,1) (2,2,1,2) (2,1,2,2) (1,2,2,2) (2,2,1,1) (2,1,2,1) (2,1,1,2).
Alternatively, write f as input balls {1,2,3,4} in 2 output bins:
123|4 124|3 134|2 234|1 12|34 13|24 14|23
4|123 3|124 2|134 1|234 34|12 24|13 23|14.
Entry #6. Two of the above functions count as the same if you can get one from the other by rearranging the inputs (entries in the list), for example (1,1,1,2) = (1,1,2,1). There are ((2 | 4–2)) = 3 distinct surjective functions (i.e. 3 symmetry classes of functions):
(1,1,1,2) (1,1,2,2) (1,2,2,2)
Alternatively, write f : {•,•,•,•} → [2] as 4 input balls in 2 output bins:
•••|• ••|•• •|•••
Another alternative: write the number of balls in each bin (the multiplicity):
3+1 2+2 1+3.
Entry #9. The count for this entry is given by Stirling partition numbers, whose standard vertical notation is given in the Twelvefold Way table. Here I will use a non-standard horizontal notation {k | n} for these numbers, just as I write (n | k) for choose numbers.
Two functions from entry #3 count as the same if you can get one from the other by switching the outputs {1,2}, for example (1,1,1,2) = (2,2,2,1). The count is given by the Stirling number {4 | 2} = 7. distinct surjective functions:
(1,1,1,2) (1,1,2,1) (1,2,1,1) (2,1,1,1) (1,1,2,2) (1,2,1,2) (1,2,2,1).
Alternatively, write a function f : [4]→{•,•} as input balls {1,2,3,4} in 2 output bins, remembering that switching bins gives an equivalent function:
123|4 124|3 134|2 234|1 12|34 13|24 23|14
Entry #12: Two functions count the same if you can get one from the other by a combination of the above two equivalences. Threre are p2(4) = 2 distinct surjective functions:
(1,1,1,2) (1,1,2,2)
Alternatively, write a function f : {•,•,•,•}→{•,•} as 4 input balls in 2 output bins, remembering that switching bins gives the same function.
•••|• ••|••
Another alternative: write the number of balls in each bin (the multiplicity):
3+1 2+2.
Match word problems to the Twelvefold Way.
Three candidates (A,B,C) split 100 votes. Entry #4: 100 identical votes into 3 bins A,B,C. Answer ((3 | 100)).
Entry #10: 100 identical votes into 3 exchangeable bins. Answer: p≤3(100), which has no simple formula.
Entry #12: 100 identical votes into 3 exchangeable non-empty bins. Answer: p3(100), which has no simple formula.
Nations (A,B,C,D,E,F) split into three exclusive non-empty alliances are like 6 marked balls put into 3 non-empty, exchangeable bins. Entry #9:
{6 | 3} = 1⁄3! ( 36 – (3 | 1) 26 + (3 | 2) 16 ).
Nations (A,B,C,D,E,F) to split into any number of exclusive non-empty alliances. Entry #7: {6 | 1} + {6 | 2} + ··· + {6 | 6}. This is also the Bell number B(6), at the bottom of the Twelvefold Way.
To analyze the false equation p≤2(3) ?=? p≤1(3) + p≤2(2), write the partitions of type p≤2(3) as (a1, a2) with a1 ≥ a2 and a1 + a2 = 3. If a2 = 0, the transformation drops it to give the partition (a1) of type p≤1(3); if a2 > 0, the transformation subtracts 1 from it to give the partition (a1, a2 – 1) of type p≤2(2). The table is:
p≤2(3) | p≤1(3) | p≤2(2) | |
(3,0) | (3) | ||
(2,1) | (2,0) | ||
?? | (1,1) |
Clearly the transformation is not fully reversible: the reverse rule will take every output of the transformation back to the input it came from, but this rule does not work on every entry in the output columns. The reverse rule for the second column takes (a1) back to (a1, 0) = (a1, a2); and for the third column, it should take (b1, b2) = (a1, a2 – 1) back to (b1, b2 + 1) = (a1, a2), meaning (1,1) goes back to (1,2), which is not a valid input.
Thus, the reverse transformation is not defined on the desired set of outputs, and the original transformation is a one-to-one (injective) mapping, but not an onto (surjective) mapping. This will happen in every case with n > 1, so in fact we get the inequality p≤n(k) < p≤n–1(k) + p≤n(k–1).
S = {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}.
A set like S = {1,3,4} is not counted, since it contains 3,4.The difference between the third and fourth trees is whether the grandchild belongs to the older or the younger child. Let on be the number of ordered trees with n nodes, so that the above example counts o4 = 5.
The transformation table for the Stirling cycle number identity [4 | 2] = [3 | 1] + 3 [3 | 2] is:
[4 | 2] |
|
[3 | 1] |
3 [3 | 2] |
(1)(234) |
|
|
2 , (1)(23) |
(1)(243) |
|
|
3 , (1)(23) |
(2)(134) |
|
|
1 , (2)(13) |
(2)(143) |
|
|
3 , (2)(13) |
(3)(124) |
|
|
1 , (3)(12) |
(3)(142) |
|
|
2 , (3)(12) |
(4)(123) |
|
(123) |
|
(4)(132) |
|
(132) |
|
(12)(34) |
|
|
3 , (12)(3) |
(13)(24) |
|
|
2 , (13)(2) |
(14)(23) |
|
|
1 , (1)(23) |
Note that (1)(432) = (1)(243) and (12)(34) = (12)(43), etc., so there are no more permutations to list in the first column. Also, the third column contains every possible combination of a number 1 ≤ j ≤ 3 and a permutation τ of type [3 | 2].
on = o1on–1 + o2on–2 + o3on–3 + ... + on–1o1.
If we define cn = on+1, this means:
cn = on+1 = o1on + o2on–1 + o3on–2 + ... + ono1 = c0cn–1 + c1cn–2 + c3cn–3 + ... + cn–1c0 ,
which is precisely the same recurrence as for the Catalan numbers Cn.
Also we have the same initial value c0 = o1 = 1 = C0.
The same recurrence starting from the same initial value will produce the same numbers: cn = Cn. That is,
on = cn–1 = Cn–1.
Problem: Translate this algorithm into an algebraic formula using the logic-to-algebra chart in today's Notes.
Hint: Choosing mulitplicity j of any kind increases the total size of M by j, so this choice should be translated into xj. Since the logical expression is infinte, the algebraic expression will involve infinte series. Replace these with a simple finite expression, using the Known Series formulas.
Translating the choice algorithm into algebra according to the chart:Step 2:f(x) = (x0 + x1 + x2 + ...) ⋅ (x0 + x1 + x2 + ...) ⋅ ... ⋅ (x0 + x1 + x2 + ...) The infinite series in parentheses is a geometric series, which by the Known Series is 1⁄(1−x). Thus f(x) = 1⁄(1−x)n.
= (1 + x + x2 + ⋅⋅⋅)n.
Taking derivatives of f(x) = (1−x)−n, mindful of the Chain Rule:f '(x) = (−n)(1−x)−n−1(−1) = n(1−x)−n−1, Now Taylor's Formula gives:f ''(x) = n(−n−1)(1−x)−n−2(−1) = n(n+1)(1−x)−n−2,
⋮
f(k)(x) = n(n+1)(n+2)...(n+k−1)(1−x)−n−kak = f(k)(0)⁄k! = n(n+1)(n+2)...(n+k−1)(1−0)−n−k⁄k! Now using the rising-power notation nk = n(n+1)(n+2)...(n+k−1), which is pronounced "n to the k rising", we get:
= n(n+1)(n+2)...(n+k−1)⁄k!((n | k)) = ak = nk / k! .
This is of course equivalent to ((n | k)) = (k+n−1 | k), but this form is neater, and nicely analogous to (n | k) = nk / k! .
Step 0: Let ak be the number of handfuls of the three kinds of coins worth a total of k euros. This is the natural generalization of the problem, rather than changing the kinds of coins.
Step 1:
Because a handful is unordered, all that matters is how many of each kind of coin. The choice algorithm is:Step 2:(choose a handful, any value) ⇔ (0 ones or 1 ones or 2 ones or …) and (0 golds or 1 golds or 2 golds or …) and (0 silvers or 1 silvers or 2 silvers or …).
Translating into algebra, replacing one by x1, gold and silver by x2:
f(x) = (x0 + x1 + x2 + ...) ⋅ (x0 + x2 + x4 + ...) ⋅ (x0 + x2 + x4 + ...) Using z = x2 in the known geometric series 1⁄(1−z) = 1 + z + z2 + …, we find 1 + x2 + x4 + … = 1⁄(1−x2). Hence:
= (1 + x + x2 + …)(1 + x2 + x4 + …)2.f(x) = 1⁄(1−x)(1−x2)2
The denominator is factorable as (1−x)3 (1+x)2, so a partial fraction expansion would be of the form:Follow-up: It is wise to check this with Wolfram Alpha (which I should have done originally): the power series of f(x) = 1⁄(1−x)(1−x2) is indeed:f(x) = A⁄(1−x) + B⁄(1−x)2 + C⁄(1−x)3 + D⁄(1+x) + E⁄(1+x)2 . Yuck! Not worth the trouble! Hard to compute, and the resulting formula would be a mess, anyway.
A much better trick is the following: since 1−x2 = (1−x)(1+x), we can substitute 1⁄(1−x) = (1+x) ⋅ 1⁄(1−x2) to consolidate the denominator as a power of a single binomial factor:f(x) = (1+x)⁄(1−x2) ⋅ 1⁄(1−x2)2 = (1+x) ⋅ 1⁄(1−x2)3
Knowing the negative-power binomial series 1⁄(1−x2)3 = ∑k≥0 ((3 | k)) x2k, we find:
Using ((3 | k)) = (k+2 | k) = (k+2 | 2) = (k+2)(k+1)/2, we simplify: f(x) = (1+x) ⋅ ∑k≥0 ((3 | k)) x2k = ∑k≥0 ((3 | k)) x2k + ∑k≥0 ((3 | k)) x2k+1
a2k = a2k+1 = ((3 | k)) = ½(k+2)(k+1).
The answer to our original problem is therefore: a20 = a2(10) = ((3 | 10)) = ½(12)(11) = a2k = 66.
f(x) = 1 + x + 3x2 + 3x3 + 6x4 + 6x5 + 10x6 + 10x7 + 15x8 + 15x9 + 21x10
+ 21x11 + 28x12 + 28x13 + 36x14 + 36x5 + 45x16 + 45x17 + 55x18 + 55x19 + 66x20 + ...
This can be explained combinatorially as follows: to get a total value of 20 euros, we must have an even number of one-euro coins. Grouping the one-euros into pairs, we can think of this as 3 kinds of 2-euro coins: one-euro pair, gold two-euro, silver two-euro. The ways to choose a multi-set of 10 of these 2 kinds is ((3 | 10)). This is much clearer in retrospect, once the Generating Function Method has given us the answer.
Step 0: Let ak be the number of rows of 14 of the three kinds of coins worth a total of k. This is the natural, minimal generalization of the problem, rather than changing the length of a row or the kinds of coins. It would be possible to replace 14 with k, but this would not yield a tractable generating function.
Step 1:
Because a row is ordered, we must choose the 14 coins one by one. The choice algorithm is:Step 2:(choose 14 coins, any total value) ⇔ (coin 1 is one or gold or silver) and (coin 2 is one or gold or silver) and … and (coin 14 is one or gold or silver)
Translating into algebra:
f(x) = (x1 + x2 + x2) ⋅ … ⋅ (x1 + x2 + x2) = (x+2x2)14.
Factoring and applying the Binomial Theorem:Follow-up: This can be explained combinatorially as follows: to get a total value of 20 from 14 coins, we must have 8 ones and 6 twos. Choose 6 of the 14 positions for the twos, giving (14 | 6) possibliities; then choose whether each two is a silver or a gold, giving 26 possibilities. Again, this is clear once we know the answer!We want the coefficient of x20, which corresponds to k = 6, i.e. a20 = (14 | 6) 26. f(x) = x14 (1+2x)14 = x14 ∑k=014 (14 | k) (2x)k = ∑k=014 (14 | k) 2k xk+14.
f(x)
=
0 + ∑k≥1 ak−1xk
+ ∑k≥1 krkxk
=
x∑k≥1 ak−1xk−1
+ ∑k≥1 krkxk
=
x f(x) +
rx⁄(1−rx)2.
Follow-up: Compare this to the sum of a finite geometric series:
Once we have our formula, we can prove it very easily, by multiplying out (1−r)2 (r + 2r2 + ... + krk), and finding we can cancel all the terms except for krk+2 − (k+1)rk+1 + r.
We can also check the formula in special cases. For example, for r = 0 we get ak = 0, as expected. For r = 1, we get ak = 1 + 2 + ... + k. Our formula is not valid at r = 1 since the denominator vanishes. However, we can apply L'Hopital's Rule twice as r → 1, giving:
f(x) = 1 ⁄(1 − x −x3).
This is almost (but not quite!) the same as the Fibonacci generating function x⁄(1 − x −x2) , which is derived in exactly the same way.
Writing the denominator as 1−x− x3 = −(x−α)(x−β)(x−γ) and clearing denominators, we get:
and substituting x = α gives A = 1⁄α(α−β)(α−γ), which we can simplify by part (c) as:
Hence we have the approximation:
ak ≅ 1⁄(3α2+1)αk+1 ,
Applying the above approximation to k = 10, we get a10 ≅ 27.95, whereas the exact value is 28. Not bad!
Let us compare ak to the Fibonacci sequence Fk. We can see from the recurrence that ak grows more slowly than Fk : the reproduction is more delayed in ak. And indeed, ak ≅ const × 1.47k, whereas we previously showed the approximation Fk ≅ const × 1.62k.
fk(x) = ∑n≥k {n | k} xn = xk ⁄(1 − x)(1−2x)…(1−kx) .
Work out the constants A1,..., Ak in the partial fraction decomposition:
fk(x) = A1 ⁄(1 − x) + A2 ⁄(1 − 2x) + ... + Ak ⁄(1 − kx) .
a0 + a1x + a2x2 + a3x3 + ....
=
1 + 1 + x + x2 + x3 + ...
−2a0x − 2a1x2 − 2a2x3 − ...
a0 + a1x + a2x2 + a3x3 + ....
=
1⁄2
+ 3⁄2 + 3⁄2 (2x) + 3⁄2 (22x2) + 3⁄2 (23x3) + ...
−a0x − a1x2 − a2x3 − ...
Clearing denominators in the third way:
a0 + a1x + a2x2 + a3x3 + ....
=
2 − x + 0x2 + 0x3 + ...
−3a0x − 3a1x2 − 3a2x3 − ...
2a0x2 + 2a1x3 + ...
Step 2. From Math 481 HW 10/4, we recall: h(x) = ½ − ½(1−4x)1/2 , h'(x) = (1−4x)−1/2 , h''(x) = ½(4)(1−4x)−3/2 , h'''(x) = (1⁄2)(3⁄2)(42)(1−4x)−5/2, and:
ak = h(k)(0) / k! | = (1⁄2)(3⁄2)...(2k−3⁄2) 4k−1 / k! |
= (1)(3)(5)...(2k−3) 4k−1 / 2k−1 k! | |
= (1)(3)(5)...(2k−3) 2k−1(k−1)! / (k−1)! k! | |
= (1)(3)(5)...(2k−3) (2)(4)(6)...(2k−2) / (k−1)! k! | |
= (2k−2)! / (k−1)! k! = 1⁄k (2k−2 | k−1) . |
HW 1/24 #4. We did this in class. Assuming {Cn} ↔ops f(x), we apply the ops correspondence to both sides of the recurrence equation: Cn+1 = C0Cn + C1Cn−1 + ⋯ + CnC0 for n≥0. We apply Rule 1 on the left side, Rule 3 or 4 on the right side, and we equate the two generating functions:
L(f(x)) =
D(M(D(f(x)))) + 3 D(f(x)) − 5 f(x)
=
(x f '(x))' + 3 f '(x) − 5 f(x)
=
f ''(x) + x f '(x) + 3 f '(x) − 5 f(x) .
S1|⋯⋯|Sk
↦
(
S' ,
S'1|⋯|S'j−1|S'j+1|⋯|S'k
)
where
n ∈ Sj ,
S' = Sj\{n} ⊂ [n−1],
|Sj| = i
and
S'1∪⋯∪S'k = [n−1−i] .
S1|S2|S3 = 16|347|25 .
We remove S2 = {3,4,7} containing n = 7, and we record S' = {3,4}. The remaining set partition is S1|S3 = 16|25, which covers [n] \ S2 = {1,2,5,6}. The tamping map {1,2,5,6} → {1,2,3,4} is 1↦1, 2↦2, 5↦3, 6↦4, and applying it to S1 and S3 gives the final set partition S'1|S'3 = 14|23 . The completed transformation is:S1|S2|S3 = 16|347|25 ↦ (S' , S'1|S'3) = ({3,4} , 14|23)
log(y) = ∫ 1⁄y dy = ∫ ex dx = ex + c
for some constant c. Solving for y gives y = B~(x) = C exp(ex) for some C = ec > 0. The initial condition B~(0) = B0 = 1 forces C = e−1, so that B~(x) = e(ex − 1) = exp(ex − 1).
(n | 2) (n−2 | 2) ⋯ (2 | 2) = (2m)!⁄(2!)m .
This is the number of ways to partition the set [n] into m two-element subsets [n] = S1 ∪ ⋯ ∪ Sm , where the order of the Si's matters.
{(2,♠), (3,♥), (5,♥), (1♦), (4,♦)} = {(1♦), (2,♠), (3,♥), (4,♦), (5,♥)}.
Two types of sets which are illegal, and do not count as hands in this family:{(1,♦), (2,♠), (2,♥), (4,♦), (5,♥)} or {(1♦), (2,♠), (4,♥), (5,♦), (6,♥)}.
hn = ∑i1,...,i4 (n | i1) (n−i1 | i2) (n−i1−i2 | i3) (n−i1−i2−i3 | i4)
= ∑i1,...,i4 n!⁄(i1! i2! i3! i4!) ,
where the summation runs over integers i1,...,i4 ≥ 0 with i1 + i2 + i3 + i4 = n. It is easily seen by generalizing [W] Rule 3' (exponential convolution), that this has generating function:h(x) = (∑i≥0 xi⁄i!)4 = e4x .
B(x) = ed(x) = 1 + d(x) + 1⁄2! d(x)2 + 1⁄3! d(x)3 + ⋯ ..
n | 1 | 2 | 3 | 4 | 5 |
cn / gn | 1 | 1⁄2 | 1⁄2 | 19⁄32 | 91⁄128 |
1 | 0.5 | 0.5 | 0.59 | 0.71 |
c(x) = log(1 + z) = z
− z2⁄2
+ z3⁄3
− z4⁄4
+ ⋯
= x
+ 1⁄2 x2
+ 2⁄3 x3
+ 19⁄12 x4
+ ⋯ .
= 1 x
+ 1 x2⁄2!
+ 4 x3⁄3!
+ 38 x4⁄4!
+ ⋯ .
expand z - z^2 / 2 + z^3 / 3 - z^4 / 4
where z = x + 2 x^2 / 2! + 2^3 x^3 / 3! + 2^6 x^4 / 4! .
{n | k} = 1⁄k! ∑j=0k (−1)k−j (k | j) jn.
B(x) = 1⁄e ∑j≥0 ejx⁄j! = 1⁄e ∑j≥0 ∑n≥0 (jx)n⁄j!n! .
Bn = 1⁄e ∑j≥1 jn⁄j! .
B3 = 1⁄e (1 + 23⁄2! + 33⁄3! + 43⁄4! + 53⁄5! + ⋯) =
I don't think we would have thought of this by combinatorial reasoning, do you?
Extra Credit: For general n, how many terms of this series do we need, so that rounding to the nearest integer gives Bn? Are n terms enough, or n/2, or √n? If we knew this, it would give a finite formula for Bn, perhaps even an efficient formula.
For more on Bell numbers, see Wikipedia.
h(k)(x) = ∑n≥0 {n | k} xn⁄n! = 1⁄k! d(x)k = 1⁄k! logk(1⁄1−x) .
See also Wilf Ch 3.5, p. 81
R(x)
=
ℓ(x)
=
∑k≥0 ℓ(k)(x)
=
∑k≥0 d(x)k
=
1⁄(1 − d(x))
=
1⁄(1 − (ex−1))
=
1⁄(2 − ex) .
R(x)
=
1⁄2
1⁄(1 − ½ex)
=
1⁄2
∑k≥0
(½ex)k
=
1⁄2
∑k≥0
(1⁄2k)
ekx
=
1⁄2
∑k≥0
(1⁄2k)
∑n≥0 knxn⁄n!
=
∑n≥0
(∑k≥0
kn⁄2k+1)
xn⁄n!
Step 1: We want to find the exponential generating function f(x) = ∑n≥0 an xn⁄n! . We start with the deck D = {•, ••}, so d(x) = x + x2⁄2! . A combination of teams corresponds to an unordered hand with any number of cards from D, so by Notes 2/7 #4, the team enumerator is:
f(x) = h(x) = exp d(x) = exp(x + x2⁄2!).
Step 2: We could try expanding this using the Taylor series of exp(z), and the binomial theorem for zk = (x + x2⁄2!)k, but this does not seem worth it. Wolfram Alpha gives the x10 term of the Taylor series as: (1187⁄453600) x10, so:
Step 1: To find the exponential generating function f(x) = ∑n≥0 an xn⁄n! , we start with the same deck D = {•, ••} with d(x) = x + x2⁄2! . A list of teams corresponds to an ordered hand with any number of cards from D, so by Notes 2/7 #2, summed over all k into a geometric series, the team list enumerator is:
f(x) = ℓ(x) = ∑k≥0 d(x)k = 1⁄(1 − d(x)) = 1⁄(1 − x − ½x2) .
Step 2: Again, putting the above function into Wolfram Alpha immediately gives:
We could also expand algebraically using a partial fraction expansion of f(x). Letting x = α = −1−√3 and x = β = −1+√3 be the vertical asymptotes, so that 1 − x − ½x2 = (1 − x⁄α)(1 − x⁄β), we expand as:
f(x) = 1⁄(1 − x − ½x2) = A⁄(1 − x⁄α) + B⁄(1 − x⁄β)
1⁄α = 1−√3⁄2 1⁄β = 1+√3⁄2 A = 3−√3⁄6 B = 3+√3⁄6
an⁄n! = A⁄αn + B⁄βn ≈ B⁄βn = (3+√3⁄6) (1+√3⁄2)n .
Step 1: We want to find the exponential generating function f(x) = ∑n≥0 an xn⁄n! . This time the deck must take the order of each pair into account:
D = {① , ①→② , ②→①} or {(①) , (①,②) , (②,①)},
f(x) = h(x) = exp d(x) = exp(x + x2).
Step 2: a10 = 10! (19093⁄518400) = 133651.
Step 1: The deck is the same as in part (c), so and d(x) = x + x2. A list of teams-with-leader corresponds to an ordered hand with any number of cards from D, so as in part (b), the team enumerator is:
f(x) = ℓ(x) = 1⁄(1 − x − x2)
Step 2: Since the exponential generating function of our sequence {an} is the same as the ordinary generating function of the Fibonacci numbers {Fn+1}, we get:
an⁄n!
= Fn+1, i.e. an = n! Fn+1.
Extra Credit: Explain this formula combinatorially. It seems to be saying that one of our team lists can be transformed into a permutation along with a combinatorial model for the Fibonacci numbers. (We gave some models for the Fibonacci numbers in class, or check Wikipedia.)
x f '(x)⁄f(x) = x d'(x) .
d(x) = ∑n≥2 (n−1)! xn⁄n! = log 1⁄(1−x) − x .
D(x) = exp d(x) = exp(log 1⁄(1−x)) exp(−x) = e−x⁄(1−x) .
(1 − x) ∑n≥0 Dn xn⁄n! = ∑n≥0 Dn xn⁄n! − ∑n≥0 Dn xn+1⁄n!
= ∑n≥0 Dn xn⁄n! − ∑n≥0 (n+1)Dn xn+1⁄(n+1)!
= ∑n≥0 Dn xn⁄n! − ∑n≥1 n Dn−1 xn⁄n!
A = limx→1 (e−x⁄(1−x)) (1−x) = e−1.
Dn = n!(1 − 1⁄1! + 1⁄2! ⋯ ± 1⁄n!).
Dn ≈ e−1√2πn (n⁄e)n.
log10(e−1√2π(100) (100⁄e)100) = −log10(e) + ½ log10(2π) + 1 + 100(2 − log10(e)) ≈ 157.5
d⁄dx log f(x) = 1⁄f(x) f '(x),
n an = ∑ i=0n (n | i) i di an−i .
an = 1⁄n ((n | 1)d1an−1 + 2(n | 2)d2an−2 + 3(n | 3)d3an−3 + ⋯ + n(n | n)dna0) .
an = d1an−1 + (n−1 | 1)d2an−2 + (n−1 | 2)d3an−3 + ⋯ + (n−1 | n−1)dna0 .
x f '(x) = x (x + 2 x2⁄2)' f(x)
n an = (n | 1)d1an−1 + 2(n | 2)d2an−2 ,
an = an−1 + 2(n−1) an−2 .
Bn = Bn−1 + (n−1 | 1)Bn−2 + (n−1 | 2)Bn−3 + ⋯ + (n−1 | n−1)B0 .
log D(x) = − x + log 1⁄(1−x) ,
x D'(x)⁄D(x) = − x + x⁄(1−x) = x2⁄(1−x) ,
x D'(x) = x2⁄(1−x) D(x) .
n Dn = ∑ i=2n (n | i) i! Dn−i
Dn = (n−1) Dn−2 + (n−1)2 Dn−3 + (n−1)3 Dn−4 + ⋯ + (n−1)n−2 D1 + (n−1)! D0 .
A = limx→α R(x) (1 − x/α) = limx→α (1 − x/α)⁄(2 − ex)
= limx→α (− 1/α)⁄(− ex) = 1⁄αeα = 1⁄2log(2) .
∑n≥0 Rn⁄n! xn = R(x) ≈ A⁄(1 − x/α) = ∑n≥0 A⁄αn xn ,
n | 5 | 10 | 20 |
Cn | 42 | 16796 | 6564120420 |
4n⁄n3/2√π | 52 | 18708 | 6.93 × 109 |
ratio | 1.23 | 1.11 | 1.06 |
d(x) = 2x + ∑n≥2 (n−1)! xn⁄n! = x + log 1⁄(1−x) .
f(x) = h(x) = ed(x) = exp(x + log 1⁄(1−x)) = ex⁄(1−x) .
an⁄n! = 1 + 1⁄1! + 1⁄2! + ⋯ + 1⁄n! ,
Also, ex2/2 = ∑m≥0 (2m)!⁄2m m! x2m⁄(2m)! = ∑n≥0 n!odd xn⁄n! , where we invent the notation: n!odd = (1)(3)(5)⋯(n) for n odd, and n!odd = 0 for n even. (This appeared in HW 1/24 #4.) Applying Wilf's Rule 3' (p 42):
(choose any boxes of $1, $2, $3) | ⇔ | (0×$1 or 1×$1 or 2×$1 or ⋯)
and (0×$2 or 1×$2 or 2×$2 or ⋯) and (0×$3 or 1×$3 or 2×$3 or ⋯) . |
f(x) = ∑n≥0 anxn
=
(x0 + x1 + x2 + ⋯)
(x0 + x2 + x4 + ⋯)
(x0 + x3 + x6 + ⋯)
=
1⁄(1−x)
1⁄(1−x2)
1⁄(1−x3)
=
1⁄(1−x)(1−x2)(1−x3) .
f(x) =
1⁄(1−x)
1⁄(1−x2)
1⁄(1−x3)
=
1⁄(1−x)
(1−x)(1+x)
(1−x)(1 − x/γ)(1 − x/δ)
=
1⁄(1−x)3
(1+x)
(1 − x/γ)(1 − x/δ)
=
A⁄(1−x)3
+
B⁄(1−x)2
+
C⁄(1−x)
+
D⁄(1+x)
+
E⁄(1 − x/γ)
+
F⁄(1 − x/δ) .
f(x) ≈ A⁄(1−x)3 = ∑n≥0 A ((3 | n)) xn ,
A = limx→1 f(x) (1−x)3 = limx→1 (1−x)3⁄(1−x)(1−x2)(1−x3) = −6⁄−36 . = 1⁄6 .
an ∼ 1⁄6 ((3 | n)) = 1⁄12 (n+1)(n+2) ∼ n2⁄12
f(x) =
1⁄(1−x)
1⁄(1−x2)
1⁄(1−x3)
=
(1+x+⋯+x5)⁄(1−x6)
(1+x2+x4)⁄(1−x6)
(1+x3)⁄(1−x6)
=
(1+x+2x2+3x3+4x4+5x5+4x6+5x7+ 4x8+3x9+2x10+x11+x12)⁄(1−x6)3.
f(x) =
∑m≥0 ((3 | m)) x6m
+
∑m≥0 ((3 | m)) x6m+1
+
2 ∑m≥0 ((3 | m)) x6m+2
3 ∑m≥0 ((3 | m)) x6m+3
+
4 ∑m≥0 ((3 | m)) x6m+4
+
5 ∑m≥0 ((3 | m)) x6m+5
4 ∑m≥0 ((3 | m)) x6m+6
+
5 ∑m≥0 ((3 | m)) x6m+7
+
4 ∑m≥0 ((3 | m)) x6m+8
3 ∑m≥0 ((3 | m)) x6m+9
+
2 ∑m≥0 ((3 | m)) x6m+10
+
∑m≥0 ((3 | m)) x6m+11
+
∑m≥0 ((3 | m)) x6m+12
a6m
=
((3 | m)) + 4((3 | m−1)) + ((3 | m−2))
a6m+1
=
((3 | m)) + 5((3 | m−1))
a6m+2
=
2((3 | m)) + 4((3 | m−1))
a6m+3
=
3((3 | m)) + 3((3 | m−1))
a6m+4
=
4((3 | m)) + 2((3 | m−1))
a6m+5
=
5((3 | m)) + ((3 | m−1))
a6m
=
3m2 + 3m + 1
a6m+1
=
(m+1)(3m+1)
a6m+2
=
(m+1)(3m+2)
a6m+3
=
3(m+1)2
a6m+4
=
(m+1)(3m+4)
a6m+5
=
(m+1)(3m+5) .
a100 = (16 + 1) (3(16) + 4) = 884.
(1−x)(1−x2)(1−x3) f(x) = 1
(1 − x − x2 + x4 + x5 − x6) ∑n≥0 anxn = 1 + 0x + 0x2 + ⋯ .
an − an−1 − an−2 + an−4 + an−5 − an−6 = 0
an = an−1 + an−2 − an−4 − an−5 + an−6 for n ≥ 1 (from a0 = 1).
(1−x2)(1−x3) f(x) = 1⁄(1−x)
(1 − x2 − x3 + x5) ∑n≥0 anxn = 1 + 1x + 1x2 + ⋯
an − an−2 − an−3 + an−5 = 1
an = an−2 + an−3 − an−5 + 1.
(list of k ≥ 0 boxes
of $1, $2, $3) | ⇔ | (0 boxes) or
(1 box: $1 or $2 or $3)
or ( 2 boxes: ($1 or $2 or $3) then ($1 or $2 or $3) ) or ( 3 boxes: ($1 or $2 or $3) then ($1 or $2 or $3) then ($1 or $2 or $3) ) or ⋯ |
f(x) = ∑n≥0 anxn
=
1 +
(x1 + x2 + x3)
+ (x1 + x2 + x3)2
+ (x1 + x2 + x3)3
+ ⋯
=
1⁄(1 − (x+x2+x3))
=
1⁄(1−x−x2−x3) .
α ≈ 0.54 , β ≈ − 0.77 + 1.12i , γ ≈ − 0.77 − 1.12i ,
f(x) =
1⁄(1−x−x2−x3)
=
1⁄(1 − x/α)(1 − x/β)(1 − x/γ)
=
A⁄(1 − x/α)
+
B⁄(1 − x/β)
+
C⁄(1 − x/γ) .
f(x) ≈ A⁄(1 − x/α) = ∑n≥0 (A⁄αn) xn ,
A = limx→α f(x) (1 − x/α) = limx→α (1 − x/α)⁄(1−x−x2−x3)
= (−1/α)⁄(−1−2α−3α2) = 1⁄α(1+2α+3α2) .
an ∼ A⁄αn = 1⁄αn+1(1+2α+3α2) .
(1−x−x2−x3) f(x) = 1
(1 − x − x2 − x3) ∑n≥0 anxn = 1 + 0x + 0x2 + ⋯ .
an − an−1 − an−2 − an−3 = 0
an = an−1 + an−2 + an−3 for n ≥ 1 (from a0 = 1).
D =
{
① ,
①→② ,
②→① ,
①→②→③ ,
①→③→② ,
②→①→③ ,
②→③→① ,
③→①→② ,
③→②→①
}
g(x) = ℓ(x) = 1⁄(1 − d(x)) = 1⁄(1−x−x2−x3) .
D = { ① , ①② , ①②③ }
c100 = 11527937348312713865082241287737153907730362053400425345132475796235815534719539623297472916358562840576
λ = (λ1, λ2,..., λk) where λ1 ≥ λ2 ≥ ⋯ ≥ λk > 0 and λ1 + λ2 + ⋯ + λk = n.
|
|
|
|
|
φ(x) = ∑n≥0 p(n)xn = ∏i≥1 1⁄(1−xi) .
1⁄φ(x) = ∏i≥1 (1−xi) = 1 + ∑m≥1 (−1)m(x½m(3m−1) + x½m(3m+1)).
an =
#{partitions of n into an even number of distinct parts}
−
#{partitions of n into an odd number of distinct parts}.
p(n) = ∑m≥1 (−1)m+1(p(n − ½m(3m−1)) + p(n − ½m(3m+1))).
(2m−1, 2m−2,..., m) and (2m, 2m−1,..., m+1).
rn+1 = 1⁄n ∑k=1n ∑i | k i ri rn−k+1 .
rn n! =?? nn−1,
r5 = ((r1 | 4)) + ((r1 | 2)) ((r2 | 1)) + ((r2 | 2)) + ((r1 | 1)) ((r3 | 1)) + ((r4 | 1))
= 1 + 1 + 1 + 2 + 4 = 9 .
T = | ®−− | ® | −−® | −−O | |
| | |||||
® |
rn+1 = ∑k ∏i≥1 ((ri | ki)) = ∑k ((r1 | k1)) ((r2 | k2)) ((r3 | k3)) ⋯
r5 = ((r1 | 4)) + ((r1 | 2)) ((r2 | 2)) + ((r1 | 1)) ((r3 | 1)) + ((r4 | 1)) .
T1 | T2 | T3 | T4 | T5 | T6 | |
|Sym(T)| | 2 | 2 | 2 | (4)(2) = 8 | 3! = 6 | 5! = 60 |
pT | 3 | 5 | 4 | 2 | 4 | 2 |
qT | 2 | 4 | 3 | 1 | 3 | 1 |
T | P3 | P5 | P4 | P2 | P4 | P2 |
12 | ||||
| | ||||
10 | 11 | |||
| | | | |||
1 | −− | 2 | −− | 3 |
\ | / |
Sym(G) = { ε, (12), (13), (23), (123), (132), (67), (12)(67), (13)(67), (23)(67), (123)(67), (132)(67) }
V− = {1−, 4−, 5−, 6−}, where 1− = {1,2,3}, 4− = {4}, 5− = {5}, 6− = {6,7}.
Proposition: Any finite tree T has at most one symmetry edge. |
T−e = (T−e)x ∪ (T−e)y
T−f = (T−f)v ∪ (T−f)w
T−e−f | = | (T−e−f)v ∪ (T−e−f)x ∪ (T−e−f)y |
= | (T−e−f)v ∪ (T−e−f)w ∪ (T−e−f)y. |
La,c = {x ∈ R2 s.t. a • x = c}.
(a, c) = ((1,1), 2), ((-1,1), 2), (−1,2), 0).
(0,0,0), (1,1,1), (1,2,3), (−1,1,1).
½ n + 2 ≤ r ≤ 2n − 4.
3 ≤ κ(G) ≤ δ(G) ≤ 5.
P1 = (0,1)(0,2),(1,2),(2,2),(3,2) and P2 = (0,1),(1,1),(2,1),(3,1)(3,2).
P1 = (1,1)(2,1),(3,1),(3,0),(2,0) and P2 = (1,1),(0,1),(0,2).
P | pyram | prism | anti-pr | bipyr | trapezo | dodeca | icosa |
κ(G) | 3 | 3 | 4 | 4 | 3 | 3 | 5 |
δ(G) | 3 | 3 | 4 | 4 | 3 | 3 | 5 |
PE(x1) = −∫0x1F(x) dx .
F(x) = −(x−a1) − (x−a2),
PE(x1,y1) = −∮ F(r) • dr ,
Fi = ∑j ∈ N(i) (vj − vi) = (0, 0) for i = 1,...,k,
deg(vi) | if i = j, | ||
ℓij | = | −1 | if ij ∈ E |
0 | otherwise. |
bi = ∑j ∈ XN(i) xj , ci = −∑j ∈ XN(i) yj ,
L • x = b and L • y = c,
(x1, y1) = (1⁄3, 1⁄2√3 ), (x2, y2) = (13⁄24, 1⁄4√3 ), (x3, y3) = (7⁄24, 1⁄4√3 ).
|
|
z = ajx + bjy + cj .
hv = qR • (v,1) = qS • (v,1)
Da(x) = a'(x) = limh→0 (a(x+h) − a(x))⁄h = limh→0 (a(x) − a(x−h))⁄h
Δ+an = (an+1−an)⁄1 = an+1 − an.
Δ−an = (an−an−1)⁄1 = an − an−1.
Σan = ∑i=0n ai.
Δ(Σan) = an and Σ(Δan) = an .
(an)n≥0 ↔ops f(x) = ∑n≥0 anxn.
Δ+Δ−an = Δ−Δ+an = an+1 + an−1 − 2an for n ≥ 1.
nk = ∑i=0k {k | i}n i ,
aba, abb, bab, bba, bbb.
Any word w ⇔ (w = ∅) or (w = a) or (w = bw' for word w') or (w = abw' for word w')
f(x) = 1 + x + x f(x) + x2 f(x).
(1 − x − x2) ∑n≥0 wnxn = ∑n≥0 wnxn − ∑n≥0 wnxn+1 − ∑n≥0 wnxn+2 = 1 + x .
f(x) = A⁄(1 − x/α) + B⁄(1 − x/β)
A = limx→α (1 − x/α) f(x) = limx→α (1 − x/α)(1+x)⁄(1 − x/α)(1 − x/β) = (1+α)⁄(1 − α/β) = (5+3√5)⁄10 ,
100 = n ≤ 2r−4 = 200 and 102 = r ≤ 2n−4 = 196.
S | {1,2,3} | {1,2,4} | {1,2,5} | {1,2,6} | {1,3,4} | {1,3,5} | {1,3,6} | {1,4,5} | {1,4,6} | {1,5,6} | {2,3,4} | {2,3,5} | {2,3,6} | {2,4,5} | {2,4,6} | {2,5,6} | {3,4,5} | {3,4,6} | {3,5,6} | {4,5,6} |
S' | {1,2} | {1,3} | {1,4} | {1,5} | {2,3} | {2,4} | {2,5} | {3,4} | {3,5} | {4,5} | ||||||||||
S' | {1,2,3} | {1,2,4} | {1,2,5} | {1,3,4} | {1,3,5} | {1,4,5} | {2,3,4} | {2,3,5} | {2,4,5} | {3,4,5} |
In the first case, the output of the transformation is a permutation τ of type [n–1 | k–1], which can be restored to σ by adding the cycle (n). In the second case, the output is a pair (τ, j), where τ is of type [n–1 | k] and 1 ≤ j ≤ n–1, which can be restored to σ by enlarging the cycle of τ which contains j by inserting n before j. For example, the above σ = (124)(36)(5) would be transformed to the pair (τ, j) where τ = (124)(3)(5) and j = σ(6) = 3. The reverse transformation inserts 6 before j = 3, giving (124)(63)(5), which is another expression for σ.
f(x) = a0 + a1x + a2x2 + .... = ∑k≥0 ak xk .
Logic | choose an object of any size k ≥ 0 | ⇔ | basic choice adding size m | or | and |
Algebra | f(x) = ∑k≥0 akxk | = | xm | + | × |
P(xD) f(x) = (xD)2 f(x) − 5 xD f(x) + 3 f(x)
= x d⁄dx(x d⁄dx f(x)) − 5x d⁄dx f(x) + 3 f(x) .
S1 ∪ ⋯ ∪ Sk = [n].
The weight of hand is the total weight of its cards: wt(H) = n = wt(C1) + ⋯ + wt(Ck).hn = #{hands H with wt(H) = n}
and its exponential generating function: h(x) = ∑n≥0 hn xn⁄n! .
|
|
|
|
|
|
|
|
|
|
C1 = ({1},ℂ) = |
| C2 = ({1,2},ℙℙ) = |
|
h(x) = exp d(x) = ed(x)
We illustrate this formula and its proof for the toy example.bn = b2m = n!⁄m!(2!)m ,
giving the exponential generating function:∑m≥0 b2m(x2m⁄(2m)!) = ∑m≥0 (2m)!⁄m!(2!)m (x2m⁄(2m)!)
= ∑m≥0 1⁄m! (x2⁄2!)m = exp(x2⁄2!) = ex2 / 2!.
hn = ∑i=0n (n | i) (1) bn−i .
This is precisely the exponential convolution formula, so the hand-enumerator series must be the product of the enumerator series of the ℂ-only and the ℙ-only coolers, which we determined above. That is:h(x) = ∑n≥0 hnxn⁄n! . = ex • ex2/2! = exp(x + x2⁄2!) = exp d(x).
B(x) = ed(x) = eex−1 = exp(ex − 1).
We got this formula previously from a recurrence in HW 1/31 #2.P = { K = (V,E), where V = [i] for some i ≥ 1, and K is a connected graph }.
C = ( S = {2,5,6}, K = ①−③−② )
represents the graph K' with vertex set S = {2,5,6} substituted for the standard labels {1,2,3} by means of the spreading map: 1 ↦ 2, 2 ↦ 5, 3 ↦ 6.C ↭ K' = ②−⑥−⑤
G = ③ ①−④ ②−⑥−⑤
is represented by the hand H = {C1, C2, C3}, where C1 = {{3},①), C2 = ({1,4}, ①−②), C3 = {{2,5,6}, ①−③−②}.g(x) = ec(x) ⇒ c(x) = log g(x) = log ∑n≥0 2(n | 2) xn⁄n! .
(Recall that we always use log to mean the natural logarithm.)
ℓ(x) = d(1)(x) • d(2)(x).
ℓ(k)(x) = d(x)k.
h(k)(x) = 1⁄k! ℓ(k)(x) = 1⁄k! d(x)k.
h(x) = ed(x) = exp d(x).
h(x) = 1⁄(1 − d(x)) .
ℓ(x) = ∑k≥0 ℓ(k)(x) = ∑k≥0 d(x)k = 1⁄(1 − d(x)) ,
λ = (λ1, λ2,..., λk) where λ1 ≥ λ2 ≥ ⋯ ≥ λk > 0 and λ1 + λ2 + ⋯ + λk = n.
|
|
|
|
|
φ(x) = ∑n≥0 p(n)xn = ∏i≥1 1⁄(1−xi) .
1⁄φ(x) = ∏i≥1 (1−xi) = 1 + ∑m≥1 (−1)m(x½m(3m−1) + x½m(3m+1)).
an =
#{partitions of n into an even number of distinct parts}
−
#{partitions of n into an odd number of distinct parts}.
T1,1 = ®, T2,1 = ®−−O, T3,1 = ®−−O−−O T3,2 = O−−®−−O.
Choose T | ⇔ | (root) and (0 T1,1's or 1 T1,1's or 2 T1,1's or ⋯) |
and (0 T2,1's or 1 T2,1's or 2 T2,1's or ⋯) | ||
and (0 T3,1's or 1 T3,1's or 2 T3,1's or ⋯) | ||
and (0 T3,2's or 1 T3,2's or 2 T3,2's or ⋯) | ||
and ⋯ |
∑n≥1 rnxn = x ∏i≥1 (1 + xi + x2i + ...)ri = x ∏i≥1 1⁄(1 − x)ri
∑n≥0 rn+1xn = ∑n≥1 rnxn−1 = ∏i≥1 1⁄(1 − x)ri
∑n≥1 n rn+1 xn ⁄ ∑n≥0 rn+1 xn
log ∏i≥1 1⁄(1 − x)ri = ∑i≥1 rj log 1⁄(1−xi)
= ∑i≥1 ∑j≥1 ri⁄j xij = ∑k≥1 (∑i | k iri⁄k) xk,
∑k≥1 (∑i | k iri) xk.
∑n≥1 n rn+1 xn = ∑k≥1 (∑i | k iri) xk • ∑m≥0 rm+1 xm
= ∑n≥1 ( ∑k=1n ∑i | k i ri rn−k+1 ) xn,
rn+1 = 1⁄n ∑k=1n ∑i | k i ri rn−k+1 . |
r5 = 1/4 ( 1r1r4 + 1r1r3 + 2r2r3 + 1r1r2 + 3r3r2 + 1r1r1 + 2r2r1 + 4r4r1 )
= 1/4 (4 + 2 + 4 + 1 + 6 + 1 + 2 + 16) = 9
Γ = ΓT = Sym(T) = { one-to-one σ : V→V s.t. uv ∈ E ⇒ σ(u)σ(v) ∈ E },
E := { e = u v, such that u ≠ v, and u'v' ∈ E for some u' ∈ u and v' ∈ v}.
T = | 1 −− | 2 | −− 3 | −− 4 | |
| | | | ||||
5 | 6 |
tn = rn − ½[ ∑ i=1n−1 ri rn−i − rn/2 ] .
½ n + 2 ≤ r ≤ 2n − 4.
qR = qS + (v,1)×(u,1).
qS = qR + (u,1)×(v,1).
hi = (vi,1) • qj.
(vi, hi) = (xi, yi, hi).
hR(v) = (v,1) • qR = (v,1) • qS + (v,1) • (v,1)×(u,1) = (v,1) • qS = hS(v),
hR(w) = (w,1) • qR + (w,1) • ((v,1)×(u,1)) ?<? hS(w) = (w,1) • qS,
meaning:
0 ?>? (w,1) • ((v,1)×(u,1)) = det((w,1), (v,1), (u,1)),