MTH 481
Old Assignments
Spring 2016
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 1 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.
1b. This is a list of 3 students from the 6, with no repeats. We can choose the president to be any of the 6, the vice-president from the remaining 5, etc., so the number of possibilities is 63 = 6×5×4 =120.
1c. Let S be the set of 6 students. For the first problem, let A = { (a,b,c,d,e,f) s.t. {a,b,c,d,e,f} = S }; that is, the set whose elements are lists (a,b,c,d,e,f) which, when considered as sets {a,b,c,d,e,f}, make the full set of students. For the second problem, let A = { (a,b,c) s.t. a,b,c ∈ S and a≠b, a≠c, b≠c }; that is, the set whose elements are triples of distinct elements of S.
2a. The first digit can be 1,...,9, the rest can be 0,1,...,9, so there are 9×10×10×10 = 9000.
2b. The first digit can be 1,...,9, the second can be 0,1,...,9 but different from the first digit, etc., so there are 9×9×8×7 = 4536.
2c. 4536/9000, a bit over 50%.
3a. A result is a list of 10 heads or tails, so the possibilities are 210 = 1024. There is only one way to get all heads, so the probability is 1/1024.
3b. There is 1 way to get no tails and 10 ways to get exactly one tail, so the probability is 11/1024, about 1%.
3c. This is the complement of 3(b), all lists of 10 tosses which do not contain at most one tail. Thus the probability of this case is: (1024−11) / 1024 = 1 − 11/1024 .
4a. We have A∪B = {a,b,c}, A∩B = {b}, A\B = {a}, A×B = {(a,b), (a,c), (b,b), (b,c)}
4b. A has 4 subsets {a,b}, {a}, {b}, {}. B has 4 subsets {b,c}, {b}, {c}, {}. The set A×B has 16 subsets, for example {(a,b), (b,b), (b,c)}. Can you find a general rule predicting how many subsets a set will have?
4c. T = A3 = A×A×A.
4d. R3 = R×R×R = {(x,y,z) s.t. x,y,z ∈ R}, the set of possible coordinates for the points of space.
4e. Usually, no. S×T is a set whose elements are pairs (s,t), so no element s∈S can be an element of S×T. However, if S = {}, the nullset with no elements, then S×T = {} also has no elements, and S ⊂ S×T. Also, we might manage it for some weird sets of inifinite lists.
1a. Basic Problem 3: Choose a set of 5 out of 20. Ans: (20 | 5) = 205 / 5! = 20×19×18×17×16 / 5×4×3×2 = 15504. Try computing a few of these on a calculator, then on a spreadsheet using the FACTORIAL and/or BINOMIAL functions.
1b. First choose 5 from 20, then 5 from the remaining 15. Ans: (20 | 5) (15 | 5) = 46558512.
2. A list of 4 increasing digits corresponds to a set of 4 digits chosen from {1,...,9}, since a set (without order) can always be written in increasing order. For example {2,3,5,9} corresponds to 2359. Ans: (9 | 4) = 94/4! = 126.
3a. A hand like {6♠, 6♥, 3♦, 8♠, J♥} corresponds to
the following choices: one face value (6) for the pair from the possible 13, and a set of 3 face values {3,8,J} from the remaining 12; then a set of two suits {♠,♥} for the pair from the 4 suits, and a list of suits (♥,♦,♠) for the 3 distinct face values.
Ans: 13 (4 | 2) (12 | 3) 43 = 1098240.
Note: The suits for the pair are interchangeable, which is why they form a set. Order matters for the suits of the other 3 cards, the suits for the lowest, middle, and highest face values: changing the order gives a different hand. Thus, these 3 suits form a list.
3b. A hand like {6♠, 6♥, J♦, J♥, 8♠} corresponds to
the following choices: a set of two face values {6,J} from the possible 13,
then another face value (8) from the remaining 11;
then a set of two suits {♠,♥} from 4 for the smaller pair and two suits {♦,♥} for the larger pair, and finally a suit ♠ for the last card.
Ans: (13 | 2) (13−2) (4 | 2) (4 | 2) 4 = 123552.
Note: The choice of face values for the two pairs is a set {6,J} = {J,6}, since 6,6,J,J is the same two pairs as J,J,6,6.
3c. Choose a face value for the triple, then a different one for the pair; then choose a set of 3 suits and a set of 2 suits.
Ans: 13 (13−1) (4 | 3) (4 | 2) = 3744.
Note: The choice of face values is a list like (6,J) ≠ (J,6), since 6,6,6,J,J is a different full house from J,J,J,6,6.
3d. Choose the low face-value of the straight: A or 2 or 3 or...or 10, then choose the 5 suits arbitrarily, but exclude all suits the same (4 cases). Ans: 10 (45 - 4) = 10200.
4. Of the 15 steps, choose which 5 are north (the other 10 must be east). Ans: (15 | 5) = 3003.
5a. Given a lineup of balls, record the positions of the black balls. The example • • • • • • • • corresponds to the set {3,5,6}, since there is a black ball in the 3rd, 5th, and 6th positions. This gives a 1-to-1 correspondence between the ball lineups and 3-element subsets of {1,2,...,8}. Ans: (8 | 3) = 56.
5b. Think of the 5 red balls as having 6 spaces between them (counting the two end spaces), and choose which 3 of these spaces is occupied by a black ball. Ans: (6 | 3) = 20.
2a. First choose 5 from 20, then 5 from the remaining 15, then 5 from the remaining 10, leaving 5 for the last team. Ans: (20 | 5) (15 | 5) (10 | 5) = 11732745024 . (I got this from Wolfram Alpha, which understands a command like binomial(20,5).) This is the same as splitting the 20 players into four subsets of size 5, so it is the multinomial coefficient (20 | 5,5,5,5).
2b. This is HW 1/13 #1b: (20 | 5) (15 | 5). Choosing teams A and B leaves 10 students in a third set, so this is the same as (20 | 5,5,10).
2c. To see that the above answers give the formula, write the choose numbers as: (n | k) = n! / k! (n−k)!. Then in 1b, we see by cancellation that:
3. Ans: ((4 | 10)) = (4+10−1 | 10) = 286.
4. A number like 2556 corresponds to a multiset {2,5,5,6}, with 4 objects of 9 possible kinds. Ans: ((9 | 4)) = (9+4−1 | 4) = 495.
5a. A solution like (a,b,c) = (4,5,1) correpsonds to a multiset {1,1,1,1,2,2,2,2,2,3}, in which there are 4 ones, 5 twos and 1 three. Ans: ((3 | 10)) = (12 | 10) = (12 | 2) = 66.
5b. A configuration is determined by the triple (d,m,s), the number of defenders, midfielders, and strikers, with d+m+s = 10. Ans: ((3 | 10)) = 66.
5c. Since 1 goalie, 2 defenders, 2 midfielders, 2 strikers are fixed, the remaining 4 members are determined by (d,m,s) with d+m+s = 4. Ans: ((3 | 4)) = (6 | 4) = 15.
1b. Lists of 10 independent entry grades, each with 5 choices. Product Principle: 510
1c. Multi-sets of 10 grades of 5 kinds (with repeats). Requiring increasing order is the same as saying order is irrelevant, since switching the order does not give a new case to count. Basic Problem #4: ((5 | 10)) = (5+10−1 | 10) = (14 | 10) = (14 | 4) = 14×13×12×11 / 4×3×2.
1d. Sets of 3 names out of 10 (order irrelevant). Basic Problem #3: (10 | 3).
1e. Lists of 3 distinct names from 10 (pen-winner, pencil-winner, skittles-winner). Basic Problem #2: 103.
1f. Lists of 3 independent names with 10 choices for each. Product Principle: 103.
1g. The Position Transformation shows this is (10 | 6) = 210.
1h. An arrangement of rings is a list of 10 whole numbers adding up to 6. By the Multiplicity Transform, this corresponds to multi-sets of 6 elements of 10 kinds (think of each ring as a choice of finger 1,2,...,10, with repetition allowed). Ans: ((10 | 6)) = (15 | 6) = 5005.
2a. See HHM p. 139, or type "Pascal's triangle" into Wolfram Alpha.
2b. The triangle is more efficient for computing a whole row, while the formula is better if you only need one value.
2c. The formula (n | k) = n! / k!(n−k)! is very inefficient, since n! is usually much larger than nk. However, this formula is useful for seeing the properties of (n | k), as in the next problem.
2d. There is a left-right mirror symmetry in the entries, which can be proved by noting that (n | k) = n! / k!(n−k)! whereas:
2e. See HHM p. 139.
2f. (n | 0) + (n | 1) + ... + (n | n) = 2n for all n, which follows from the Binomial Theorem next time.
2g. (n | 0) − (n | 1) + ... ± (n | n) = 0 for all n ≥ 1, which also follows from the Binomial Theorem.
3a. Imitate the table at the bottom of Notes 1/11, Position Transformation.
3b,c,d. There are ((3 | 4)) = (6 | 4) = (6 | 2) = 15 multi-sets M, each corresponding to a multiplicity list (a,b,c), a bins-and-beans diagram, and a position set S (see Notes 1/11, Multi-sets). They are:
M | {1,1,1,1} | {1,1,1,2} | {1,1,1,3} | {1,1,2,2} | {1,1,2,3} | {1,1,3,3} | {1,2,2,2} | {1,2,2,3} | {1,2,3,3} | {1,3,3,3} | {2,2,2,2} | {2,2,2,3} | {2,2,3,3} | {2,3,3,3} | {3,3,3,3} |
(a,b,c) | (4,0,0) | (3,1,0) | (3,0,1) | (2,2,0) | (2,1,1) | (2,0,2) | (1,3,0) | (1,2,1) | (1,1,2) | (1,0,3) | (0,4,0) | (0,3,1) | (0,2,2) | (0,1,3) | (0,0,4) |
B&B | OOOOII | OOOIOI | OOOIIO | OOIOOI | OOIOIO | OOIIOO | OIOOOI | OIOOIO | OIOIOO | OIIOOO | IOOOOI | IOOOIO | IOOIOO | IOIOOO | IIOOOO |
S | {1,2,3,4} | {1,2,3,5} | {1,2,3,6} | {1,2,4,5} | {1,2,4,6} | {1,2,5,6} | {1,3,4,5} | {1,3,4,6} | {1,3,5,6} | {1,4,5,6} | {2,3,4,5} | {2,3,4,6} | {2,3,5,6} | {2,4,5,6} | {3,4,5,6} |
Similarly,
2a. The transformation is defined by two cases: if |S'| = k, then S = S'; if |S'|= k−1, then S = S'∪{n}. We easily see that this reverses the previous transformation, and vice versa.
2b. Here we use 3 rows instead of columns.
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} |
2a. The Position Transformation shows this is (10 | 6) = 210.
2b. An arrangement of rings is a list of 10 whole numbers adding up to 6. By the Multiplicity Transform, this corresponds to correspond to multi-sets of elements of 10 kinds (think of each ring as a choice of finger 1,2,...,10, with repetition allowed). Ans: ((10 | 6)) = (15 | 6) = 5005.
2c. To count B1, begin by putting 2 rings on the right thumb, then distribute the remaining 4 rings on any of the 10 fingers (including extras on the right thumb). Thus, |B1| = ((10 | 4)), and the same for |B2|. Ans: ((10 | 6)) − ((10 | 4)) − ((10 | 4)) + ((10 | 2)).
2d. Since there are only 6 rings total, we cannot have an intersection of more than 2 subsets Bi∩Bj . Ans:
2e. Write an arrangement by recording which finger has D, which has E, which has R, etc. Then the arrangements correspond to lists of 6 distinct numbers from {1,2,...,10}. Ans: 106.
2f. PIE with A = {arrangements of D,E,R,S,T,C on 10 fingers, at most 1 per finger} and
B1 = {arrangements with D on left thumb},
B2 = {arrangements with D on right thumb},
B3 = {arrangements with E on left thumb},
B4 = {arrangements with E on right thumb}.
Ans: 106 − 4×95 + 2×84.
Positive counting: There are 8 choices for D, 7 for E, 8 for R, 7 for S, 6 for T, and 5 for C. Ans: 8×7×84.
3a. A job roster is a list of all the jobs in some order. Ans: 6! .
3b. Note |B1| = 5! since we assign the remaining 5 jobs to 5 people. Similarly for the rest of the terms in PIE formula. Ans: 6! − 3×5! + 3×4! -3!
3c. PIE with A = {all job rosters}, B1 = {P1 doing J1}, B2 = {P1 doing J2}, B3 = {P2 doing J3}, B4 = {P2 doing J4}.
Then |B1| = 1×5×4×3×2×1, figuring the number of choices for Person 1, Person 2, etc. Similarly for |B2| , |B3|, |B4|.
Also |B1∩B3| = 1×1×4×3×2×1 , and similarly for |B1∩B4|,
|B2∩B3|, |B2∩B4|, but |B1∩B2| = |B3∩B4| = 0. All triple intersections are empty.
Ans: 6! − 4×5! + 4×4!
2. PIE: A = {sets of 5 from 10}, B1 = {sets containing 1,2}, B2 = {sets containing 2,3}, B3 = {sets containing 3,4}. Clearly |A| = (10 | 5), and |Bi| = (8 | 3) since if two guests are fixed, this leaves 5−2 more to choose from 10−2. Similarly |B1∩B2| = (7 | 2), etc. Ans: (10 | 5) − (3 | 1)(8 | 3) + (7 | 2) + (6 | 1) + (7 | 2) − (6 | 1) = 126.
3a. PIE:
3b. PIE:
4a. In the original formula for dn, write out (n | k) = n! / k!(n−k)! ; then factor out n! and cancel (n−k)! in each term to get the desired formula.
4b. For both cases the answer is dn/n! ≅ 0.36788 up to many digits of accuracy.
4c. From the formula, the probabability dn/n! = 1 − 1 + 1/2! − 1/3! + ... + (−1)n/n!, which is the first n terms of the formula for e−1 = 1/e. Since the Taylor series converges for all x, this approaches 1/e as n→ ∞.
= 99 − 50 − 33 − 20 − 14 + 16 + 10 + 7 + 6 + 4 + 2 − 3 − 2 − 1 − 0 + 0 = 21.
Adding 4 to account for 2,3,5,7 themselves, this gives 25 primes less than 100.
1b. The 25 primes less than 100 are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 .
1a. (x+y)3 = (xx + xy + yx + yy)(x + y) = xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy.
term | xxx | xxy | xyx | yxx | xyy | yxy | yyx | yyy |
S | {} | {3} | {2} | {1} | {2,3} | {1,3} | {1,2} | {1,2,3} |
Thus, there are clearly (3|1) terms which are algebraically equal to x2y, and (3|2) terms equal to xy2.
1b. To get (x+y)4, start with the previous result and multiply (xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy)(x + y) to get 16 terms. Check these off one by one when you put them in the table. The term x4 comes from the set {}, the terms algebraically equal to x3y come from the sets with 1 element, the terms equal to x2y2 come from the sets with 2 elements, etc.
2a. The final expanded expression has terms (outcomes) corresponding to the multisets as follows:
term | 0A & 0B | 0A & 1B | 0A & 2B | 1A & 0B | 1A & 1B | 1A & 2B | 2A & 0B | 2A & 1B | 2A & 2B |
M | {} | {B} | {B,B} | {A} | {A,B} | {A,B,B} | {A,A} | {A,A,B} | {A,A,B,B} |
2b. Multiply out (x0 + x1 + x2)2 to get:
2c. (1 + (x+x2))2 = 1 + 2(x+x2) + (x+x2)2 = 1 + 2x + 2x2 + (x2 + 2xx2 + x4) = 1 + 2x + 3x2 + 2x3 + x4.
2a. f(x) = (1+x+...+x10) (1+x+...+x8) (1+x+...+x11)
2b. f(x) = (1+x2+x4+x6+x8+x10) (x+x3+x5+x7) (x2+x3+x5+x7+x11)
2c. f(x) = x2 (x5+x6+x7+x8) (1+x+x2+x3+x4)
3a. f(x) = 1 + (52 | 1)(x+x2) + (52 | 2)(x+x2)2 + (52 | 3)(x+x2)3 + (52 | 4)(x+x2)4 + (52 | 5)(x+x2)5 + ...
We want to extract the x5 terms. Now (x+x2)m has lowest term xm, highest term x2m, so we only need to look at:
3b. In the expression a5 = (52 | 3)(3 | 2) + (52 | 4)(4 | 1) + (52 | 5)(5 | 0), the last term (52 | 5) clearly counts 5-card hands with no repeated cards from the 52. The middle term (52 | 4)(4 | 1) means choose 4 distinct cards from 52, then choose one of them to repeat. The term (52 | 3)(3 | 2) means choose 3 distinct cards from 52, then choose 2 of them to repeat. This covers all possibilities of 0,1, or 2 repeated cards.
1b. f (k)(x) = 10k(1+x)10−k since (1+x)' = 1. Thus (10 | k) = ak = f (k)(0) / k! = 10k / k!. This is not really a new formula, but a way to get the old formula purely through algebra, without reasoning much about sets.
1c. A function which is badly behaved near x = 0 might not have a Taylor series. For example, f(x) = 1/x has a vertical asymptote, and cannot be approximated by polynomials. Also, f(x) = |x| is not differentiable at x = 0, we cannot apply the formula for ak, and there is no Taylor series. In fact, no polynomial function looks like |x| very close x=0, since every polynomial has a smooth graph, whereas the graph of |x| has a corner.
1d. f (k)(x) = ex, so f (k)(0) = 1. Hence ak = 1 / k! and ex = 1 + x + x2 / 2! + x3 / 3! + .... This converges for all x, and so a finite number of terms give an approximation to ex.
1e. f (k)(x) = k! (1−x)−(k+1), so ak = k! / k! = 1 and 1/(1−x) = 1 + x + x2 + x3 + ..., an infinte geometric series, which converges for |x| < 1.
1f. sin(x) = x − x3/3! + x5/5! − x7/7! + ...
1g. sin(π/6) = 0.5. The polynomial p(x) = x − x3/3! + x5/5! gives p(π/6) = 0.48, which is pretty close. The point of the Taylor polynomial is that it computes a good approximation of sin(θ) for any given angle θ (provided θ is not too large), for which there is no exact answer.
2a. 1/(1−ax) = 1 + (ax) + (ax)2 + (ax)3 + ... = 1 + ax + a2x2 + a3x3 + ...
2b. 1/(x+b) = 1 / b(1−(−x/b))
= 1/b (1 − x/b + x2/b2 − x3/b3 + ...)
= 1/b − x/b2 + x2/b3 − x3/b4 + ...
2c. We know 1 / (1-x) = ∑k xk.
Differentiating both sides gives: 1/(1−x)2
= ∑k≥1 k xk−1. Hence
x / (1−x)2 = ∑k≥1 k xk
2d. 0.11111... = 1/10 + (1/10)2 + (1/10)3 + ... = − 1 + 1/(1 − 1/10) = 1/9.
2e. The decimal is 10−nD (1 + 10−n + (10−n)2 + ...) = 10−nD / (1 − 10−n) = D / (10n − 1). Example: 0.325325... = 325/999.
3. Step 1: (any outcome of 10 tosses) ⇔ (T1 or H1) and ...
and (H10 or H10), where Ti means the ith toss is heads,
Hi means the ith toss is tails.
We translate Ti into x0 because a tail adds 0 to the number of heads; and we translate Hi into x1, giving:
f(x) = (x0 + x1)10
= (1 + x)10.
Step 2: Taylor's Formula in #1b above gives:
ak = 10k⁄k! = (10 | k).
The number of outcomes of 10 tosses is 210 by the Product Principle, which is a simplified version of our computation of f(x) with x = 1. The probability of k heads is thus (10 | k) / 210.
The result ak = (10 | k) is explained combinatorially by the Position Transform (Notes 1/20): each outcome with k heads is equivalent to the k-element set of positions of the k heads out of the 10 possible positions.
4. Step 0: Let ak count the possible k-card hands from a triple deck.
Step 1: For each distinct card C, we have the choice (0C or 1C or 2C or 3C). For the 52 distinct cards, this produces f(x) = (1+x+x2+x3)52
Step 2: Use the Binomial Theorem to expand:
= (1+x)52(1+x2)52,
= ( ∑52k=0 (52 | k) xk ) ( ∑52j=0 (52 | j) x2j )
so a5 = (52 | 5) + (52 | 3)(52 | 1) + (52 | 1)(52 | 2).
This must have a combinatorial explanation, corresponding to three cases
with a product principle for each, but it is not obvious just how to do this.
Once again, Generating Functions substitute algebra for fairly subtle combinatorial thinking.
1b. Step 0: ak = ((10 | k)) = # multi-sets M with k elements of n kinds.
Step 1: Construct all multi-sets M by an algorithm based on the Product Principle:
1c. The case of general n is just the same, giving the formulas (n | k) = nk / k!
and ((n | k)) = nk / k! .
An interesting algebraic parallel, which only came out with our use of the Generating Function Method!
2a. Geometric series 1/(1−z) = 1 + z + z2 + ... with z = x4, so f(x) = 1 + x4 + x8 + x12 + ... = ∑k≥0 x4k , and a4k = 1, all other am = 0.
2a. Geometric series 1/(1−z) = 1 + z + z2 + ... with z = x4, so f(x) = 1 + x4 + x8 + x12 + ... = ∑k≥0 x4k , and a4k = 1, all other am = 0.
2b. Binomial with negative exponent: f(x) = ∑k≥0 ((4 | k)) xk, so ak = ((4 | k)) = (k+1)(k+2)(k+3)/6 .
2c. Binomial with negative exponent: f(x) = ∑k≥0 ((2 | k)) x2k, so a2k = ((2 | k)) = k+1, am = 0 for m odd.
2d. f(x) = x2 (1 + ((4 | 1))x + ((4 | 2))x2 + ...) = ((4 | 0))x2 + ((4 | 1))x3 + ((4 | 2))x4 + .... = ∑k≥2 ((4 | k−2)) xk, so ak = ((4 | k−2)) = (k−1)k(k+1)/6.
2e. f(x) = (5−x) ∑k≥0 ((2 | k)) xk = ∑k≥05 ((2 | k)) xk − ∑k≥0 ((2 | k)) xk+1
= ∑k≥05 ((2 | k)) xk − ∑k≥0 ((2 | k−1)) xk = ∑k≥0 [5 ((2 | k)) − ((2 | k−1))] xk ,
so ak = 5 ((2 | k)) − ((2 | k−1)) = 5(k+1) − k = 4k + 5.
3a. This follows just from multiplying out and cancelling. Alternatively, you can deduce it from (1−xn) / (1−x) = 1 + x + x2 + ... + xn−1 (the finite geometric series summation from an old HW), with x = b/a, after clearing denominators.
3b. Use (1+x)(1−x) = 1−x2 to massage the denominator into the form 1 / (1−x2)2. Then use the known series formula: 1 / (1−z)2 = ∑k≥0 ((2 | k))zk, with z = x2.
= (1+x) / (1−x2)2 = (1+x) ∑k≥0 ((2 | k))(x2)k
= [((2|0)) + ((2|1))x2 + ((2|2))x4 + ...] + [((2|0))x + ((2|1))x3 + ((2|2))x5 + ...]
Thus a2j = a2j+1 = ((2 | j)) = j+1.
3c. Use (1+x+x2)(1−x) = 1−x3 to massage the denominator into the form 1 / (1−x3)2. Then use the known series formula: 1 / (1−z)2 = ∑k≥0 ((2 | k))zk, with z = x3.
= (1+x+x2) / (1−x3)2 = (1+x+x2) ∑k≥0 ((2 | k))(x3)k
= [((2|0)) + ((2|1))x3 + ((2|2))x6 + ...] + [((2|0))x + ((2|1))x4 + ((2|2))x7 + ...] + [((2|0))x2 + ((2|1))x5 + ((2|2))x8 + ...]
Thus a3j = a3j+1 = a3j+2 = ((2 | j)) = j+1.
4a. Step 1: (choose a handful of change of any value) ⇔ (0P or 1P or ...) and (0N or 1N or ...)
is translated algebraically as:
4b. A handful of pennies and nickels worth k = 5j cents is determined by how many nickels: either 0 or 1 or ... or j−1 or j nickels, making j+1 choices. Thus N5j = j+1. Similarly for k = 5j+1, etc.
5a. (Roll two dice) ⇔ (1 OR 2 OR ... OR 6) AND (1 OR 2 OR ... OR 6). Translating into algebra: f(x) = (x + x2 + ... + x6)2. Typing this into Wolfram Alpha as: "expand (x+x^2+x^3+x^4+x^5+x^6)^2", we get:
5b. Regardless of their labels, each of the dice can land on any of their 6 faces, making 62 = 36 equally likely cases. Let sk be the number of ways to roll a total of k with Sichermann dice. For example, s3 = 2, which can appear as either of the 2's on the first die, and 1 on the second die. Using similar reasoning as before, the generating function is:
5c. Similar to part (a):
5d. f(x) = x3 (1−x6)3 / (1−x)3
=
(x3 − 3x9 + 3x15 − x21) × ∑j≥0 ((3 | j)) xj.
Multiplying out and collecting xk terms, we get:
a19 | = | ((3 | 16)) − 3((3 | 10)) + 3((3 | 4)) − 3((3 | −3)) |
= | (18 | 2) − 3(12 | 2) + 3(6 | 2) − 0 = 153 − 198 + 45 = 0 . |
1c,d. Substituting x = −1 gives 1+5 = A(1 + 2), so A = 2; and substituting x = ½ gives −½ + 5 = B(3⁄2), so B = 3. We may check that f(x) = 2⁄(1+x) + 3⁄(1−2x) by putting over a common denominator and comparing with the previous form of f(x).
1e. f(x) = ∑k≥0 2(−x)k + ∑k≥0 3(2x)k = ∑k≥0 [2(−1)k + 3(2k)] xk, so ak = 2(−1)k + 3(2k)
2a. See class notes, where I solved a similar recurrence.
Step 1: f(x) = a0 + ∑k≥1 akxk = 1 + ∑k≥1 (2ak−1+1)xk
Notice that the summation is for k ≥ 1 since the recurrence is not valid for the k = 0 term a0. Continuing:
Notice that the last summation is almost a geometric series, but with the k = 0 term missing, which accounts for the −1 at the end.
We have: f(x) = 2x f(x) + 1/(1−x), which we solve to get:
(1−2x) f(x) = 1/(1−x) and finally:
f(x) = 1/(1−x)(1−2x).
Step 2: By partial fraction decomposition,
2b. Step 1: f(x) = a0 + ∑k≥1 akxk = 3 + ∑k≥1 (3ak−1−2k)xk
The summation is for k ≥ 1 since the recurrence is not valid for the k = 0 term.
f(x) = 3 + 3x ∑k≥1ak−1xk−1 − ∑k≥12kxk = 3 + 3x f(x) − 1/(1−2x) + 1.
The final +1 is because the geometric series ∑k≥12kxk
is missing its k = 0 term.
We have: f(x) = 3x f(x) − 1/(1−2x) + 4 = 3x f(x) + (3−8x)/(1−2x), which we solve to get: f(x) = (3−8x) / (1−2x)(1−3x).
Step 2: By partial fraction decomposition,
3a. Recurrence: ak = ak−1 + c. We do this by generating functions just for practice.
=
a0 + x ∑k≥1 ak−1xk−1 + cx ∑k≥1 xk−1
= a0 + x f(x) + cx/(1−x)
3b. Recurrence: ak = b ak−1+ c rk. Here the answer is not at all obvious. Step 1 gives:
f(x) = a0 + bx f(x) + crx/(1−rx) so f(x) = a0/(1−bx) + crx/(1−rx)(1−bx)
Partial fractions: crx/(1−rx)(1−bx) = A/(1−rx) + B/(1−bx) .
Clear denominators, substitute x = 1/b, 1/r , get A = cr/(r−b), B = −cr/(r−b).
Final answer: ak = a0bk + A rk + B bk = a0bk + cr(rk − bk)/(r−b).
Check: For the case in Prob #2, we have b = 2, c = r = 1, a0 = 1, so ak = 1(2k) + 1(1k−2k)/(1−2)
= 2k − (1−2k) = −1 + 2k+1 as we got in #2.
3c. Recurrence: ak = b ak−1 + ck . This one is harder than I would give on a test.
First, differentiating (1−x)−1 = ∑k≥0 xk gives: (1−x)−2 = ∑k≥0 kxk−1,
so x/(1−x)2 = ∑k≥0 kxk.
Equation: f(x) = a0 + bx f(x) + cx/(1−x)2 so f(x) = a0/(1−bx) + cx/(1−bx)(1−x)2
Partial fractions: cx/(1−bx)(1−x)2 = A/(1−bx) + B/(1−x)2 + C/(1−x) .
Clear denominators and substitute x = 1/b, x = 1 to get A = cb/(b−1)2 , B = −c/(b−1) .
Then we have: C/(1−x) = cx/(1−bx)(1−x)2 − A/(1−bx) − B/(1−x)2 = −c/(b−1)2(1−x) .
Final answer: ak = (a0 + cb/(b−1)2) bk − ck/(b−1) − cb/(b−1)2 .
Check: Compare with obvious formulas in the case b = 0 and in the case c = 0 .
4a. The equation reduces to ψ2 = 1−ψ, or ψ2+ψ−1 = 0, which has roots (−1±√5)/2. The positive root is ψ = (√5−1)/2 .
Also φ = 1/ψ = 2/(√5−1) = 2(√5+1) / (√5−1)(√5+1) = 2(√5+1) / (5−1) = (√5+1) / 2. The approximate values are ψ ≅ 0.6 , φ ≅ 1.6 .
4b. The roots are ψ and −φ.
F0 | F1 | F2 | F3 | F4 | F5 | F6 | F7 | F8 |
0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
f(x) | = | F0 + F1x + ∑k≥2 Fkxk |
= | x + ∑k≥2 (Fk−1 + Fk−2)xk | |
= | x + x ∑k≥2 Fk−1xk−1 + x2 ∑k≥2 Fk−2xk−2 | |
= | x + x (F1x + F2x2 + F2x3 + ...) + x2 (F0 + F1x + F2x2 + ...) | |
= | x + x (f(x) − F0) + x2 f(x) | |
f(x) | = | x + x f(x) + x2 f(x) |
1b. We should write: 1⁄(1−3x) = ∑k≥0 (3x)k = ∑k≥0 3kxk, and similarly for 1⁄(1−2x) , giving total coefficient ak = 3k − 2k.
1c. After the third equals sign, the ak just disappeared from the expression, which is wrong since in general ak ≠ 1. After the fourth equals sign, the expression 2xk was confused with as (2x)k, as in part (b).
2. Step 1:
f(x) | = | a0 + a1x + a2x2 + ∑k≥3 akxk |
= | 1 + x + 2x2 + ∑k≥3 (3ak−1− 3ak−2+ ak−3)xk | |
= | 1 + x + 2x2 + 3x ∑k≥3 ak−1xk−1 − 3x2 ∑k≥3 ak−2xk−2 + x3 ∑k≥3 ak−3xk−3 | |
= | 1 + x + 2x2 + 3x (a2x2 + a3x3 + ...) − 3x2 (a1x + a2x2 + ...) + x3 (a0 + a1x + ...) | |
= | 1 + x + 2x2 + 3x (f(x) − a0 − a1x) − 3x2 (f(x) − a0) + x3 f(x) | |
= | 1 + x + 2x2 + 3x f(x) − 3x − 3x2 − 3x2 f(x) + 3x2 + x3 f(x) | |
f(x) | = | 1 − 2x + 2x2 + 3x f(x) − 3x2 f(x) + x3 f(x) |
f(x) | = | (1 − 2x + 2x2) ∑k≥0 ((3 | k))xk | |||||||||||||||
= |
|
3. The simple functions with the asymptotes x = ψ and x = −φ are 1/(1 − x/ψ) = 1/(1−φx) and 1/(1 + x/φ) = 1/(1+ψx), since 1/ψ = φ and 1/φ = ψ.
In fact 1 − x − x2 = (1−φx)(1+ψx), since the two sides are polynoimals with the same roots and the same constant term.
Multiplying out x / (1−x−x2) = A/(1−φx) + B/(1+ψx), we get x = A(1+ψx) + B(1−φx) for all x.
Substituting x = ψ gives ψ = A(1+ψ2) + B(1−φψ) = A(1+ψ2) so A = ψ/(1+ψ2) = ... = 1/√5.
Similarly B = −1/√5.
It is much easier to rewrite the original equation as: x = (A+B) + (Aψ−Bφ)x,
and equate the constant terms and the coefficients of x on the two sides: 0 = A+B, so that B = −A; and
1 = Aψ−Bφ = Aψ+Aφ, so that A = 1/(ψ+φ) = 1/√5 and B = −1/√5.
4a. For example:
F3 | = | [(1+√5)3 − (1−√5)3] / 23√5 |
= | [ (1 + 3√5 + 3√25 + √125) − (1 − 3√5 + 3√25 − √125)] / 8√5 | |
= | (6√5 + 2(5)√5) / 8√5 = 16 / 8 = 2 (!?) |
4b. You round down when k is even and the correction term −(−ψ)k is negative, and round up when k is odd and −(−ψ)k is positive.
4c. F40 = round( (1.618033988749895)40 / 2.2360679774997896 )
= round( 1.023341550000000019 × 108 )
= 102334155 .
The run of 0's in the decimal expansion is because the correction term −(−ψ)k / √5 is exponentially small.
The number of digits is the rounding-down of:
3. ak = (ak+1 + (−1)kbk+1)⁄2√2 , where a = 1+√2, b = −1+√2.
5. Suppose we have a balance scale with an unlimited supply of three kinds of weights: red 1oz, black 1oz, and 2oz. Then ak is the number of ways to balance k oz with an ordered row of weights.
2.
k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Ck | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | 4862 | 16796 |
3a. The groupings with division point after xm split into a factor with m+1 variables and one with k−m variables, with 0 ≤ m ≤ k−1; considering recursively, there are MmMk−m−1 such groupings. Thus Mk = M0Mk−1 + M1Mk−2 + ... + Mk−1M0.
3b. Mk and Ck are computed using exactly the same recursion, starting from the same initial value M0 = C0 = 1, so they must be equal.
Formally, we can prove it by induction. Mk = Ck is definitely true for k = 0. Now assume it is proved up to a given k. Then
Mk+1 = MkM0 + Mk−1M1 + ... + M0Mk. By assumption M0 = C0, M1 = C1,..., Mk = Ck, so the right hand side equals
CkC0 + Ck−1C1 + ... + C0Ck, which equals Ck+1 by the known recurrence. Thus the equality Mk+1 = Ck+1 also holds, and the induction proceeds. Conclusion: Mk = Ck holds for all k ≥ 0.
4. Any tree T with k ≥ 2 splits into two subtrees: T' coming from the ancestor's oldest child (having m ≥ 1 vertices), and T'' with everyone else, including the ancestor (having k − m vertices). Conversely, any T' and T'' can be put together in a unique way to get a T (i.e. make the ancestor of T' into the oldest child of the ancestor of T''). Considering recursively, the number of pairs (T' , T'') is OmOk−m.
Thus, Ok = Ok−1O1 + Ok−2O2 + ... + O1Ok−1. This is the same recurrence as for the sequence C'k = Ck+1 , so Ok = C'k = Ck+1.
In the picture above, the first two trees are of type O3O1, since the subtree T' coming from the oldest (only) child has 3 vertices, and the rest make a tree T'' with 1 vertex (the ancestor alone).
The third tree is of type O2O2, since the subtree T' from the oldest child has 2 vertices, and the rest make T'' with 2 vertices. The last two trees are of type O1O3, since the oldest child has no children, and there are 3 vertices besides.
5. The kth derivative of (1−x)1/2 is (−1)k(½)(½−1)(½−2)...(½−k+1)(1−x)1/2 − k, so the kth coefficient of the Taylor series is ak = (−1)k(½)k / k!. This can be rewritten as:
2. 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) . |
3a. By the Reflection Principle, we have Ck = (2k | k) − (2k | k−1), which simplifies algebraically as:
= (2k)!⁄k!(k−1)! (1⁄k(k+1)) = 1⁄(k+1) (2k)!⁄k!k! = 1⁄(k+1) (2k | k).
1 | −−−−−− | 2 |
| | | | |
4 | −−−−−− | 3 |
° | ε | ρ | τ1 | τ2 |
ε | ||||
ρ | ||||
τ1 | ε | |||
τ2 |
2. The two-line tables for the symmetries are:
|
|
|
3. With a little practice, you can easily multiply using two- or one-line notation. For example:
° | ε | ρ | τ1 | τ2 | |||||||||||||||
ε | ε | ρ | τ1 | τ2
ρ | ρ | ε | τ2 | τ1
| τ1 | τ1 | τ2 | ε | ρ
| τ2 | τ2 | τ1 | ρ | ε
| |
4a. Each element is its own inverse, as we can see from ε's on the diagonal of the multiplication table. Note that in general, a symmetry is usually not its own inverse.
4b. We find σ−1 by reversing the inputs and outputs of σ. Thus, for σ = [4,2,5,3,1], we have σ(1) = 4, so σ−1(4) = 1, etc., and σ−1 = [5,2,4,1,3]. Given 2-line notation, we can switch the top and bottom lines, then rearrange the columns so as to get 1,2,...,n on top.
5a. Our group G, the symmetries of the rectangle, is a commutative group: we see that the table is symmetric across the upper-left to lower-right diagonal, so that an upper-right entry σ ∘ τ is the same as the corresponding lower-left entry τ ∘ σ.
5b. Writing in one-line notation, we have [2,1,3] ∘ [1,3,2] = [2,3,1], whereas [1,3,2] ∘ [2,1,3] = [3,1,2], so [2,1,3] and [1,3,2] do not commute. We can duplicate this in every larger Sn by just defining σ(i) = i for i ≥ 4. For example: [2,1,3,4,5] ∘ [1,3,2,4,5] = [2,3,1,4,5], etc.
σ | = | ⌈ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | ⌉ | |
⌊ | 6 | 8 | 7 | 4 | 1 | 5 | 2 | 3 | ⌋ |
1 | −−−−−− | 2 |
| | | | |
4 | −−−−−− | 3 |
1c. The inverse permutation reverses each cycle, so that σ−1 = (5,6,1)(7,3,8,2)(4) = (1,5,6)(2,7,3,8)(4).
2a. We write each element of the dihedral group in cycle notation, including the abbreviated form omitting cycles of length 1. Note that an element like σ = (1432) means σ(1) = 4, σ(4) = 3, σ(3)=2, σ(2) = 1, and we could equivalently write σ = (2143) = (3214) = (4321).
2b. We have ρ1(i) = i+1 modulo n. This means we wrap around an n-hour clock, with n = 0, n+1 = 1, etc. Performing this k times, we get ρ1k(i) = i+k modulo n, and this is clearly ρk(i). Note also that ρ1n = ε and by definition ρ10 = ε. (These last facts are analogous to (−1)2 = 1 and x0 = 1.)
2c. We have τk = τ1ρ1k for k = 0,1,2,3, as we can check by computing the cycle notation for the left and right sides.
3a. A cube symmetry σ can rotate Face 1 to any of the 6 faces, so there are 6 choices for σ(1). Then σ(2) can be any of the 4 faces adjacent to σ(1). Now σ(3) can only be the face adjacent to σ(1) and σ(2), such that the path σ(1) → σ(2) → σ(3) → σ(1) circles clockwise around their common corner (since the path 1 → 2 → 3 → 1 circles clockwise around their common corner). Finally, σ(4) is the face opposite σ(3), etc. This makes a total of 6 × 4 = 24 choices, so that |G| ≤ 24.
3b. The cube has 1 identity symmetry ε = (1)(2)...(6). Also 3 axes through opposite pairs of faces, each with 1⁄4, 1⁄2, and 3⁄4 rotations, such as: α = (1)(6)(2354) and α2 = (1)(6)(25)(34). Also 4 axes through opposite pairs of corners, each with 1⁄3 and 2⁄3 rotations, such as: (1,2,3)(4,6,5). Also 6 axes through midpoints of opposite pairs of edges, each with a 1⁄2 rotation, such as: (1,2)(3,4)(5,6). Total: 1 + (3)(3) + (4)(2) + (6)(1) = 24, giving all the possible symmetries of G according to part (a).
4a & b. The colorings, grouped into symmetry classes of the rectangle group. Each line lists the elements of c = {c, ρ(c), τ1(c), τ2(c)}, though some of these might be identical, so we only list them once. (Remember, the quarter-turn is not a rectangle symmetry.)
R | R | |||||||||
R | R | |||||||||
B | R | R | R | R | B | R | R | |||
R | R | R | B | R | R | B | R | |||
B | B | R | R | |||||||
R | R | B | B | |||||||
R | B | B | R | |||||||
R | B | B | R | |||||||
B | R | R | B | |||||||
R | B | B | R | |||||||
R | B | B | B | B | R | B | B | |||
B | B | B | R | B | B | R | B | |||
B | B | |||||||||
B | B |
We have |C| = 7 symmetry classes (rows) altogether. Thus, we say there are 7 colorings of the rectangle vertices with colors R,B, distinct up to symmetry.
4c. There are |D| = 4! = 24 colorings of 4 vertices with 4 distinct colors, corresponding to lists of 1,2,3,4 in some order. Every symmetry class has |G| = 4 colorings, so the number of symmetry classes is: |D| = |D|⁄|G| = 24⁄4 = 6.
5. |D| = |D|⁄|G| = 6!⁄24 = 30.
R |
B R |
R B |
B |
1 |
6 2 |
5 3 |
4 |
1b. Referring to HW 2/24 #2a, the identity ε has 4 cycles, the two 1⁄4 rotations have 1 cycle each, the 1⁄2 rotation has 2 cycles, two of the reflections have 2 cycles, and the other two reflections have 3 cycles, Burnside gives the general formula:
|C| = 1⁄8(k4 + 2k3 + 3k2 + 2k).
The case k = 1 gives |C| = 1⁄8 ∑σ∈G 1cyc(σ) = 8/8 = 1, which is correct. In the case k = 2, we get
|C| = 1⁄8(24 + 2(23) + 3(22) + 2(2)) = 6: there is one symmetry class for 0R's, 1R, 3R's, 4R's; and two symmetry class for 2R's 2G's,
namely when the R's are next to each other and when they are diagonal.
1c. Referring to HW 2/24 #3,
the identity gives contribution k6;
the three sets of face rotations like α and α2
give 6k3 + 3k4;
the four sets of corner-rotations give 8k2;
and the six edge-rotations give 6k3.
Thus |C| = 1⁄24(k6 + 3k4 + 12k3 + 8k2).
For k = 1 this gives |C| = 1,
which is correct.
and for k = 2 it is |C| = 10.
There is one symmetry class for 0R's, 1R, 5R's, 6R's; two classes for 2R's (adjacent or opposite) and similarly
for 4R's; and two classes for 3R's (all adjacent or not).
2. We can consider the 6 beads at the corners of a regular hexagon (with vertices labeled 1,...,6 clockwise), so that the symmetry group is D6 (HW 2/24 #2): the identity; 5 rotations ρi = (ρ1)i; three reflections τ1, τ2, τ3 across the lines through opposite pairs of edges; and three reflections τ4, τ5, τ6 across the lines through opposite pairs of vertices:
σ | cycles | kcyc(σ) |
ε | (1)(2)(3)(4)(5)(6) | k6 |
ρ1 | (123456) | k1 |
ρ2 | (135)(246) | k2 |
ρ3 | (13)(24)(36) | k3 |
ρ4 | (531)(642) | k2 |
ρ5 | (65431) | k1 |
τ1 | (1)(26)(35)(4) | k4 |
τ2 | (2)(13)(46)(5) | k4 |
τ3 | (3)(24)(15)(6) | k4 |
τ4 | (12)(36)(45) | k3 |
τ5 | (23)(14)(56) | k3 |
τ6 | (34)(25)(16) | k3 |
B | R | |
R B | B R | |
B R | R B | |
R | B |
3. The symmetry group is G = D3, the same motions of the plane as for a triangle (see HW 2/27 #2). However, these symmetries are permuting the 15 labeled vertices:
σ | cycles | kcyc(σ) |
ε | (1)(2)...(15) | k15 |
ρ1 | (1,6,11)(2,7,12)(3,8,13)(4,9,14)(5,10,15) | k5 |
ρ2 | (11,6,1)(12,7,2)(13,8,3)(14,9,4)(15,10,5) | k5 |
τ1 | (1)(2,15)(3,14)(4,13)(5,12)(6,11)(7,10)(8,9) | k8 |
τ2 | (6)(5,7)(4,8)(3,9)(2.10)(1,11)(12,15)(13,14) | k8 |
τ3 | (11)(10,12)(9,13)(8,14)(7,15)(6,1)(5,2)(4,3) | k8 |
4a. The natural symmetries are turning only (since flipping the board would expose the underside). The only turn which does not switch white and black squares is the 180° turn ρ, so the symmetry group is G = Sym(X) = {ε, ρ}.
4b. The identity is ε = (1)(2)...(64). The rotation is ρ = (1,64)(2,63)(3,62)...(32,33) : the 32 two-cycles are all pairs (a,b) with a+b = 65.
4c. There are k = 3 options for each square: red piece, blue piece, or empty. Choosing one of these for each square is a Burnside coloring problem with the above group G = {ε ρ}, so the number of coloring classes (arrangements up to symmetry) is:
1b. Here a bag is a multi-set with 3 items of 5 kinds (Basic Problem 4). Ans: ((5 | 3)) = (5+3−1 | 3) = (7 | 3) = 73 / 3! = 35.
1c. A bag is any non-empty subset of {P,G,C,S,B}. An n-element set has 2n subsets (since each of the n elements could be in or out of the subset: Product Principle). Since the empty set is not allowed, we get 25 − 1 = 31.
1d. A sequence of 5 independent choices, each with (5 | 3) possibilities (Product Principle). Ans: (5 | 3)5 = 100,000.
2a. Basic Problem 1: Ordering 5 distinct objects (Basic Problem 1). Ans: 5! = 120.
2b. PIE: A = {all arrangements from part (a)}, A1 = {arrangements containing sequence C,B}, A2 = {arrangements containing sequence B,C}. In A1, we can consider the adjacent letters C,B as a single unit, next to the 3 other units P, G, S; and these 4 units can be arranged arbitrarily. Same for A2, so |A1| = |A2| = 4!. Also |A1∩A2| = 0, and the number of good arrangements is:
2c. PIE: A = {all arrangements}, with 4 kinds of forbidden arrangements: A1 = {arrangements containing the sequence C,B}, A2 = {arr with B,C}, A3 = {arr with C,S}, A4 = {arr with S,C}. Reasoning as before, |A| = 5! and |Ai| = 4!. The only non-empty intersections are: A1∩A4 = {arr with S,C,B} and A2∩A3 = {arr with B,C,S}. Again, consider arbitrary arrangements of a 3-letter unit with two 1-letter units, giving 3! arrangements for each intersection. Hence:
= 5! − 4(4!) + 2(3!) = 36.
Another way: positive counting using a transformation. We analyze the data into parts which can be easily counted.
2d. Pick the positions of the two C's (Basic Problem 3), then arrange the other 4 around them (Basic Problem 1). Ans: (6 | 2) 4! = 360.
Alternatively: list the positions of B,G,S,P, making a list of 4 distinct positions out of 6 (Basic Problem 2). Ans: 64 = 360.
3a. Positive counting. Split all outcomes into disjoint cases (Sum Principle): Case (i), just 1 flavor, all 20 beans the same: 3 handfuls. Case (ii), have 2 flavors: then 4 beans are fixed (2 of each flavor), with 16 left to choose among 2 flavors; (3 | 2)((2 | 16)) handfuls. Case (iii), have all 3 flavors: then 6 beans are fixed, 14 left to choose among 3 flavors; ((3 | 14)) handfuls. Ans: 3 + 3((2 | 16)) + ((3 | 14)) = 3 + 3(17 | 1) + (16 | 2) = 174
3b. Negative counting (PIE). A = {all handfuls of 20 beans of 3 kinds}, Ai = {just 1 of flavor i, the other 19 of 2 flavors}, for i = 1,2,3. Ans: ((3 | 20)) − (3 | 1)((2 | 19)) + (3 | 2)((1 | 18)) − (3 | 3)((0 | 17)) = (22 | 2) − 3(20 | 1) + 3 = 174.
3c. Step 0: Generalize the problem to give a sequence.
Let ak be the number of ways to choose k jellybeans with the given restriction.
Step 1. Find a simple formula for the generating function f(x) = ∑k≥0 ak xk .
Consider that a handful of beans can be chosen by the logical expression:
4. Turning the recurrence into an equation for f(x) = ∑k≥0 pkxk, we get:
f(x) | = |
| . |
5a. A sequence of 8 independent choices, with 2 outcomes for each. Product Principle: 28 = 256.
5b. A sequence of 8 binary choices, with 5 steps and 3 stays. Position Transformation into Basic Problem 3: (8 | 5) = (8 | 3) = 56.
5c. A sequence of 8 whole numbers adding up to 5, (n1,..., n8) with ni ≥ 0 and n1 + ... + n8 = 5. The Multiplicity Transformation turns this into arrangements of 5 beans in 8 bins, Basic Problem 4: ((8 | 5)) = (5+8−1 | 5) = (12 | 5) = 792.
6a. Step 1: (Take 8 turns stay/step) ⇔
(turn 1: stay or step) and ... and (turn 8: stay or step).
Since "stay" advances 0 steps, it is replaced by x0, and similarly "step" becomes x1:
6b. Step 1: (Take 8 turns of any length) ⇔
(turn 1: 0 steps or 1 step or 2 steps or...) and ... and (turn 8: 0 steps or 1 step or ...).
Each choice to advance i steps gets replaced by xi:
6c. Step1: Similarly to the above:
6d. f(x) = (1+x+x2+...+x10)8
=
(1−x11)8⁄(1−x)8
=
(∑8i=0
(−1)i (8 | i) x11i)
(∑j≥0 ((8 | j)) xj),
so ak = ∑11i+j=k (−1)i (8 | i) ((8 | j))
7a. The recurrence is: (n | k) = (n−1 | k) + (n−1 | k−1). The Deletion Transformation is S → S' where: S' = S if n ∉ S; and S' = S \ {n} if n ∈ S. Its inverse is the Insertion Transformation S' → S, where S = S' if |S'| = k, and S = S' ∪ {n} if |S'| = k−1.
7b. Each input M is on top, with its transformation output M' below it.
M = | {1,1,1} | {1,1,2} | {1,1,3} | {1,2,2} | {1,2,3} | {1,3,3} | {2,2,2} | {2,2,3} | {2,3,3} | {3,3,3} |
M' = | {1,1,1} | {1,1,2} | {1,2,2} | {2,2,2} | ||||||
{1,1} | {1,2} | {1,3} | {2,2} | {2,3} | {3,3} |
The inputs cover all ((3 | 3)) multisets M; the outputs cover all ((2 | 3)) + ((3 | 2)) multisets M'.
7c. The inverse is the Insertion Transformation M' → M, where: M = M', if |M'| = k; and
8. We make a two-row table of the transformation between the 14 factorizations counted by C4, and the splitting of these at the outermost multiplication into pairs of factorizations counted by ∑3i=0 CiC3−i. In fact, the most practical way to list all the C4 expressions at all is to write the (Ci | C3−i) expressions first, then combine them.
C4 | x0(x1(x2(x3x4))) | x0(x1((x2x3)x4)) | x0((x1x2)(x3x4)) | x0((x1(x2x3))x4) | x0(((x1x2)x3)x4) |
C0 | C3 | x0 | x1(x2(x3x4)) | x0 | x1((x2x3)x4) | x0 | (x1x2)(x3x4) | x0 | (x1(x2x3))x4 | x0 | ((x1x2)x3)x4 |
C4 | (x0x1)(x2(x3x4)) | (x0x1)((x2x3)x4) | C4 | (x0(x1x2))(x3x4) | ((x0x1)x2))(x3x4) |
C1 | C2 | x0x1 | x2(x3x4) | x0x1 | (x2x3)x4 | C2 | C1 | x0(x1x2) | x3x4 | (x0x1)x2) | x3x4 |
C4 | (x0(x1(x2x3)))x4 | (x0((x1x2)x3))x4 | ((x0x1)(x2x3))x4 | (((x0(x1x2))x3)x4 | (((x0x1)x2)x3)x4 |
C3 | C0 | x0(x1(x2x3)) | x4 | x0((x1x2)x3) | x4 | (x0x1)(x2x3) | x4 | ((x0(x1x2))x3 | x4 | ((x0x1)x2)x3 | x4 |
1. (p. 4 #1) V = {a,b,c,d,e,f,g,h,i,j} and E = {all possible edges xy}−{af, bg, ch, di, ej}. That is, G is the complement of the graph with edges {af, bg, ch, di, ej}.
1. (p. 4 #2) V = {A,B,C,D,E,F}, E = {AD, BA, BE, CD, CE, DC, FA, FB}. This should be a digraph, so that AD ≠ DA, since Adam likes Doug is not the same as Doug likes Adam. Officially, each directed edge is an ordered pair like (A,D). Note that it is reasonable to ignore the loop-edge EE, since it does not denote a valid roommate pairing.
1. (p. 4 #3) V = {teams}, with an edge between each pair of teams that have played each other, and two edges between teams that have played twice. This is is a multi-graph since it has multiple edges between a given pair of vertices.
2b. |E| = (n | 2) = ½n(n−1)
3a.
3b. n = |V| = 24 = 16. Since Cub4 is 4-regular, the Vertex-Edge Formula gives |E| = ½nd = ½(16)(4) = 32.
4a. A 1-regular graph is a union of disjoint edges: V = {a_1,...,a_n, b_1,..., b_n} and E = {a_1b_1, a_2b_2,..., a_nb_n}.
4b. Set d = deg(5), the number of edges from vertex 5. For d = 0, G = K4 ∪ K1 ; for d = 2 , G has edges E = {51, 52, 31, 32, 34, 41, 42}; and for d = 4 , G has E = {51, 52, 53, 54, 12, 23, 34, 41}. For d = 1 , vertex 5 must connect to some vertex, say 1; and then 2 must connect to 1,3,4; and 3 must connect to 1,2,4; and 4 must connect to 1,2,3. But this gives deg(1) = 4, so d = 1 is impossible. For d = 3 , vertex 5 must connect to three vertices, say 1,2,3. Then 4 must connect to 1,2,3. Now there are three dangling edges 1?, 2? and 3?, and it is impossible to join them up, so d = 3 is impossible.
4c. Use that ∑v∈V deg(v) = 2|E|, so if deg(v) = d for all n vertices, we have dn = 2|E|. If d and n were both odd, then their product dn would also be odd, but dn = 2|E| is clearly even. This contradiction shows d and n cannot both be odd.
1b. A walk is a path with repeat vertices allowed, but without the same vertex twice consecutively. Thus, the number of walks with j vertices is 5(4j−1). If we take k steps along j = k+1 vertices, this becomes 5(4k).
1c. A cycle of length k in K5 is a list of any k vertices, up to cyclic symmetry. Answer: 5k⁄k .
2a. You should find the shells by labeling the vertices of the graph as described in the problem, and the vertices labeled with each value i form the set Di. To check your answer:
2b. Since (0,5) ∈ D6, this vertex is 6 steps from (3,2). Stepping from (0,5) to a neighboring vertex with a smaller label, and repeating, we get many possible paths to (3,2) with 6 steps (7 vertices), such as:
2c. It is not hard to find a path containing 35 of the 36 vertices: for example, go around the outer square and spiral inward. I do not know if there is a path using all 36 vertices, which is called a Hamiltonian path. In general, finding a Hamiltonian path is a difficult (NP complete) problem, with no efficient algorithms. Extra Credit if you find one!
3a. If (a,b) is a vertex with a+b an even number, then every edge (a,b)(a+1,b) or (a,b)(a,b+2) or (a,b)(a+1,b+1) will connect (a,b) to a vertex (c,d) with c+d also even; and similarly if a+b odd. Furthermore, if a+b and c+d are both even, it is not difficult to connect them by edges; and similarly for both odd. Hence the connected components are the subgraphs with vertices V1 = {(a,b) with a+b even} and V2 = {(a,b) with a+b odd}.
3b. There are 4 components, each with a typical representative vertex (a,b):
1b. Cycle Cn with vertices numbered clockwise V = {1,2,...,n} is bipartite if n even, with partition V = {1,3,...,n−1} ∪ {2,4,...,n}; and non-bipartite if n odd (in which case the whole graph is an odd cycle).
1c. Path Pn with vertices numbered in order V = {1,2,...,n} is always bipartite, with the following partition: if n even, V = {1,3,...,n−1} ∪ {2,4,...,n}; if n odd, V = {1,3,...,n} ∪ {2,4,...,n−1}.
1d. Cubd, with vertices v which are bit-strings of length d, is always bipartite, with V+ being the set of bit-strings with an even number of 1's, and V− the bit-strings with an odd number of 1's.
1e. Every cycle of the Petersen graph is a C5, so it is not bipartite.
2a. We have deg(ai) = s edges at each vertex a1,...., ar, and these are the only edges, so |E| = rs. Alternatively, using the Edge-Vertex Formula, |E| = ½(∑i=1r deg(ai) + ∑j=1s deg(bj)) = ½(rs + sr) = rs.
2b. Since G is bipartite, it has a splitting V = V+ ∪ V− with |V+| = r and |V−| = s for some r+s = 7. Given such a splitting, we can add all possible edges between the two parts until we get a complete bipartite graph Kr,s. Thus, the maximum number of edges is rs for some r+s = 7, namely (1)(6) = 6 or (2)(5) = 10 or (3)(4) = 12, and largest of these is 12.
3a. Let V+ = {(000), (110), (101), (011)} and V− = {(100), (010), (001), (111)}, the vertices whose coordinates have an even/odd number of 1's. Since any edge changes exactly one coordinate, it will always change an even number of 1's to an odd number, and vice versa. Thus, all edges go between the + and − vertices, never connecting two + vertices or two − vertices.
3b. The graph G' has the 3-cycle: C = (000)(100)(110)(000). A bipartite splitting of the vertices of G would also give one for C, which is impossible, so there cannot be any splitting for G.
3c. False. G is not a complete bipartite graph, meaning it does not have every possible edge between V+ and V−. In fact, we can add the long diagonals (000)(111) and (001)(110) and (010)(101) and (100)(011) to make the complete bipartite graph K4,4.
4a. Proposition P(n): 1 + 2 + 3 + ... + n = ½ n(n+1)
Proof. Base Case: The left side of equation P(1) is 1, and the right side is ½ 1(1+1) = 1. Thus equation P(1) is true.
Chain Case: Assume we know the formula for n = k, namely P(k): 1 + 2 + ... + k = ½ k(k+1).
We wish to prove it for n = k+1, so we compute the left side of P(k+1):
1 + 2 + 3 + ... + k + (k+1) | = | ½ k(k+1) + (k+1) | by the inductive hypothesis P(k) |
= | (k+1) (½k+1) = ½ (k+1) (k+2) | by algebra (factoring out k+1) |
4b. Proposition P(n): 1 + 3 + 5 + ... + (2n−1) = n2
Proof. Base Case: The left side of P(1) is 1, and the right side is 12 = 1, so P(1) is true.
Chain case: Assume we know the formula for n = k, namely P(k): 1 + 3 + ... + (2k−1) = k2.
We wish to prove it for n = k+1, so we compute the left side of P(k+1):
1 + 3 + 5 + ... + (2k−1) + (2k+1) | = | k2 + (2k+1) | by the inductive hypothesis P(k) |
= | (k+1)2 | by algebra. |
4c. We write this one less formally. I claim that k+1 ≤ 2k for all k ≥ 1. The base case k = 1 is true: 1+1 ≤ 21. For the chain case, assume k + 1 ≤ 2k. Then the next case is:
1b. P ⇒ Q: If Joe is hungry, then he eats a whole pie. (Not plausible: he will probably eat only a piece.)
Not(Q) ⇒ Not(P): If Joe doesn't eat a whole pie, then he must not be hungry. (Equivalent to previous.)
Q ⇒ P: If Joe eats a whole pie, then he must be hungry. (Plausible!!)
Not(P) ⇒ Not(Q): If Joe is not hungry, then he won't eat a whole pie. (Equivalent to the previous.)
1c. P ⇒ Q: If n = (2m)2 for some m, then n is divisible by 4. (True, since (2m)2 = 4m2.)
Not(Q) ⇒ Not(P): If n is not divisible by 4, then n ≠ (2m)2 for any m. (True: equivalent to the previous.)
Q ⇒ P: If n is divisible by 4, then n = (2m)2 for some m. (False, since n = 8 is divisible by 4, but 8 is not a square number.)
Not(P) ⇒ Not(Q): If n ≠ (2m)2 for any m, then n is not divisible by 4. (False: equivalent to the previous.)
1d. P ⇒ Q: If G is bipartite, then every subgraph is bipartite. (True, since a bipartite splitting of the vertices of G restricts to a splitting of any subgraph.)
Not(Q) ⇒ Not(P): If some subgraph of G is not bipartite, then G is not bipartite. (True: equivalent to the previous.)
Q ⇒ P: If every subgraph of G is bipartite, then G is bipartite. (True, since G itself is a subgraph of G.)
Not(P) ⇒ Not(Q): If G is not bipartite, then not every subgraph of G is bipartite. (True: equivalent to the previous.)
2. By hypothesis, let T be a tree, meaning that T is connected and has no cycles. Since T contains no cycles at all, it contains no cycles of odd length. Hence the Bipartite Graph Theorem (GN I.11 in the Notes) says that T is bipartite, which is the desired conclusion.
3. A theorem is usually stated in the form "If A then B" or "All A's are also B's". The converse statement is "If B then A" or "All B's are also A's". The converse might well be false, even if the original statement is true.
In this case, the original true statement is "All trees are also bipartite graphs", and its converse is "All bipartite graphs are also trees". This is indeed false: for example C4 is a bipartite graph, but not a tree.
4. Proof: By hypothesis, consider tree T (connected and acyclic) and a vertex v with d neighbors w1,..., wd. Extend the edge vw1 into a path as long as possible: P1 = vw1x1...y1z1. Then I claim z1 is a leaf of T. Indeed, if z1 had any neighbor t ≠ y1, then we could extend P1 further unless t were already used in the path: P1 = vw1x1...t...y1z1. But this would mean that T has the cycle C = t...y1z1t = tPz1t, which is impossible since T is acyclic. Hence z1 does not have any neighbor other than y1, so deg(z1) = 1, and z1 is a leaf.
Similarly, we produce leaves z1,...,zd from w1,...,wd. If two of these were the same, z = zi = zj, we would get the cycle:
5a. Let G be an acyclic graph, and write its connected components (GN I.7): G = T1 ∪...∪ Tk. By defintion each Ti is connected, and cannot have any cycles since G has none. Since it is connected and acyclic, the component Ti is a tree, so G is a disconnected union of trees, and hence a forest.
5b. Consider the forest G = T1 ∪...∪ Tk with the component trees Ti having ni vertices and ni−1 edges (GN II.4), so that n = n1 + ... + nk. Then the total of edges in G is:
2. (⇒) Assume T is a tree (connected and acyclic). Then any vertices x,y have some path P between them (since T connected).
Now suppose for a contradiction that there is a different path Q from x to y. (It does not follow that xPyQx is a cycle, since P and Q might cross each other several times, which is not allowed in a cycle.)
Let v be the last vertex before P and Q diverge (for example v = x if their first steps are different). Let w be the first vertex after v where P and Q cross (for example w = y if they do not cross until their endpoint). Then vPw and vQw (the parts of P and Q between v and w) are disinct paths which do not cross except at their common endpoints, so C = vPwQv is a cycle. This contradicts the assumption that T is acyclic.
Supposing two distinct P and Q leads to a contradiction, so the path P must be unique.
(⇐) Assume T has a unique path between any two vertices. Then T is connected (since there is some path). Suppose for a contradiction that T had a cycle C = xy....zx. Then P = xy and Q = xz...y are distinct paths from x to y, but this is impossible since T has unique paths. Thus there cannot be a cycle in T, so T is acyclic and connected, so T is a tree.
2a & b. The table shows all trees and their Prufer sequences:
1−2−3−4 | 1−2−4−3 | 1−3−2−4 | 1−3−4−2 | 1−4−2−3 | 1−4−3−2 | 2−1−3−4 | 2−1−4−3 | 2−3−1−4 | 2−4−1−3 | 3−1−2−4 | 3−2−1−4 | ||||||||||||
(2,3) | (2,4) | (3,2) | (3,4) | (4,2) | (4,3) | (1,3) | (1,4) | (3,1) | (4,1) | (1,2) | (2,1) |
3 | 3 | 2 | 2 | ||||||
| | | | | | | | ||||||
2−−1−−4 | 1−−2−−4 | 1−−3−−4 | 1−−4−−3 | ||||||
(1,1) | (2,2) | (3,3) | (4,4) |
Performing the Reverse Prufer Transform on each sequence σ recovers the tree above it.
3. First tree: σ = (2,2,1,3,1,4,4,1,5). Second tree: (5,8,4,3,3,3,9)
4. The Reverse Prufer Transformation on σ = (5,4,3,5,4,3,5,4,3) goes like this:
Vi\ σi | 1,2,6,7,8,9,10,11 | 2,6,7,8,9,10,11 | 6,7,8,9,10,11 | 7,8,9,10,11 | 8,9,10,11 | 9,10,11 | 10,11 | 5,11 | 4,11 |
si | 5 | 4 | 3 | 5 | 4 | 3 | 5 | 4 | 3 |
ℓi | 1 | 2 | 6 | 7 | 8 | 9 | 10 | 5 | 4 |
The left-over vertices are V10 = {1,2,...,11} \ {ℓ1,...,ℓ9} = {3, 11}. Putting together the edges ℓi−−si and 3−−11, we get the tree:
1 | 2 | 6 | |||||||
| | | | | | |||||||
7 | −− | 5 | −− | 4 | −− | 3 | −− | 11 | |
| | | | | | |||||||
10 | 8 | 9 |
5. The leaf vertices of T will be pulled off in the course of the Prufer Transformation, which records their neighbors as si in σ. The leaves themselves will never be neighbors of leaves, so they are not in σ. Furthermore, a vertex v with k neighbors will have k−1 of them pulled off (recording si = v each time), and then v becomes a leaf itself and is eventually pulled off, or it is left over at the end. Either way, v appears k−1 times in σ.
6a. Recall that for any T, each v ∈ T appears deg(v)−1 times in σ. Since c appears n−2 times in σ, the vertex c in T must have deg(c) = n−1 neighbors. This means c is a central vertex with an edge to every other vertex, and T is a star tree.
6b. Since the n−2 entries appear once each, they correspond to vertices in T of degree 2. The 2 vertices which do not appear are the leaves of T. Hence, T has no branching (degree 3 or more), and T must be an n-vertex path.
1b. The only two of the six graphs which have the same number of vertices are the lower left and middle right (8 vertices each). Start by labeling the two vertices of degree 2 as A,B in each graph, then label their neighbors C,D, etc. The result is two graphs with the same vertices and edges, just drawn differently.
2. See p. 82:
3. G0 = T is a tree, having n vertices, q = n−1 edges, and r = 1 region, giving n − q + r = n − (n−1) + 1 = 2. Adding an edge to T creates a cycle which cuts off a finite region from the infinite region; so T+e has n vertices, q = n edges, r = 2 regions, giving n − q + r = n − n + 2 = 2. Adding another edge cuts one more region in two, giving q = n + 1, r = 3, and still n − q + r = 2. Continuing in this way, after each new edge the new values of (n,q,r) become (n', q', r') = (n, q+1, r+1), and the quantity n' − q' + r' = n − q + r remains unchanged, namely 2. This is the idea behind the inductive proof of Euler's Theorem in the next lecture.
4c. Proposition: If G is a planar graph with k connected components, n vertices, q edges, r regions, then:
n − q + r = k + 1.
Proof: If a component Gi is drawn in the plane with ni vertices, qi edges, and ri regions, then the original Euler formula applies to this connected graph: ni − qi + ri = 2. A drawing of G is just placing G1,...,Gk next to each other: none of the vertices, edges, or regions overlap, except that the infinite region is the same for all G1,...,Gk. Thus:
= ∑i (ni − qi + ri) − k + 1 = 2k − k + 1 = k + 1.
5. We have G with n = |V| = 24, and deg(v) = 3 for all v, so q = |E| = ½∑v∈V deg(v) = ½(24)(3) = 36. Hence r = 2 − n + q = 2 − 24 + 36 = 14.
1b. For G = K1 and K2, we have g = 0, so the Region-Edge Inequality is automatically satisfied. Indeed, in these cases, the graph is obviously planar.
For G = Kn with n ≥ 3, we have q = (n | 2) = ½n(n−1), g = 3, so if planar then r = 2 − n + ( ½n2 − ½n) = ½n2 − 3⁄2n + 2. The edge inequality becomes:
2a. For K5 with an extra vertex on one edge, we have n = 6, q = 11, g = 3. If planar, we have r = 2 − 6 + 11 = 7 and gr = (3)(7) = 21, 2q = (2)(11) = 22, so the Region-Edge Inequality holds. Thus we get no contradiction. However, this failed proof does not mean G is planar: the jury is still out, and other arguments might succeed.
2b. For K3,3 with an extra vertex on one edge, we have n = 7, q = 10, g = 4. If planar, we have r = 2 − 7 + 10 = 5 and gr = (4)(5) = 20, 2q = (2)(10) = 20, so the Region-Edge Inequality holds, and again there is no contradiction.
2c. Neither of these graphs is planar. If we had any planar drawing of either, we could erase the extra vertex (turning the subdivided edge back into a single edge), and get a planar drawing of K5 or K3,3. Since we know this is impossible, we could not have any planar drawing of the subdivided graphs.
3a. Since 3 ≤ g, the Edge-Region Inequality gives: 3r ≤ gr ≤ 2q. But since G is connected, we have r = 2 − n + q, so that 3(2 − n + q) ≤ 2q. Solving for q gives: q ≤ 3n − 6.
Now if G, with q edges, is disconnected or has no cycles, then we can draw extra edges to connect all the components and to produce cycles, giving a graph G' with q' edges. Then q' ≤ q ≤ 3n − 6.
3b. Kn has q = ½n(n−1), which is maximal planar if ½n(n−1) = 3n−6. Solving gives n = 3,4, which are indeed maximal planar: K3 is a triangle, and K4 can be drawn as a triangle with a vertex in its center and an edge to each corner.
3c. If a graph has any regions with 4 or more edges, then we can draw an extra edge across the region, without causing any edge-crossings. In fact the maximal planar graphs are precisely those having only triangular regions (including the infinite region). Here triangular means 3 boundary edges, which may be drawn as curves.
2a. This graph cannot contain a subdivision of K5, since it does not have 5 vertices of degree 4, only 2 such vertices. But in the following diagram, the square and circle vertices can be taken as the two sides of a subdivision of K3,3, with two extra edges (broken lines).
2b. Again, this graph cannot contain a K5 subdivision, since all its vertices have degree 3. The figure shows a subdivision of K3,3 inside G: there are 3 red and 3 blue vertices, connected by 9 gray paths having no common vertices except endpoints. There is also an extra vertex, not part of K3,3, with its edges drawn as broken lines.
2c. The graph contains both a subdivision of K5 along with an extra edge (broken line), and a copy of K3,3 along with extra edges.
4a. Statement: If a graph G has gr ≤ 2q (where we define r = 2−n+q), then G is planar.
This is false for G = K5 + v + e, meaning the complete graph K5 together with an extra vertex v and an edge e to one of the previous 5 vertices. This is connected with n = 7, q = (5 | 2) + 1 = 11, r = 2−n+q = 6, g = 3, and the inequality gr = 18 ≤ 2q = 22 is valid. However, G is not planar, since it contains K5. This illustrates that gr ≤ 2q is a necessary condition for G to be planar, but not a sufficient condition.
4b. Statement: If a graph G has q ≤ 3n−6, then G is planar.
Again this is false, with the same counter-example: q = 11 ≤ 3n−6 = 12. Again the condition is necessary, but not sufficient.
4c. Statement: If a graph G contains no subdivision of K5 or K3,3, then G is planar.
This is true, and is one direction of Kuratowski's Theorem, Graph Notes III.7
2a. Twisted hexagonal drum: one 6-cycle inside another, with 12 edges zig-zagging between the two cycles.
2b. Tetrahedron: a complete graph K4, most naturally drawn as a triangle with a central vertex connected to each corner.
2c. Vertex-truncated tetrahedron: in the tetrahedron graph, make each vertex grow into a small triangle with the original three edges attached to the corners of the triangle.
2d. Permutahedron: in the previous graph (c), and make each edge grow into a long thin rectangle with the original four edges attached to its corners four corners.
2e. Similar to (c)
2f. Make the triangles in (e) grow until they squeeze out the edges betweem them, leaving only triangle and quadrilateral regions.
Basic Problems: Let S be a set of n distinct elements.
Typical example: How many ways to toss a coin 5 times with 3 heads, such as HTTHH? This naturally corresponds to lists like (H,T,T,H,H) with 3 H's and 2 T's, which cannot be easily counted with any of our usual principles or essential problems. Instead, we transform the data by recording the positions of the H's: (H,T,T,H,H) has an H in the first, fourth, and fifth positions, so it corresponds to the set {1,4,5}. Since there were 3 H's in the list, there are 3 elements in the set, which lies inside {1,2,3,4,5}. The transformation has the table:
list | HHHTT | HHTHT | HHTTH | HTHHT | HTHTH | HTTHH | THHHT | THHTH | THTHH | TTHHH |
set | {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} |
The point of this transformation is that it outputs all 3-element subsets of {1,2,...,5}, each just once, and we know how to count these: Basic Problem 3 tells us there are (5 | 3) = 10. Of course, in this case we can just write out all the lists and count them, but the argument works in general: the number of ways to get k heads out of n tosses is (n | k).
We could also record the positions of the 2 T's instead of the 3 H's, but this gives us the same answer, since (5 | 2) = (5 | 3), and in general (n | k) = (n | n−k).
We have seen the Position Transform in the following problems:
set S | {} | {1} | {2} | {3} | {1,2} | {1,3} | {2,3} | {1,2,3} |
list L | (−,−,−) | (+,−,−) | (−,+,−) | (−,−,+) | (+,+,−) | (+,−,+) | (−,+,+) | (+,+,+) |
The output is all lists of three +/− entries, and the Product Principle says there are 23 = 8 of these. Of course, in this case, we can just write all the sets and count them, but the argument works in general: The number of all subsets of {1,2,...,n} is 2n.
Now, a sequence of O's and |'s is determined by choosing which n − 1 of the k + n − 1 symbols are | ; this is a subset of n − 1 positions chosen from k + n − 1 . In the above example k + n − 1 = 11 :
which we know how to compute. For example, ((5 | 7)) = (11 | 4) = 114 / 4! = 330, or ((5 | 7)) = (11 | 7) = 117 / 7! = 330.
{1,2}∪{3,4} {1,3}∪{2,4} {1,4}∪{2,3} {2,3}∪{1,4} {2,4}∪{1,3} {3,4}∪{1,2}
{4}∪{1,2,3} {3}∪{1,2,4} {2}∪{1,3,4} {1}∪{2,3,4}.
{1,2}∪{3,4} {1,3}∪{2,4} {1,4}∪{2,3}.
f(x) = a0 + a1x + a2x2 + .... = ∑k≥0 ak xk .
logic | choose object of any size | ⇔ | basic choice adding size m | or | and |
algebra | f(x) = ∑k≥0 akxk | = | xm | + | × |
= (1+x+x2+...+x9)⁄(1−x10) × (1+x5)⁄(1−x10) × 1⁄(1−x10)
= (1+x+x2+...+x9) (1+x5) × 1⁄(1−x10)3
= (1+x+x2+x3+x4) (1+2x5+x10) × ∑j≥0 ((3 | j))x10j.
Finally, multiplying by (1+x+x2+x3+x4) shows a10j = a10j+1 = ... = a10j+4, and a10j+5 = a10j+6 = ... = a10j+9. These results are combinatorially mysterious: for example, how to see directly that there are 112 ways to make change for $1.00 with pennies, nickels, and dimes? Once again, the Method of Generating Functions is more clever with combinatorics than we are!
X = | 1 3 2 | G = {ε, ρ1, ρ2, τ1, τ2, τ3}, |
σ \ c
W
W W
B
W W
W
W B
W
B W
W
B B
B
B W
B
W B
B
B B
Row Counts
ε = (1)(2)(3)
× × × × × × × ×
8 = 23
ρ1 = (123)
× ×
2 = 21
ρ2 = (321)
× ×
2 = 21
τ1 = (1)(23)
× × × ×
4 = 22
τ2 = (2)(13)
× × × ×
4 = 22
τ3 = (3)(12)
× × × ×
4 = 22
|C| = ∑ |Gc| ⁄|G| =
6⁄6 +
2⁄6 +
2⁄6 +
2⁄6 +
2⁄6 +
2⁄6 +
2⁄6 +
6⁄6
= |S| / |G| =
1⁄6(23+21+21+22+22+22)
|
|
|
|
c = |
|
c = |
|
|
|
GRAPHS
We draw the edge: s1−−ℓ1 = 4−−2. Next σ2 = (s2) = (1) and V2 = V1−{ℓ1} = {1,3,4} Repeating this, we get ℓ2 = min(V2−σ2) = min{3,4} = 3, and we draw: ℓ2−−s2 = 3−−1. Now we are left with only σ2 = ( ) and V2 = V1−{ℓ2} = {1,4}, and we draw the final edge 1−−4 . This recovers the tree T = 2−−4−−1−−3 .
r = 2 − n + q n = 2 − r + q
q ≤ 3n−6 q ≤ 3r−6