18 312 Algebraic Combinatorics Lionel Levine Problem Set 4 Due at the beginning of class on Tuesday March 8 2011 P15 Let P Q R be finite posets Prove that P Q R P Q P R and P Q R P Q R P16 Let P be a finite poset An upper order ideal is a subset U P such that if x y and x U then y U An antichain is a subset A P such that no two elements of A are comparable that is if x y A are distinct then x 6 y and y 6 x Show that the number of order ideals upper order ideals and antichains of P are all equal P17 Let Dn be the set of positive divisors of n partially ordered by divisibility a Show that Dn is a lattice Is it distributive If so describe the poset Pn such that Dn J Pn b Show that Dmn Dm Dn If m and n are relatively prime P18 Let s s0 s1 s2 be a sequence with s0 1 satisfying both of the following linear recurrences sn 3 3sn 2 sn 1 2sn 0 sn 3 3sn 1 2sn 0 Find s100 4 1 P19 Let sm n m n 0 be an infinite two dimensional array sm n C such that each column obeys a linear recurrence k X ai sm i n 0 m n 0 i 0 and each row obeys a linear recurrence X bj sm n j 0 m n 0 j 0 Prove that the sequence sn n n 0 obeys a linear recurrence of order k Hint consider horizontal and vertical shift operators E and F and prove that the vector space spanned by the arrays E i F j s is finite dimensional 4 2
View Full Document
Unlocking...