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 multiset number (n multichoose 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 buttoncolor 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 n^{k} = 3^{6}.
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) = 3^{6 }− (3  1) 2^{6} + (3  2) 1^{6}.
Give each position one of 3 kinds of buttons or leave empty, which is like a 4^{th} color denoted by −. Entry #1: f : [6]→{B,W,R,−}. The number is 4^{6}.
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 6^{6} = 6! ; or by entry #3, giving surj(6,6) = 6^{6} − (6  1)5^{6} + (6  2)4^{6} − (6  3)3^{6} + (6  4)2^{6} − (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 n^{k} 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 45degree 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 onetoone 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 n^{th} bin. If this empties the n^{th} 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 n^{th} bin with a single ball.
If the transformation does not empty the n^{th} 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 n^{th} 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 nonempty bins and removes one ball from the third bin, giving either 4 balls in 2 nonempty bins if the third bin is emptied, or otherwise 4 balls in 3 nonempty 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:
1234 1243 1342 2341 1234 1324 1423
4123 3124 2134 1234 3412 2413 2314.
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 nonstandard 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:
1234 1243 1342 2341 1234 1324 2314
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 p_{2}(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 nonempty bins. Answer: p_{3}(100), which has no simple formula.
Nations (A,B,C,D,E,F) split into three exclusive nonempty alliances are like 6 marked balls put into 3 nonempty, exchangeable bins. Entry #9:
{6  3} = ^{1}⁄_{3!} ( 3^{6} – (3  1) 2^{6} + (3  2) 1^{6 }).
Nations (A,B,C,D,E,F) to split into any number of exclusive nonempty 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 (a_{1}, a_{2}) with a_{1 }≥_{ }a_{2} and a_{1 }+ a_{2 }= 3. If a_{2 }= 0, the transformation drops it to give the partition (a_{1}) of type p_{≤1}(3); if a_{2 }> 0, the transformation subtracts 1 from it to give the partition (a_{1}, a_{2 }– 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 (a_{1}) back to (a_{1}, 0) = (a_{1}, a_{2}); and for the third column, it should take (b_{1}, b_{2}) = (a_{1}, a_{2 }– 1) back to (b_{1}, b_{2} + 1) = (a_{1}, a_{2}), 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 onetoone (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 o_{n} be the number of ordered trees with n nodes, so that the above example counts o_{4} = 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].
o_{n} = o_{1}o_{n–1} + o_{2}o_{n–2} + o_{3}o_{n–3} + ... + o_{n–1}o_{1}.
If we define c_{n} = o_{n+1}, this means:
c_{n} = o_{n+1} = o_{1}o_{n} + o_{2}o_{n–1} + o_{3}o_{n–2} + ... + o_{n}o_{1 } = c_{0}c_{n–1} + c_{1}c_{n–2} + c_{3}c_{n–3} + ... + c_{n–1}c_{0}_{ },
which is precisely the same recurrence as for the Catalan numbers C_{n}.
Also we have the same initial value c_{0} = o_{1} = 1 = C_{0}.
The same recurrence starting from the same initial value will produce the same numbers: c_{n} = C_{n}. That is,
o_{n }= c_{n–1 }= C_{n–1}.
Problem: Translate this algorithm into an algebraic formula using the logictoalgebra 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 x^{j}. 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) = (x^{0} + x^{1} + x^{2} + ...) ⋅ (x^{0} + x^{1} + x^{2} + ...) ⋅ ... ⋅ (x^{0} + x^{1} + x^{2} + ...) 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 + x^{2} + ⋅⋅⋅)^{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−k}a_{k} = ^{f(k)(0)}⁄_{k!} = ^{n(n+1)(n+2)...(n+k−1)(1−0)−n−k}⁄_{k!} Now using the risingpower notation n^{k} = 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)) = a_{k} = n^{k} / k! .
This is of course equivalent to ((n  k)) = (k+n−1  k), but this form is neater, and nicely analogous to (n  k) = n^{k} / k! .
Step 0: Let a_{k} 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 x^{1}, gold and silver by x^{2}:
f(x) = (x^{0} + x^{1} + x^{2} + ...) ⋅ (x^{0} + x^{2} + x^{4} + ...) ⋅ (x^{0} + x^{2} + x^{4} + ...) Using z = x^{2} in the known geometric series ^{1}⁄_{(1−z)} = 1 + z + z^{2} + …, we find 1 + x^{2} + x^{4} + … = ^{1}⁄_{(1−x2)}. Hence:
= (1 + x + x^{2} + …)(1 + x^{2} + x^{4} + …)^{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:Followup: 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−x^{2} = (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 negativepower binomial series ^{1}⁄_{(1−x2)3} = ∑_{k≥0} ((3  k)) x^{2k}, 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)) x^{2k} = ∑_{k≥0} ((3  k)) x^{2k} + ∑_{k≥0} ((3  k)) x^{2k+1}
a_{2k} = a_{2k+1} = ((3  k)) = ½(k+2)(k+1).
The answer to our original problem is therefore: a_{20} = a_{2(10)} = ((3  10)) = ½(12)(11) = a_{2k} = 66.
f(x) = 1 + x + 3x^{2} + 3x^{3} + 6x^{4} + 6x^{5} + 10x^{6} + 10x^{7} + 15x^{8} + 15x^{9} + 21x^{10}
+ 21x^{11} + 28x^{12} + 28x^{13} + 36x^{14} + 36x^{5} + 45x^{16} + 45x^{17} + 55x^{18} + 55x^{19} + 66x^{20} + ...
This can be explained combinatorially as follows: to get a total value of 20 euros, we must have an even number of oneeuro coins. Grouping the oneeuros into pairs, we can think of this as 3 kinds of 2euro coins: oneeuro pair, gold twoeuro, silver twoeuro. The ways to choose a multiset 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 a_{k} 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) = (x^{1} + x^{2} + x^{2}) ⋅ … ⋅ (x^{1} + x^{2} + x^{2}) = (x+2x^{2})^{14}.
Factoring and applying the Binomial Theorem:Followup: 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 2^{6} possibilities. Again, this is clear once we know the answer!We want the coefficient of x^{20}, which corresponds to k = 6, i.e. a_{20} = (14  6) 2^{6}. f(x) = x^{14} (1+2x)^{14} = x^{14} ∑_{k=0}^{14} (14  k) (2x)^{k} = ∑_{k=0}^{14} (14  k) 2^{k} x^{k+14}.
f(x)
=
0 + ∑_{k≥1} a_{k−1}x^{k}
+ ∑_{k≥1} kr^{k}x^{k}
=
x∑_{k≥1} a_{k−1}x^{k−1}
+ ∑_{k≥1} kr^{k}x^{k}
=
x f(x) +
^{rx}⁄_{(1−rx)2}.
Followup: 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 + 2r^{2} + ... + kr^{k}), and finding we can cancel all the terms except for kr^{k+2} − (k+1)r^{k+1} + r.
We can also check the formula in special cases. For example, for r = 0 we get a_{k} = 0, as expected. For r = 1, we get a_{k} = 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− x^{3} = −(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:
a_{k} ≅ ^{1}⁄_{(3α2+1)αk+1} ,
Applying the above approximation to k = 10, we get a_{10} ≅ 27.95, whereas the exact value is 28. Not bad!
Let us compare a_{k} to the Fibonacci sequence F_{k}. We can see from the recurrence that a_{k} grows more slowly than F_{k} : the reproduction is more delayed in a_{k}. And indeed, a_{k} ≅ const × 1.47^{k}, whereas we previously showed the approximation F_{k} ≅ const × 1.62^{k}.
f_{k}(x) = ∑_{n≥k} {n  k} x^{n} = ^{xk} ⁄_{(1 − x)(1−2x)…(1−kx) } .
Work out the constants A_{1},..., A_{k} in the partial fraction decomposition:
f_{k}(x) = ^{A1} ⁄_{(1 − x)} + ^{A2} ⁄_{(1 − 2x)} + ... + ^{Ak} ⁄_{(1 − kx)} .
a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ....
=
1 + 1 + x + x^{2} + x^{3} + ...
−2a_{0}x − 2a_{1}x^{2} − 2a_{2}x^{3} − ...
a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ....
=
^{1}⁄_{2 }
+ ^{3}⁄_{2 } + ^{3}⁄_{2 }(2x) + ^{3}⁄_{2 }(2^{2}x^{2}) + ^{3}⁄_{2 }(2^{3}x^{3}) + ...
−a_{0}x − a_{1}x^{2} − a_{2}x^{3} − ...
Clearing denominators in the third way:
a_{0} + a_{1}x + a_{2}x^{2} + a_{3}x^{3} + ....
=
2 − x + 0x^{2} + 0x^{3} + ...
−3a_{0}x − 3a_{1}x^{2} − 3a_{2}x^{3} − ...
2a_{0}x^{2} + 2a_{1}x^{3} + ...
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})(4^{2})(1−4x)^{−5/2}, and:
a_{k} = h^{(k)}(0) / k!  = (^{1}⁄_{2})(^{3}⁄_{2})...(^{2k−3}⁄_{2}) 4^{k−1} / k! 
= (1)(3)(5)...(2k−3) 4^{k−1} / 2^{k−1} k!  
= (1)(3)(5)...(2k−3) 2^{k−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 {C_{n}} ↔^{ops} f(x), we apply the ops correspondence to both sides of the recurrence equation: C_{n+1} = C_{0}C_{n} + C_{1}C_{n−1} + ⋯ + C_{n}C_{0} 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) .
S_{1}⋯⋯S_{k}
↦
(
S' ,
S'_{1}⋯S'_{j−1}S'_{j+1}⋯S'_{k}
)
where
n ∈ S_{j} ,
S' = S_{j}\{n} ⊂ [n−1],
S_{j} = i
and
S'_{1}∪⋯∪S'_{k} = [n−1−i] .
S_{1}S_{2}S_{3} = 1634725 .
We remove S_{2} = {3,4,7} containing n = 7, and we record S' = {3,4}. The remaining set partition is S_{1}S_{3} = 1625, which covers [n] \ S_{2} = {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 S_{1} and S_{3} gives the final set partition S'_{1}S'_{3} = 1423 . The completed transformation is:S_{1}S_{2}S_{3} = 1634725 ↦ (S' , S'_{1}S'_{3}) = ({3,4} , 1423)
log(y) = ∫ ^{1}⁄_{y} dy = ∫ e^{x} dx = e^{x} + c
for some constant c. Solving for y gives y = B^{~}(x) = C exp(e^{x}) for some C = e^{c} > 0. The initial condition B^{~}(0) = B_{0} = 1 forces C = e^{−1}, so that B^{~}(x) = e^{(ex − 1)} = exp(e^{x} − 1).
(n  2) (n−2  2) ⋯ (2  2) = ^{(2m)!}⁄_{(2!)m }.
This is the number of ways to partition the set [n] into m twoelement subsets [n] = S_{1} ∪ ⋯ ∪ S_{m} , where the order of the S_{i}'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,♥)}.
h_{n} = ∑_{i1,...,i4} (n  i_{1}) (n−i_{1}  i_{2}) (n−i_{1}−i_{2}  i_{3}) (n−i_{1}−i_{2}−i_{3}  i_{4})
= ∑_{i1,...,i4} ^{n!}⁄_{(i1! i2! i3! i4!)} ,
where the summation runs over integers i_{1},...,i_{4} ≥ 0 with i_{1} + i_{2} + i_{3} + i_{4} = n. It is easily seen by generalizing [W] Rule 3' (exponential convolution), that this has generating function:h(x) = (∑_{i≥0} ^{xi}⁄_{i!})^{4} = e^{4x . }
B(x) = e^{d(x)} = 1 + d(x) + ^{1}⁄_{2!} d(x)^{2} + ^{1}⁄_{3!} d(x)^{3} + ⋯ ..
n  1  2  3  4  5 
c_{n} / g_{n}  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} x^{2}
+ ^{2}⁄_{3} x^{3}
+ ^{19}⁄_{12} x^{4}
+ ⋯ .
= 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=0}^{k} (−1)^{k−j} (k  j) j^{n}.
B(x) = ^{1}⁄_{e} ∑_{j≥0} ^{ejx}⁄_{j!} = ^{1}⁄_{e} ∑_{j≥0} ∑_{n≥0} ^{(jx)n}⁄_{j!n!} .
B_{n} = ^{1}⁄_{e} ∑_{j≥1} ^{jn}⁄_{j!} .
B_{3} = ^{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 B_{n}? Are n terms enough, or n/2, or √n? If we knew this, it would give a finite formula for B_{n}, 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!} log^{k}(^{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}
(½e^{x})^{k}
=
^{1}⁄_{2}
∑_{k≥0}
(^{1}⁄_{2k})
e^{kx}
=
^{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} a_{n} ^{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 z^{k} = (x + ^{x2}⁄_{2!})^{k}, but this does not seem worth it. Wolfram Alpha gives the x^{10} term of the Taylor series as: (^{1187}⁄_{453600}) x^{10}, so:
Step 1: To find the exponential generating function f(x) = ∑_{n≥0} a_{n} ^{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 − ½x^{2} = (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} a_{n} ^{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 + x^{2}).
Step 2: a_{10} = 10! (^{19093}⁄_{518400}) = 133651.
Step 1: The deck is the same as in part (c), so and d(x) = x + x^{2}. A list of teamswithleader 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 {a_{n}} is the same as the ordinary generating function of the Fibonacci numbers {F_{n+1}}, we get:
^{ an}⁄_{n!}
= F_{n+1}, i.e. a_{n} = n! F_{n+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} D_{n} ^{xn}⁄_{n!} = ∑_{n≥0} D_{n} ^{xn}⁄_{n!} − ∑_{n≥0} D_{n} ^{xn+1}⁄_{n!}
= ∑_{n≥0} D_{n} ^{xn}⁄_{n!} − ∑_{n≥0} (n+1)D_{n} ^{xn+1}⁄_{(n+1)!}
= ∑_{n≥0} D_{n} ^{xn}⁄_{n!} − ∑_{n≥1} n D_{n−1} ^{xn}⁄_{n!}
A = lim_{x→1} (^{e−x}⁄_{(1−x)}) (1−x) = e^{−1}.
D_{n} = n!(1 − ^{1}⁄_{1!} + ^{1}⁄_{2!} ⋯ ± ^{1}⁄_{n!}).
D_{n} ≈ e^{−1}√2πn (^{n}⁄_{e})^{n}.
log_{10}(e^{−1}√2π(100) (^{100}⁄_{e})^{100}) = −log_{10}(e) + ½ log_{10}(2π) + 1 + 100(2 − log_{10}(e)) ≈ 157.5
^{d}⁄_{dx} log f(x) = ^{1}⁄_{f(x)} f '(x),
n a_{n} = ∑_{ i=0}^{n} (n  i) i d_{i} a_{n−i} .
a_{n} = ^{1}⁄_{n} ((n  1)d_{1}a_{n−1} + 2(n  2)d_{2}a_{n−2} + 3(n  3)d_{3}a_{n−3} + ⋯ + n(n  n)d_{n}a_{0}) .
a_{n} = d_{1}a_{n−1} + (n−1  1)d_{2}a_{n−2} + (n−1  2)d_{3}a_{n−3} + ⋯ + (n−1  n−1)d_{n}a_{0} .
x f '(x) = x (x + 2 ^{x2}⁄_{2})' f(x)
n a_{n} = (n  1)d_{1}a_{n−1} + 2(n  2)d_{2}a_{n−2} ,
a_{n} = a_{n−1} + 2(n−1) a_{n−2} .
B_{n} = B_{n−1} + (n−1  1)B_{n−2} + (n−1  2)B_{n−3} + ⋯ + (n−1  n−1)B_{0} .
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 D_{n} = ∑_{ i=2}^{n} (n  i) i! D_{n−i}
D_{n} = (n−1) D_{n−2} + (n−1)^{2} D_{n−3} + (n−1)^{3} D_{n−4} + ⋯ + (n−1)^{n−2} D_{1} + (n−1)! D_{0} .
A = lim_{x→α} R(x) (1 − x/α) = lim_{x→α} ^{(1 − x/α)}⁄_{(2 − ex)}
= lim_{x→α} ^{(− 1/α)}⁄_{(− ex)} = ^{1}⁄_{αeα} = ^{1}⁄_{2log(2)} .
∑_{n≥0} ^{ Rn}⁄_{n!} x^{n} = R(x) ≈ ^{A}⁄_{(1 − x/α)} = ∑_{n≥0} ^{A}⁄_{αn} x^{n} ,
n  5  10  20 
C_{n}  42  16796  6564120420 
^{4n}⁄_{n3/2√π}  52  18708  6.93 × 10^{9} 
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) = e^{d(x)} = exp(x + log ^{1}⁄_{(1−x)}) = ^{ex}⁄_{(1−x)} .
^{an}⁄_{n!} = 1 + ^{1}⁄_{1!} + ^{1}⁄_{2!} + ⋯ + ^{1}⁄_{n!} ,
Also, e^{x2/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} a_{n}x^{n}
=
(x^{0} + x^{1} + x^{2} + ⋯)
(x^{0} + x^{2} + x^{4} + ⋯)
(x^{0} + x^{3} + x^{6} + ⋯)
=
^{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)) x^{n} ,
A = lim_{x→1} f(x) (1−x)^{3} = lim_{x→1} ^{(1−x)3}⁄_{(1−x)(1−x2)(1−x3)} = ^{−6}⁄_{−36} . = ^{1}⁄_{6} .
a_{n} ∼ ^{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)) x^{6m}
+
∑_{m≥0} ((3  m)) x^{6m+1}
+
2 ∑_{m≥0} ((3  m)) x^{6m+2}
3 ∑_{m≥0} ((3  m)) x^{6m+3}
+
4 ∑_{m≥0} ((3  m)) x^{6m+4}
+
5 ∑_{m≥0} ((3  m)) x^{6m+5}
4 ∑_{m≥0} ((3  m)) x^{6m+6}
+
5 ∑_{m≥0} ((3  m)) x^{6m+7}
+
4 ∑_{m≥0} ((3  m)) x^{6m+8}
3 ∑_{m≥0} ((3  m)) x^{6m+9}
+
2 ∑_{m≥0} ((3  m)) x^{6m+10}
+
∑_{m≥0} ((3  m)) x^{6m+11}
+
∑_{m≥0} ((3  m)) x^{6m+12}
a_{6m}
=
((3  m)) + 4((3  m−1)) + ((3  m−2))
a_{6m+1}
=
((3  m)) + 5((3  m−1))
a_{6m+2}
=
2((3  m)) + 4((3  m−1))
a_{6m+3}
=
3((3  m)) + 3((3  m−1))
a_{6m+4}
=
4((3  m)) + 2((3  m−1))
a_{6m+5}
=
5((3  m)) + ((3  m−1))
a_{6m}
=
3m^{2} + 3m + 1
a_{6m+1}
=
(m+1)(3m+1)
a_{6m+2}
=
(m+1)(3m+2)
a_{6m+3}
=
3(m+1)^{2}
a_{6m+4}
=
(m+1)(3m+4)
a_{6m+5}
=
(m+1)(3m+5) .
a_{100} = (16 + 1) (3(16) + 4) = 884.
(1−x)(1−x^{2})(1−x^{3}) f(x) = 1
(1 − x − x^{2} + x^{4} + x^{5} − x^{6}) ∑_{n≥0} a_{n}x^{n} = 1 + 0x + 0x^{2} + ⋯ .
a_{n} − a_{n−1} − a_{n−2} + a_{n−4} + a_{n−5} − a_{n−6} = 0
a_{n} = a_{n−1} + a_{n−2} − a_{n−4} − a_{n−5} + a_{n−6} for n ≥ 1 (from a_{0} = 1).
(1−x^{2})(1−x^{3}) f(x) = ^{1}⁄_{(1−x)}
(1 − x^{2} − x^{3} + x^{5}) ∑_{n≥0} a_{n}x^{n} = 1 + 1x + 1x^{2} + ⋯
a_{n} − a_{n−2} − a_{n−3} + a_{n−5} = 1
a_{n} = a_{n−2} + a_{n−3} − a_{n−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} a_{n}x^{n}
=
1 +
(x^{1} + x^{2} + x^{3})
+ (x^{1} + x^{2} + x^{3})^{2}
+ (x^{1} + x^{2} + x^{3})^{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}) x^{n} ,
A = lim_{x→α} f(x) (1 − x/α) = lim_{x→α} ^{(1 − x/α)}⁄_{(1−x−x2−x3)}
= ^{(−1/α)}⁄_{(−1−2α−3α2)} = ^{1}⁄_{α(1+2α+3α2)} .
a_{n} ∼ ^{A}⁄_{αn} = ^{1}⁄_{αn+1(1+2α+3α2)} .
(1−x−x^{2}−x^{3}) f(x) = 1
(1 − x − x^{2} − x^{3}) ∑_{n≥0} a_{n}x^{n} = 1 + 0x + 0x^{2} + ⋯ .
a_{n} − a_{n−1} − a_{n−2} − a_{n−3} = 0
a_{n} = a_{n−1} + a_{n−2} + a_{n−3} for n ≥ 1 (from a_{0} = 1).
D =
{
① ,
①→② ,
②→① ,
①→②→③ ,
①→③→② ,
②→①→③ ,
②→③→① ,
③→①→② ,
③→②→①
}
g(x) = ℓ(x) = ^{1}⁄_{(1 − d(x))} = ^{1}⁄_{(1−x−x2−x3)} .
D = { ① , ①② , ①②③ }
c_{100} = 11527937348312713865082241287737153907730362053400425345132475796235815534719539623297472916358562840576
λ = (λ_{1}, λ_{2},..., λ_{k}) where λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{k} > 0 and λ_{1} + λ_{2} + ⋯ + λ_{k} = n.





