Problem set 8 Solution F(x)=-2-22x-22x2-23x3 +30+31x+32x2+33x3+ 39-2)+(32-21)x+(32-2) Thus, tn= 3n-2 Problem 7. Below is a combinatorial proof of an equation. What is the equation Proof. Stinky Peterson owns n newts, t toads, and s slugs. Conveniently, he lives in a dorm with n+t+s other students. The students are distinguishable, but creatures of the same variety are not distinguishable )Stinky wants to put one creature in each neighbor's bed. Let w be the set of all ways in which this can be done On one hand, he could first determine who gets the slugs. Then, he could decide who among his remaining neighbors has earned a toad. Therefore, W is equal to the expression on the left On the other hand, Stinky could first decide which people deserve newts and slugs and then, from among those, determine who truly merits a newt. This shows that WI is equal to the expression on the right Since both expressions are equal to w they must be equal to each other Combinatorial proofs are real proofs. They are not only rigorous, but also convey an intuitive understanding that a purely algebraic argument might not reveal. However, combinatorial proofs are usually less colorful than this one. Solution n+t+s/n+ n+t+s/n+s n+s Problem 8. Consider the following equation (a) Describe a set S of binary sequences whose size is given by the expression on the Solution. Let s be all 2n-bit sequences with exactly n+1 ones (b) Describe a way of partitioning S into disjoint subsets To,..., In-1 such that: k八k+1� �� � Problem Set 8 7 Solution. 1 2 2 − 23 3 F(x) = −20 − 2 x − 2 x x − . . . 1 2 3 3 + 30 + 3 x + 3 x 2 + 3 x + . . . 0 1 − 21 2 2 − (33 − 23 = (30 − 2 ) + (3 )x + (32 − 2 )x )x 3 − . . . n n Thus, tn = 3 − 2 . Problem 7. Below is a combinatorial proof of an equation. What is the equation? Proof. Stinky Peterson owns n newts, t toads, and s slugs. Conveniently, he lives in a dorm with n+t+s other students. (The students are distinguishable, but creatures of the same variety are not distinguishable.) Stinky wants to put one creature in each neighbor’s bed. Let W be the set of all ways in which this can be done. On one hand, he could first determine who gets the slugs. Then, he could decide who among his remaining neighbors has earned a toad. Therefore, |W| is equal to the expression on the left. On the other hand, Stinky could first decide which people deserve newts and slugs and then, from among those, determine who truly merits a newt. This shows that |W| is equal to the expression on the right. Since both expressions are equal to |W|, they must be equal to each other. (Combinatorial proofs are real proofs. They are not only rigorous, but also convey an intuitive understanding that a purely algebraic argument might not reveal. However, combinatorial proofs are usually less colorful than this one.) Solution. � � � � � � � � n + t + s n + t n + t + s n + s = s · t n + s · n Problem 8. Consider the following equation: � � n−1 � �� � 2n � n n = (*) n + 1 k k + 1 k=0 (a) Describe a set S of binary sequences whose size is given by the expression on the left. Solution. Let S be all 2n­bit sequences with exactly n + 1 ones. (b) Describe a way of partitioning S into disjoint subsets T0, . . . , Tn−1 such that: n n |Tk| = k k + 1