21-301 Combinatorics CMU Qatar, Spring 2013 TEST-3 NAME: ........... ~.~.'!..· ............ . April18, 2013 1) (20 Points) ~nswer the following short questions. a) What IS the coefficient of x3 xz x 3 . h . ( 1 2 3X4 m t e expansion of xl -Xz + 2x3 - 3x4 Y? q! 2 . (-J)3 --3~ 2~ 3 I 3' l~ 3 I . • S" ft. I\ 11-e. ccef.(•<.:-ef\..J. . Jl 21 Jl b) Let A and B be finite sets ~ith .I AI =· 6 and IBI = 2 F" d h d" t" · . · m t enumberof IS met surJeCtive functions that can be defined f A fl. ~ rom onto B. ~Mrs v # of f-cAile:i i 1;)/IJ +kJ 0:•1 be. der ,.,ed. f~t¥\ A--lo 6 ;;. . -/o d.tbf,YVL.d prDrA A f tJ 1\ (., fi~l\ <; -/Aak (e;i/1 k #of {5 ' '). 6 · e.l e (t\IY\ 1-of IJ . I l::tw.J-\vi tl rli;Sf oil e... 6 6~ -'--::::;; 61. sur -Te G fi'Oil.S COA fkl\<..e_ 2. - 2 -.::"-ckr~ fro "A A g 15 B -k +o f>.2) (20 points) Prove that (n)-2(n) + 3(n) + ... + (-l)n-t (n) _ 0 c II .. 1 2 3 n -10r a pos1t1ve . l n mteger n> . ~'j l31nor{'\lcll +heof'e m fl ~ LeA-y = I I ~r1 (\ k X (X+I)f\ := 2_ (:)X\:_ for al\ X E:-\f<. C\f'd (\ E::ltJ I • ~=o '1:-- 1 X: -2 -3) (20 points) Prove the following equaltty y usmg a c . b · ombinatorial argument IJ (~) = n 2n-I . i=l l ~ fH . FONl- '-"e.. co'\ c hoe> >e... .J.he_ S.~e ctaA e I e men t 01 "d H" ; ccu, be.. done { ? ) = 1\ l\fS · We_ """ parldoo."' -l»e possible selec-l.oll b.,..sed_ o" -fhe s l le. Of f-~ s •led Oo ,.., f ; r r.J. . l e,f -, ~ ·th<!-si ~;>_ Of ..J. ~ 1£ le.a.-1 '0/1 . co., be_ c f)ase n ( f ) l,,) \>Ja'jS i C~) I:::: I -34) (20 points) What is the number of ways to place five non-attacking rooks on the 5-by-5 boards with forbidden positions as shown? X X X X X X X X X Co('~ pond,'~ 1"'00~ po \'j norn•'c. \s qre_ ( l +-S X + fiX1... t- )(3) and (I+ l.J.x +-2.x'l.. )8 C+ SY + ~xL -t _x'J. If l.tX t--L...xl. 5 ! - 9 4-~ -+ Zl: 3 ! -3-f 2... ~ + I;.. I ~ - 2 0! B 120 - ). I b + 16 1=--61.. +I~-L = I b 8 4 -,.. • 5) (20 points) Ofthe 16! orderings ofthe letters A, B, C, D, E, F, G, H, I, J, K, L, M, N, 0 , P how many are there such that we cannot obtain any of the words BAD, DEAF, APE by crossing out some letters? (Note that "LMNBEGHF ACIJDKPO" is not a desired permutation of the given letters, as after crossing out some letters, we can obtain the word "BAD".) Of }~ 9•v-eA It> le-f~rs '\'1./e COl\ obklf) <caA07> r_•~-+ -1 he ward... o ar ?t:r cro~•'AJ ou some.. of--t~ le..+kts Oe f.•~ A L o" d A:1. (e.s. pee + ;ve/t l.j [\.XAe need--f-o -f'" d ..fi-e_ By .\-~ ~llc\us\t:YI-exc lu.HD-'\ [A,(\ A, () A3 I= I ~I-(1At\+\A.\+IA3 \) -t ( \ f\, " A 2. \ -r ) A, r\ A~ \ + \ A1.-() A~) - I A , A A1. n As \ , e..+kJ>;S. ) \ ?> l •