CSE191                          Problem Set 9 Answer Key                     Fall 2013

(1) Note: Calculator values were optional.  For the exam, some Q's could ask you /not/ to write the    
    numerical answer, as an anti-cheating provision.
(c) ||X([A-Z])^7|| = 26^7.  (Calculator gives 8,031,810,176)
(d) Counting X itself as an unrepeatable letter, the answer is the number of lists of length 7
    without repetitions from 25 items, = C(25,7)*7! = 25!/18! = 25x24x23x22x21x20x19.  (Calculator gives 2,422,728,000)
(g) ||B([A-Z]^6)O|| = 26^6.  (Calculator gives 308,915,776)
(h) ||BO([A-Z]^6)|| + ||([A-Z]^6)BO|| *minus* ||BO([A-Z]^6)BO|| because those items were double-counted,
    = 2*26^6 - 26^4.   (Calculator gives 617,374,576)
	
(2) (a) Six places for the bride, other 5 places can be any subset of the remaining 9, but order matters.  So equals 6*P(9,5) = 6*(9*8*7*6*5).  (Calculator: 90,720)
    (b) Six places for the bride, 5 for the groom---they are distinct so that makes 30 not 5-choose-2 = 15.  Then a list of 4 from the remaining 8.  So = 30*P(8,4) = 30*8*7*6*5.  (Calculator: 50,400)
	(c) Bride in, groom out: 6*P(8,5).  Groom in, bride out: another 6*P(8,5) since those cases are exclusive.  So 12*8*7*6*5.   (calculator: 20,160)
	
(3) (a) 13-choose-10 = 13-choose-3 = 13*12*11/6 = 13*11*2 = 286.
    (b) Order matters, so P(13,10) which is (a)*10!  (Calculator: 286*10! = 1,037,836,800)
	(c) Choose all 3 women and 7 of 10 men, or 2 women and 8 of 10 men, or one woman and 9 men.  These options are mutually exclusive, so their counts add.  The answer is:
	C(3,3)*C(10,7) + C(3,2)C(10,8) + C(3,1)*C(10,9) = 1*120 + 3*45 + 3*10 = 285.  This checks out---the only option from (a) that isn't legal is choosing all 10 men.
	