φ(x) = ∑_{n≥0} p(n)x^{n} = ∏_{i≥1} ^{1}⁄_{(1−xi)} .
^{1}⁄_{φ(x)} = ∏_{i≥1} (1−x^{i}) = 1 + ∑_{m≥1} (−1)^{m}(x^{½m(3m−1)} + x^{½m(3m+1)}).
a_{n} =
#{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).
r_{n+1} = ^{1}⁄_{n} ∑_{k=1}^{n} ∑_{i  k} i r_{i} r_{n−k+1} .
r_{n} n! =^{??} n^{n−1},
r_{5} = ((r_{1}  4)) + ((r_{1}  2)) ((r_{2}  1)) + ((r_{2}  2)) + ((r_{1}  1)) ((r_{3}  1)) + ((r_{4}  1))
= 1 + 1 + 1 + 2 + 4 = 9 .
T =  ®−−  ®  −−®  −−O  
  
® 
r_{n+1} = ∑_{k} ∏_{i≥1} ((r_{i}  k_{i})) = ∑_{k} ((r_{1}  k_{1})) ((r_{2}  k_{2})) ((r_{3}  k_{3})) ⋯
r_{5} = ((r_{1}  4)) + ((r_{1}  2)) ((r_{2}  2)) + ((r_{1}  1)) ((r_{3}  1)) + ((r_{4}  1)) .
T_{1}  T_{2}  T_{3}  T_{4}  T_{5}  T_{6}  
Sym(T)  2  2  2  (4)(2) = 8  3! = 6  5! = 60 
p_{T}  3  5  4  2  4  2 
q_{T}  2  4  3  1  3  1 
T  P_{3}  P_{5}  P_{4}  P_{2}  P_{4}  P_{2} 
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}. 
L_{a,c} = {x ∈ R^{2} 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.
P_{1} = (0,1)(0,2),(1,2),(2,2),(3,2) and P_{2} = (0,1),(1,1),(2,1),(3,1)(3,2).
P_{1} = (1,1)(2,1),(3,1),(3,0),(2,0) and P_{2} = (1,1),(0,1),(0,2).
P  pyram  prism  antipr  bipyr  trapezo  dodeca  icosa 
κ(G)  3  3  4  4  3  3  5 
δ(G)  3  3  4  4  3  3  5 
PE(x_{1}) = −∫_{0}^{x1}F(x) dx .
F(x) = −(x−a_{1}) − (x−a_{2}),
PE(x_{1},y_{1}) = −∮ F(r) • dr ,
F_{i} = ∑_{j ∈ N(i)} (v_{j} − v_{i}) = (0, 0) for i = 1,...,k,
deg(v_{i})  if i = j,  
ℓ_{ij}  =  −1  if ij ∈ E 
0  otherwise. 
b_{i} = ∑_{j ∈ XN(i)} x_{j} , c_{i} = −∑_{j ∈ XN(i)} y_{j} ,
L • x = b and L • y = c,
(x_{1}, y_{1}) = (^{1}⁄_{3}, ^{1}⁄_{2√3} ), (x_{2}, y_{2}) = (^{13}⁄_{24}, ^{1}⁄_{4√3} ), (x_{3}, y_{3}) = (^{7}⁄_{24}, ^{1}⁄_{4√3} ).


z = a_{j}x + b_{j}y + c_{j} .
h_{v} = q_{R} • (v,1) = q_{S} • (v,1)
Da(x) = a'(x) = lim_{h→0} ^{(a(x+h) − a(x))}⁄_{h} = lim_{h→0} ^{(a(x) − a(x−h))}⁄_{h}
Δ^{+}a_{n} = ^{(an+1−an)}⁄_{1} = a_{n+1} − a_{n}.
Δ^{−}a_{n} = ^{(an−an−1)}⁄_{1} = a_{n} − a_{n−1}.
Σa_{n} = ∑_{i=0}^{n} a_{i}.
Δ(Σa_{n}) = a_{n} and Σ(Δa_{n}) = a_{n} .
(a_{n})_{n≥0} ↔^{ops} f(x) = ∑_{n≥0} a_{n}x^{n}.
Δ^{+}Δ^{−}a_{n} = Δ^{−}Δ^{+}a_{n} = a_{n+1} + a_{n−1} − 2a_{n} for n ≥ 1.
n^{k} = ∑_{i=0}^{k} {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) + x^{2} f(x).
(1 − x − x^{2}) ∑_{n≥0} w_{n}x^{n} = ∑_{n≥0} w_{n}x^{n} − ∑_{n≥0} w_{n}x^{n+1} − ∑_{n≥0} w_{n}x^{n+2} = 1 + x .
f(x) = ^{A}⁄_{(1 − x/α)} + ^{B}⁄_{(1 − x/β)}
A = lim_{x→α} (1 − x/α) f(x) = lim_{x→α} ^{(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) = a_{0} + a_{1}x + a_{2}x^{2} + .... = ∑_{k≥0} a_{k} x^{k} .
Logic  choose an object of any size k ≥ 0  ⇔  basic choice adding size m  or  and 
Algebra  f(x) = ∑_{k≥0} a_{k}x^{k}  =  x^{m}  +  × 
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) .
S_{1} ∪ ⋯ ∪ S_{k} = [n].
The weight of hand is the total weight of its cards: wt(H) = n = wt(C_{1}) + ⋯ + wt(C_{k}).h_{n} = #{hands H with wt(H) = n}
and its exponential generating function: h(x) = ∑_{n≥0} h_{n} ^{xn}⁄_{n!} .










C_{1} = ({1},ℂ) = 
 C_{2} = ({1,2},ℙℙ) = 

h(x) = exp d(x) = e^{d(x)}
We illustrate this formula and its proof for the toy example.b_{n} = b_{2m} = ^{n!}⁄_{m!(2!)m} ,
giving the exponential generating function:∑_{m≥0} b_{2m}(^{x2m}⁄_{(2m)!}) = ∑_{m≥0} ^{(2m)!}⁄_{m!(2!)m (x2m⁄(2m)!) }
= ∑_{m≥0} ^{1}⁄_{m!} (^{x2}⁄_{2!})^{m} = exp(^{x2}⁄_{2!}) = e^{x2 / 2!}.
h_{n} = ∑_{i=0}^{n} (n  i) (1) b_{n−i} .
This is precisely the exponential convolution formula, so the handenumerator 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} h_{n}^{xn}⁄_{n!} . = e^{x} • e^{x2/2!} = exp(x + ^{x2}⁄_{2!}) = exp d(x).
B(x) = e^{d(x)} = e^{ex−1} = exp(e^{x} − 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 = {C_{1}, C_{2}, C_{3}}, where C_{1} = {{3},①), C_{2} = ({1,4}, ①−②), C_{3} = {{2,5,6}, ①−③−②}.g(x) = e^{c(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) = e^{d(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)x^{n} = ∏_{i≥1} ^{1}⁄_{(1−xi)} .
^{1}⁄_{φ(x)} = ∏_{i≥1} (1−x^{i}) = 1 + ∑_{m≥1} (−1)^{m}(x^{½m(3m−1)} + x^{½m(3m+1)}).
a_{n} =
#{partitions of n into an even number of distinct parts}
−
#{partitions of n into an odd number of distinct parts}.
T_{1,1} = ®, T_{2,1} = ®−−O, T_{3,1} = ®−−O−−O T_{3,2} = O−−®−−O.
Choose T  ⇔  (root) and (0 T_{1,1}'s or 1 T_{1,1}'s or 2 T_{1,1}'s or ⋯) 
and (0 T_{2,1}'s or 1 T_{2,1}'s or 2 T_{2,1}'s or ⋯)  
and (0 T_{3,1}'s or 1 T_{3,1}'s or 2 T_{3,1}'s or ⋯)  
and (0 T_{3,2}'s or 1 T_{3,2}'s or 2 T_{3,2}'s or ⋯)  
and ⋯ 
∑_{n≥1} r_{n}x^{n} = x ∏_{i≥1} (1 + x^{i} + x^{2i} + ...)^{ri} = x ∏_{i≥1} ^{1}⁄_{(1 − x)ri}
∑_{n≥0} r_{n+1}x^{n} = ∑_{n≥1} r_{n}x^{n−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} r_{j} log ^{1}⁄_{(1−xi)}
= ∑_{i≥1} ∑_{j≥1} ^{ri}⁄_{j} x^{ij} = ∑_{k≥1} (∑_{i  k} ^{iri}⁄_{k}) x^{k},
∑_{k≥1} (∑_{i  k} ir_{i}) x^{k}.
∑_{n≥1} n r_{n+1} x^{n} = ∑_{k≥1} (∑_{i  k} ir_{i}) x^{k} • ∑_{m≥0} r_{m+1} x^{m}
= ∑_{n≥1} ( ∑_{k=1}^{n} ∑_{i  k} i r_{i} r_{n−k+1} ) x^{n},
r_{n+1} = ^{1}⁄_{n} ∑_{k=1}^{n} ∑_{i  k} i r_{i} r_{n−k+1} . 
r_{5} = ^{1}/_{4} ( 1r_{1}r_{4} + 1r_{1}r_{3} + 2r_{2}r_{3} + 1r_{1}r_{2} + 3r_{3}r_{2} + 1r_{1}r_{1} + 2r_{2}r_{1} + 4r_{4}r_{1} )
= ^{1}/_{4} (4 + 2 + 4 + 1 + 6 + 1 + 2 + 16) = 9
Γ = Γ_{T} = Sym(T) = { onetoone σ : 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 
t_{n} = r_{n} − ½[ ∑_{ i=1}^{n−1} r_{i} r_{n−i} − r_{n/2} ] .
½ n + 2 ≤ r ≤ 2n − 4.
q_{R} = q_{S} + (v,1)×(u,1).
q_{S} = q_{R} + (u,1)×(v,1).
h_{i} = (v_{i},1) • q_{j}.
(v_{i}, h_{i}) = (x_{i}, y_{i}, h_{i}).
h_{R}(v) = (v,1) • q_{R} = (v,1) • q_{S} + (v,1) • (v,1)×(u,1) = (v,1) • q_{S} = h_{S}(v),
h_{R}(w) = (w,1) • q_{R} + (w,1) • ((v,1)×(u,1)) ^{?}<^{?} h_{S}(w) = (w,1) • q_{S},
meaning:
0 ^{?}>^{?} (w,1) • ((v,1)×(u,1)) = det((w,1), (v,1), (u,1)),