Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Enumerative Combinatorics, Math 245 Homework one
1. From Stanley’s book Chapter One: 1, 2.c, 9, 12, 14(d,e).
2. What is the number of k-subsets chosen from 1 to n containing no two consecutive integers?
3. What is the number of monotone increasing functions mapping the set {1, . . . , n} into itself?
4. Prove that the Catalan numbers give the cardinality of the set of Standard tableaux in a 2 × n rectangular diagram. A Standard tableaux for a 2 × n rectangular array of boxes is a way to arrange the numbers {1, 2, ..., 2n} in the boxes in such a way they increase across rows and down columns.
5. A Full binary tree is one where every node has either 2 or 0 children. Set up a bijection between binary trees with n nodes and full binary trees with 2n+1 nodes.
6. All points of the plane that have integer coordinates are colored red, blue, or green. Prove that there will always be rectangle whose vertices are all of the same color.
7. The number of partitions of n into (any number) of distinct terms is equal to the number of partitions of n into odd terms.
8. What is the number of conjugacy classes in the symmetric group Sn? Now, suppose you choose a permutation in Sn uniformly at random. What is the expected number of cycles?