(4) (a) ||[a-z]^6 \ [b-z]^6|| = 26^6 - 25^6, which my calculator gives
as 64,775,151.  (This fixes an earlier error of asserting that this was
also equal to 6*26^5, which calculator shows is a larger number: 71,288,256.
The difference is overcounting strings that have two or more a's.)
    (b) By similar logic, "having a or b" would be 26^6 - 24^6.  But the question asks for "having a /and/ b".  One can subtract out the strings having no `a' and then subtract out those having no `b'.  But this double-penalizes the 24^6 string having neither.  Removing the double-penalty makes 26^6 - 2*25^6 + 24^6.  (Calculator: 11,737,502)
	(c) Five places to put down "ab", then P(24,4) ways to fill the remaining places, = 5*24*23*22*21 (Calculator 1,275,120.  This fixes an earlier typo which taked on an extra "*20", giving 25,502,400.)
	(d) C(6,2) places to put down a and b (no "times 2" like in problem 2(b) since 'a' must come first), then P(24,4) places to put the rest, =- 15*24*23*22*21.  (Calculator: 3,825,360)
	
(5) Show that for all n >= 1, C(2n,2) = 2C(n,2) + n^2.  
    (a) For a combinatorial argument, C(2n,2) means the number of ways to choose 2 eggs from 2n of them.  Let n of the eggs be white and the other n brown.  Then the 2 eggs can be:
	() Both white: C(n,2) ways;
	() Both brown: another C(n,2) ways;
	() One of n white and one of n brown eggs: n^2 ways.
	These events are mutually exclusive, so the counts add.
	(b) Algebriacally, C(2n,2) = 2n(2n-1)/2 = n(2n-1).  And 2C(n,2) + n^2 = 2n(n-1)/2 + n^2 = n^2 - n + n^2 = 2n^2 - n = 2(n^2 - 1) too.
	

(6) The simplest argument IMHO, without induction, goes as follows: Suppose G has no vertex of degree n-1.  Then the possible degrees are 0 .. n-2.  This makes n-1 possible degrees for n nodes.  The pigeonhole principle (PHP) then gives the conclusion that there are 2 modes of the same degree.  So instead let v have degree n-1.  Then v has n-1 neighbors.  No neighbor can have degree 0, because it is connected at least to v.  If one has degree n-1, then we have the conclusion again.  So the last possibility is that the neighbors have degrees 1 .. n-2.  There are n-2 such values for the n-1 neighbors, so once again PHP yields the conclusion.

I don't recall exactly what I had in mind when I wrote the suggestion on the problem, but I think it involved the postulated vertex of degree n-1, and is anyway subsumed by the above argument.  Or I may have originally intended induction on vertices, which is more natural anyway.  We can do either at once: For any m >= 0 and n >= 2, let P(m) be the statement that any graph G with m edges and n nodes must have two or more nodes of equal degree.  The basis P(0) is trivially true, since we have n >= 2 nodes of degree 0.  So let m >= 1 be given.  To show P(m), let any G with m edges and n nodes be given.  If G does not have a node of degree n-1, the same pigeonhole argument kicks in.  So take v to be a node of degree n-1, and take G' to be the graph obtained by deleting v and all edges into v. The new graph G' has k = m - (n-1) edges.  By strong induction using IH P(k), G' has two nodes of equal degree.  Now in G, restoring v ups the degree of each of those nodes by 1.  So their degrees stay equal.  This proves P(m), and the result follows by strong induction.

Well if we define Q(n) to be the statement that any graph G on n nodes, and however-many edges, then G' needs only the simple induction hypothesis Q(n-1), and the argument goes through just like that.  You can also try this by inducting on isolated vertices rather than vertices of max degree.  If the graph has no isolated vertices, then since it is simple, the max degree is n-1 and so the degrees are all between 1 and n-1.  There are n-1 possible degree values for n vertices, so again by the pigeonhole principle, some two vertices have the same degree.
   
But the graph may have an isolated vertex, putting degree 0 into the picture.  But, then the max degree can't be n-1.  But there could be 2 isolated vertices...  To stop a "but spiral" from the get-go, define k to be the number of isolated vertices.  Then the other n-k vertices have degrees between 1 and (n-k)-1, and the pigeonhole principle finishes the job.  Here again you can actually get away without using induction at all.

Here is the induction on the number of vertices, let P(n) == all graphs on n vertices have two equal degrees.  Basis (n=2): whether it's (u)----(v) or (u)   (v) without an edge, the degrees of u and v are equal.  Ind. (n >= 3), assume (IH) P(n-1).  Let any G with n nodes be given.  If there is no isolated vertex, the pigeonhole reasoning in the first paragraph gives P(n) without using P(n-1).  If there is an isolated vertex, call it v, then let G' be the graph minus v.  Then |V(G')| = n-1, so by IH P(n-1), G' has two equal degrees.  Since restoring the isolated v does not change any other degree, this equality carries over into G.  Since G of size n is arbitrary, P(n) holds, so (\forall n)P(n) holds by induction, and the pigeon---or Monty Python parrot---is really dead by now.


(7) 26: For G1, ordering edges (a,b), (a,c), (a,d), (b,d), (c,d):
a: 11100  FYI: adjacency matrix: 0111
b: 10010                         1001
c: 01001                         1001
d: 00111                         0111
For G2, ordering (a,b), (a,d), (b,d), (b,e), (c,d), (c,e):
a: 110000      Adjacency matrix: 01010
b: 101100                        10011
c: 000011                        00011
d: 011010                        11100
e: 000101                        01100
28: In an adjacency matrix---and in an incidence matrix by the way---the sum of entries in the row for a vertex v equals the degree deg(v) of the vertex (in an undirected graph), and the outdegree deg^+(v) in a directed graph