-KE'f 21-301 Combinatorics CMU Qatar, Spring 2013 TEST-2 NAME: .................. : ............. . 1) (20 points) Recall the Reflected Gray Code of Order n: Begin with the n-tuple an-I an-2 ... ao = 0 0 ... 0. While the n-tuple an-I an-2 ... ao * 1 0 ... 0, Do the following: 1) Compute 0" (an-I an-2 ... ao) =an-I + an-2 + ... + ao. 2) If cr (an-I an-2 .. . ao) is even, then change ao . March 17,2013 3) Else, determine j such that ai = 1 and ai = 0 for all i with j > i, and then change aj+l A) Determine the immediate successors and predecessors of the following 9-tuples if this algorithm is used to list all subset of a set with 9 elements. I. 001100101 t'le'\t. +~C\ ~ <Y( 00 I\ 00 I 0 I ) -:= V 0 o I\ o 0 \ oo ~s. '\-~ II. 101100011 <t' ( 1 o 11 o oO I ' \ = S oo "A Sl.(cce ~sc r. \Q\\00~\0 B) Determine the subset of S = {A, C, D, F, H, M, T, U, Q} that immediately follows the subset whose binary coding is 010001001 if we apply above algorithm. (j' (OIDO 0 lOO l) -= 1 0\1\d +his IS CN\. o~ numbv' @ fc.M,U.~1-@)2) (20 points) Show~~ere is no simple graph with 12 vertices and 28 edges in which i. the degree of each vertex is either 3 or 4 S urpo~ +·he >e.. ex-IS-h :S\.le..h a. ~I"'Ctf'h. ' le.+ x. 'oe._ \-~ "'"'rl\~ of d~t'ee.. ~ ver·~ of G . ~~f\ l\2.-x) h 4~ num~ of. ~t-eL '+ vQrV of G . \~(\ we fl\i.t.\\-ha~ ·?> )( +-4L \1-X) .:= 56 3){ -t 't 8 -t,.x. -:=. s -b ) 4 g--56 :=-I( -=) .,.. -= -)5-11. the degree of each vertex is either 3 or 6. ';;u.f' 1'0">(. ~ ex..'.\-~ 'iuc \-I C\ 'ret(' k Le+ )(.. ~ +I-.e_ 1"\\(t"l\ ~ of ~r-e(_ c~ ve..r-le...~ Of G . I ~ef\ (I 2 ->< ) i\ +~ nuf'"i\~f of ~r-e.e.. b ~-4-ei-of G . '3)( -t 7-'2.-6x.. =-5 b 1-l.- 5 b -;::. 3 )( l (,:::- 3.< )C :::. ~ 3 2 -3) (20 points) Prove d' a) K ~ K K or tsprove following statements. 5 3, 3 b) K,o ~ K3, K4 Glv-tA ~o, n ~:@ Cot)srd-2-• C\ t\I.Jo-c..olcx~ of t\-.e... CO()".plek..-<j.-ph Kto. Lo} "'-k ex verk-< of K,o. LV-b Pe-T~ ~'""bet-oJ b lv.< v!.~ ""d. r 1>e.--\~ nurn\Jer. of oe.d e¥ """"-·h-1 ~ ". Ad r, b a~ ncf'{\€...!3oJ.;ve_ ~r-;'~\ u )0 \.e.. e.l-t~ r r-~ ""~ kA---:.4-6 . \~(\ r t-b -:::.. '\ ~~f) \oj (>~eP>~~\e._ or-.elc;.Q. 1o IS Gl\-c I-f, +her-e.. C\r-t.. 4 N,<i_ ~ cd-X 1 -t-~1\ If-(;lfl'j eJ cp.-ve .-hu. ~ are.. re-d I O~rv-•~ <!\. \,\....e. ~~"-~ f<>~Ar t~ ~~ ~ a. ~c:l \(3. \( 't \YI t~ v£.. 'f-\.v--<;,IV\-CZ l'4 , X1.-X~ )(~.1 I J , \ • t;~n r-(3., 1) ~b, -l:-M verh~ o.f -\-h.. I. 6 b\v-t. X cu -G\1\d ® ~~ fO' ro/\ 01 CO~VI.f ~ t<'(, i+ Col)~ •"f'. <; ~~ ~iH~. Q .-ed K1 ( t-1-e" we. o,e_ do ('(}_ ) ,. or e l\e. • K3. \H-1'-hz....e-or-+-h·s bl~ \(1 ~l 0 I:Jl.,u_ "\lt--W\~ ~ f'O r """--CA lo\.!4~ \( ~ . A"'~ we_ 0ve... ck"t . 34) (20 points) Consider the set Sa={1, 2, 3, 4, 5, 6, 7, 8}. a) Determine the inversion sequence of the permutation 35267814. 11-le tn~~lon..~ cf-+he 91~n ~rm~-+.-uo~ ar-e.. {3,2)1 (3,•), (.5,2.)1 (S,l) J (S,~) ( !2., I) I { b, I) I ( b, '-t } I ( '1-, I) I ( t, 't ) I (%I I) q "c. ( <6' It,-) . @ b) Construct a permutation of Sa whose inversion sequence is 6 6 1 4 2 1 0 0 ' ' ' ' ' ' ' . l : i 2 '. 1 ~ @ ~~ '3, -' 1--'3 .!:L i '1-t.,~ 3 2-_!t_ ( '2-s~ --!L J_ '2-6 ~ 3 b 5 -@ .!L !L t J... ]: 3 5 -]"- : -1-3:. 3 b 2 ~ '+ _1 9~ c) How many permutations of Sa have exactly 26 inversions? Nc4e.-\h£1A.. -+!..€_ r'Y\..ct;(.. 1')-..trn\:;le,:' o f rr'\v(rlt'o(\~ II\ &\ ferm..t..\.q~,ol'l of S"~ iS 2....&'. '\ 'bi s s c +"'-ct+ hi::: % - ; l-ie nc.e . 4 -5) (20 points) Consider the following three graphs. XI ~1-~·l-Only two o~the abo~e graphs are isomorphic. Determine these two graphs and then give a proof for tsomorphtsm. Le+\ Label +-1-e... v-er\-i'(LS o.f-6 •. (n_ CV\~ 61 O-s I 11 t~ f·~~Ae. @ l?ac.~ ~f'Qph ~CA-S. ord-er t1 lit eJ.Cje..~ 0\('\ci -\-~ ~~ ~~(\L(__ ( 4, 4 J • • • I 4-) . 0 I 0 0 o I 0 0 l 0 I \ 0 0 0 \ 0 \ \ 0 I 0 0 ~ G\ CW\d.. GL C) \ I \ o I \ 0 0 () \ () 5 0 I 0 \ ' 0 0 I 0 0 0 ' 0 l 0 0 I I 0 G,. 0 D I 0 I 0 0 f 0 1 0 { 0 I 0