1. (3 pts) Give a combinatorial proof of the identity that for all positive inte

Question

1. (3 pts) Give a combinatorial proof of the identity that for all positive integers n, that is, (0)2'4 G)2n-i +--+ (n 1)24 (JS-3". (hint: ternary strings.) 2. (3 pts) Give a combinatorial proof of the identity that for all positive integers n, 3. (4 pts) Let n be a fixed positive integer. Prove the following combinatorial identity TL k-1 in two different ways. (1) Use the binomial theorem to expand (x1)h. Differentiate both sides with respect to r. Then substitute in an appropriate value for x. (2) Give a combinatorial proof by designing a counting problem with the two sides both being the answer. (hint: consider selecting a committee with a designated chair from n people, where the committee size is unrestricted.)

Explanation / Answer

Let M=(mij)M=(mij) be a n×nn×n matrix of variables. Then this number counts the number of "rooted" submatrices whose row indices match the column indices. By "rooted" I mean there is a distinguished element in the submatrix.

Left hand side. Since the row and column indices must match, there are (nk)(nk) submatrices with dimensions k×kk×k, each of which could have exactly k2k2 roots. Summing this over kk gives ?nk=0k2(nk)?k=0nk2(nk)as the number of rooted matrices with matching row and column indices.

Right hand side. Now, lets re-do this count, but first choose the root cell (i,j)(i,j):

?

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.