15-344/Homework Assignment 9: Difference between revisions
(Created page with "{{15-344/Navigation}} {{In Preparation}} This assignment is due <span style="color: blue;">at the tutorials on Thursday December 3</span>. Here and everywhere, '''neatness cou...") |
No edit summary |
||
| Line 6: | Line 6: | ||
'''Solve''' problems ... in section ..., but submit only your solutions of the underlined problems. |
'''Solve''' problems ... in section ..., but submit only your solutions of the underlined problems. |
||
'''In addition,''' solve the following problem, but submit only your solutions to parts <u>2</u>, <u>3</u>, and <u>4</u>: |
|||
'''Part 1.''' For <math>n\geq 0</math>, let <math>C_n</math> be the <math>n</math>'th Catalan number, defined as the number of sequences of <math>n</math> <math>a</math>'s and <math>n</math> <math>b</math>'s in which in every initial segment there are at least as many <math>a</math>'s as <math>b</math>'s. Prove that for <math>n\geq 1</math>, <math>C_n=C_0C_{n-1}+C_1C_{n-2}+C_2C_{n-3}+\ldots+C_{n-1}C_0</math>. |
|||
'''Part 2.''' For <math>n\geq 1</math>, let <math>D_n</math> be the number of different ways of computing the product <math>A_1A_2\cdots A_n</math> of <math>n</math> matrices. Prove that for <math>n\geq 2</math>, <math>D_n=D_1D_{n-1}+D_2D_{n-2}+D_3D_{n-3}+\ldots+D_{n-1}D_1</math>. |
|||
'''Part 3.''' Let <math>E_2=1</math> and for <math>n\geq 3</math> let <math>E_n</math> be the number of triangulations of a convex <math>n</math>-gon using non-crossing diagonals. Prove that for <math>n\geq 3</math>, <math>E_n=E_2E_{n-1}+E_3E_{n-2}+E_4E_{n-3}+\ldots+E_{n-1}E_2</math>. |
|||
'''Part 4.''' Use the above three assertions to prove that for any <math>n\geq 0</math>, <math>C_n=D_{n+1}=E_{n+2}</math>. |
|||
{{15-344:Dror/Students Divider}} |
{{15-344:Dror/Students Divider}} |
||
Revision as of 16:35, 26 November 2015
The information below is preliminary and cannot be trusted! (v)
This assignment is due at the tutorials on Thursday December 3. Here and everywhere, neatness counts!! You may be brilliant and you may mean just the right things, but if the teaching assistants will be having hard time deciphering your work they will give up and assume it is wrong.
Reread sections 6.1-6.2 of our textbook, and your notes for November 26. Remember that reading math isn't like reading a novel! If you read a novel and miss a few details most likely you'll still understand the novel. But if you miss a few details in a math text, often you'll miss everything that follows. So reading math takes reading and rereading and rerereading and a lot of thought about what you've read. Also, preread chapter 7, just to get a feel for the future.
Solve problems ... in section ..., but submit only your solutions of the underlined problems.
In addition, solve the following problem, but submit only your solutions to parts 2, 3, and 4:
Part 1. For , let be the 'th Catalan number, defined as the number of sequences of 's and 's in which in every initial segment there are at least as many 's as 's. Prove that for , .
Part 2. For , let be the number of different ways of computing the product of matrices. Prove that for , .
Part 3. Let and for let be the number of triangulations of a convex -gon using non-crossing diagonals. Prove that for , .
Part 4. Use the above three assertions to prove that for any , .
| Dror's notes above / Students' notes below |
