Drorbn - User contributions [en]

15-344/Homework Assignment 10

2015-12-17T02:29:53Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due by Friday December 11 at 5PM. It can be submitted either to Gaurav during his office hours on Thursday December 10 at 3:30-5:30 or during his office hours on Friday December 11 at 4-5, both at 215 Huron room 1012. It can also be submitted to a drop box near Dror's office, Bahen 6178, at any time between Thursday December 10 at 5 and Friday December 11 at 5.

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''' your notes for November 26 through December 3. 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.

'''Solve''' and submit your solutions of the following three problems:

'''Problem 1.''' What is the probability that a soccer game with <math>2n</math> goals ends with a tie, and that this tie is the first tie in the game (except before the first goal)?

'''Problem 2.''' How many possible histories are there for a soccer game that ends with the score <math>(m,n)</math>, where <math>m>n</math>, if it is known that the first team is never behind the second?

'''Problem 3.''' Let <math>n</math> be a natural number. How many sequences of integers <math>0=a_1\leq a_2\leq\ldots\leq a_n</math> are there, such that <math>a_k<k</math> for every <math>1\leq k\leq n</math>? For example, for <math>n=3</math> the allowed sequences are 000, 001, 002, 011, and 012.

{{15-344:Dror/Students Divider}}

Homework Assignment 10 Solutions

'''1)What is the probability that a soccer game with <math>2n</math> goals ends with a tie, and that the tie is the first tie in the game (except before the first goal)?'''

'''A)''' <math>2n</math> goals ending with a tie means <math>n</math> goals each (<math>(n,n)</math> on the Catalan diagram). Number of possibilities with no tie before <math>(n,n)</math> is basically the number of possible paths to <math>(n,n)</math> without crossing the diagonal line. This is equal to:
<math>C_{n-1} = \frac{1}{n}\binom{2(n-1)}{n-1}</math>

Total number of possible games with <math>2n</math> goals is <math>\binom{2n}{n}</math>

The required probability is: <math>C_{n-1} = 2\frac{\frac{1}{n}\binom{2(n-1)}{n-1}}{\binom{2n}{n}}</math>

The reason why we multiply the probability by two is because there are two possible cases (either above the diagonal or below the diagonal).

'''2)How many possible histories are there for a soccer game that ends with the score <math>(m,n)</math>, where <math>m>n</math>, if it is known that the first team is never behind?'''

'''A)''' This can be thought of as an A-dominant game.
The total number of possibilities with end score <math>(n,m)</math> is <math>\binom{n+m}{n}</math>
Using Andre's Reflection, we need to find the number of good paths (A-dominant paths): Total paths - Bad paths (any paths that cross the diagonal) = Good Paths.

Number of Bad Paths to <math>(n,m) = \binom{n+m}{n-1}</math>, so using Andre's Reflection, we have

<math>\binom{n+m}{n} - \binom{n+m}{n-1} = \frac{(n+m)!}{n!m!} - \frac{(n+m)!}{(n-1)!(m+1)!}</math>

Simplifying it gives:

<math>\frac{(n+m)!(m-n+1)}{n!(m+1)!}</math>

'''3) Let <math>n</math> be a natural number. How many sequences of integers <math>0=a_1\leq a_2\leq\ldots\leq a_n</math> are there, such that <math>a_k<k</math> for every <math>1\leq k\leq n</math>? For example, for <math>n=3</math> the allowed sequences are 000, 001, 002, 011, and 012.'''

'''A)''' This could also be thought as an A-dominant game. We can think of each digit in a sequence as the score difference between the two teams at a certain point in the game. For example, <math>000</math> would mean the score started with a tie and ended with a tie. Likewise, <math>012</math> would mean that (starting from the right end), Team A led by two goals in the first third of the game, by one goal at half time and gave up another goal and tied the game in the end. In the 3 digit sequence case, the total goal in the game is 3 therefore sequences like <math>022</math> are not possible. (this would mean Team B was down by two goals and then scored two to tie the game -> 4 goals total). Therefore, for sequences of length <math>n</math>, the number number of sequences is <math>C_{n} = \frac{1}{n+1}\binom{2n}{n}</math>

15-344/Homework Assignment 7

2015-12-16T02:22:23Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due at the tutorials on Thursday November 19. 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 5.1-5.4 of our textbook. 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''' sections 5.5 and 6.1, just to get a feel for the future.

'''Solve''' problems 8, 10, 15, 20, 24, 28, and 29 in section 5.3 and problems 1, 3, 16, 39, 40, 63, and 65 in section 5.4, but submit only your solutions of the underlined problems.

{{15-344:Dror/Students Divider}}

Homework Assignment 7 Solution

'''15 How many 8-digit sequences are there involving exactly six different digits?'''

'''A)'''
We have 2 cases: 1 digit repeated three times (for example, 11123456) and 2 digits repeated (for example, 11223456)

For the first case, there are <math> \binom{10}{6} </math> ways to choose 6 digits from 10 digit choice. Then there are
<math>\frac{8!}{3!}</math> arrangements involving a triple digit and and <math>\binom{6}{1}</math> different triple digits possible (111,222 and so on).So, in total, we have: <math>\binom{10}{6} \binom{6}{1}\frac{8!}{3!}</math>

Similarly, for the second case, we have: <math>\binom{10}{6} \binom{6}{2}\frac{8!}{2!2!}</math>

The sum of the two cases gives the answer:

<math>\binom{10}{6}(\binom{6}{1}\frac{8!}{3!}+ \binom{6}{2}\frac{8!}{2!2!})</math>

'''24 How many arrangements of the word PREPOSTEROUS are there in which the five vowels are consecutive? '''

'''A)'''

We have P-2, R-2, E-2, O-2, S-2, T-1,U-1

The vowels are OOUEE and its variations.

The number of all the possible variations of OOUEE is: <math>\frac{5!}{2!2!}</math>

The remaining 7 letters can be arranged in <math>\frac{7!}{2!2!2!}</math> ways.

Also, there are 8 different positions for the vowel group in the word. For example, OOUEE_ _ _ _ _ _ _ and _ _ _ _ _ _ _ OOUEE

In total, <math>8\frac{5!}{4}\frac{7!}{8} = 151200 </math>

'''28 How many ways are there to place nine different rings on the four fingers of your right hand if
a) the order of the rings on a finger does not matter
b) the order of the rings on a finger is considered'''

'''A) a)'''
For each ring, we have a choice of being on 1 - 4th finger. So, we have <math> 4^9 </math> possible such ways.

'''A) b)''' First, without considering the different types of the rings, consider the distribution of the nine rings to four fingers:
<math> \binom{n+k-1}{k-1} = \binom{9+4-1}{4-1} = \binom{12}{3} </math>
If we consider the fact that the rings are all different, we have the permutations <math>9!</math> So, in total, <math>9!\binom{12}{3}</math> ways.

'''39 How many non-negative integer solutions are there to the equation <math> 2x_{1} + 2x_{2} + x_{3} + x_{4} = 12 </math>.'''

'''A)''' This can be viewed as a special type of distribution problems.

First we think of all the possible pairs of <math>x_{1}, x_{2} </math>. For example:

<math>x_{1} = 0, x_{2} = 0 \to x_{3}+x_{4} = 12 </math>

<math>x_{1} = 1, x_{2} = 0 \to x_{3}+x_{4} = 10 </math> (two such cases since we can interchange the role of x1 and x2)

and so on.

In total, we have:

<math>\binom{12+2-1}{2-1} + 2\binom{10+2-1}{2-1} + 3\binom{8+2-1}{2-1} ... + 7\binom{0+2-1}{2-1} = 140 ways</math>

15-344/Homework Assignment 7

2015-12-16T02:21:58Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due at the tutorials on Thursday November 19. 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 5.1-5.4 of our textbook. 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''' sections 5.5 and 6.1, just to get a feel for the future.

'''Solve''' problems 8, 10, 15, 20, 24, 28, and 29 in section 5.3 and problems 1, 3, 16, 39, 40, 63, and 65 in section 5.4, but submit only your solutions of the underlined problems.

{{15-344:Dror/Students Divider}}

Homework Assignment 7 Solution

'''15 How many 8-digit sequences are there involving exactly six different digits?'''

'''A)'''
We have 2 cases: 1 digit repeated three times (for example, 11123456) and 2 digits repeated (for example, 11223456)

For the first case, there are <math> \binom{10}{6} </math> ways to choose 6 digits from 10 digit choice. Then there are
<math>\frac{8!}{3!}</math> arrangements involving a triple digit and and <math>\binom{6}{1}</math> different triple digits possible (111,222 and so on).So, in total, we have: <math>\binom{10}{6} \binom{6}{1}\frac{8!}{3!}</math>

Similarly, for the second case, we have: <math>\binom{10}{6} \binom{6}{2}\frac{8!}{2!2!}</math>

The sum of the two cases gives the answer:

<math>\binom{10}{6}(\binom{6}{1}\frac{8!}{3!}+ \binom{6}{2}\frac{8!}{2!2!})</math>

'''24 How many arrangements of the word PREPOSTEROUS are there in which the five vowels are consecutive? '''

'''A)'''

We have P-2, R-2, E-2, O-2, S-2, T-1,U-1

The vowels are OOUEE and its variations.

The number of all the possible variations of OOUEE is: <math>\frac{5!}{2!2!}</math>

The remaining 7 letters can be arranged in <math>\frac{7!}{2!2!2!}</math> ways.

Also, there are 8 different positions for the vowel group in the word. For example, OOUEE_ _ _ _ _ _ _ and _ _ _ _ _ _ _ OOUEE

In total, <math>8\frac{5!}{4}\frac{7!}{8} = 151200 </math>

'''28 How many ways are there to place nine different rings on the four fingers of your right hand if
a) the order of the rings on a finger does not matter
b) the order of the rings on a finger is considered'''

'''A) a)'''
For each ring, we have a choice of being on 1 - 4th finger. So, we have <math> 4^9 </math> possible such ways.

'''A) b)''' First, without considering the different types of the rings, consider the distribution of the nine rings to four fingers:
<math> \binom{n+k-1}{k-1} = \binom{9+4-1}{4-1} = \binom{12}{3} </math>
If we consider the fact that the rings are all different, we have the permutations <math>9!</math> So, in total, <math>9!\binom{12}{3}</math> ways.

'''39 How many non-negative integer solutions are there to the equation <math> 2x_{1} + 2x_{2} + x_{3} + x_{4} = 12 </math>.'''

'''A)''' This can be viewed as a special type of distribution problems.

First we think of all the possible pairs of <math>x_{1}, x_{2} </math>. For example:

<math>x_{1} = 0, x_{2} = 0 \to x_{3}+x_{4} = 12 </math>

<math>x_{1} = 1, x_{2} = 0 \to x_{3}+x_{4} = 10 </math> (two such cases since we can interchange the role of x1 and x2)

In total, we have:

<math>\binom{12+2-1}{2-1} + 2\binom{10+2-1}{2-1} + 3\binom{8+2-1}{2-1} ... + 7\binom{0+2-1}{2-1} = 140 ways</math>

15-344/Homework Assignment 7

2015-12-16T02:21:31Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due at the tutorials on Thursday November 19. 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 5.1-5.4 of our textbook. 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''' sections 5.5 and 6.1, just to get a feel for the future.

'''Solve''' problems 8, 10, 15, 20, 24, 28, and 29 in section 5.3 and problems 1, 3, 16, 39, 40, 63, and 65 in section 5.4, but submit only your solutions of the underlined problems.

{{15-344:Dror/Students Divider}}

Homework Assignment 7 Solution

'''15 How many 8-digit sequences are there involving exactly six different digits?'''

'''A)'''
We have 2 cases: 1 digit repeated three times (for example, 11123456) and 2 digits repeated (for example, 11223456)

For the first case, there are <math> \binom{10}{6} </math> ways to choose 6 digits from 10 digit choice. Then there are
<math>\frac{8!}{3!}</math> arrangements involving a triple digit and and <math>\binom{6}{1}</math> different triple digits possible (111,222 and so on).So, in total, we have: <math>\binom{10}{6} \binom{6}{1}\frac{8!}{3!}</math>

Similarly, for the second case, we have: <math>\binom{10}{6} \binom{6}{2}\frac{8!}{2!2!}</math>

The sum of the two cases gives the answer:

<math>\binom{10}{6}(\binom{6}{1}\frac{8!}{3!}+ \binom{6}{2}\frac{8!}{2!2!})</math>

'''24 How many arrangements of the word PREPOSTEROUS are there in which the five vowels are consecutive? '''

'''A)'''

We have P-2, R-2, E-2, O-2, S-2, T-1,U-1

The vowels are OOUEE and its variations.

The number of all the possible variations of OOUEE is: <math>\frac{5!}{2!2!}</math>

The remaining 7 letters can be arranged in <math>\frac{7!}{2!2!2!}</math> ways.

Also, there are 8 different positions for the vowel group in the word. For example, OOUEE_ _ _ _ _ _ _ and _ _ _ _ _ _ _ OOUEE

In total, <math>8\frac{5!}{4}\frac{7!}{8} = 151200 </math>

'''28 How many ways are there to place nine different rings on the four fingers of your right hand if
a) the order of the rings on a finger does not matter
b) the order of the rings on a finger is considered'''

'''A) a)'''
For each ring, we have a choice of being on 1 - 4th finger. So, we have <math> 4^9 </math> possible such ways.

'''A) b)''' First, without considering the different types of the rings, consider the distribution of the nine rings to four fingers:
<math> \binom{n+k-1}{k-1} = \binom{9+4-1}{4-1} = \binom{12}{3} </math>
If we consider the fact that the rings are all different, we have the permutations <math>9!</math> So, in total, <math>9!\binom{12}{3}</math> ways.

'''39 How many non-negative integer solutions are there to the equation <math> 2x_{1} + 2x_{2} + x_{3} + x_{4} = 12 </math>.'''

'''A)''' This can be viewed as a special type of distribution problems.
First we think of all the possible pairs of <math>x_{1}, x_{2} </math>. For example:

<math>x_{1} = 0, x_{2} = 0 \to x_{3}+x_{4} = 12 </math>
<math>x_{1} = 1, x_{2} = 0 \to x_{3}+x_{4} = 10 </math> (two such cases since we can interchange the role of x1 and x2)

In total, we have:

<math>\binom{12+2-1}{2-1} + 2\binom{10+2-1}{2-1} + 3\binom{8+2-1}{2-1} ... + 7\binom{0+2-1}{2-1} = 140 ways</math>

15-344/Homework Assignment 7

2015-12-16T02:11:18Z

ChrisKim:

15-344/Homework Assignment 8

2015-12-16T02:03:55Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due at the tutorials on Thursday November 26. 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 5.1-5.5 of our textbook. 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''' sections 6.1-6.3, just to get a feel for the future.

'''Solve and submit''' problems 7, 9a, 11, and 15 in section 5.5. (9b was originally also assigned, but it is too difficult).

{{15-344:Dror/Students Divider}}

Homework Assignment 8 Solution

'''9a) Show by combinatorial argument that <math>\binom{2n}{n} = 2 \binom{n}{2} + n^2 </math>'''

'''A)'''Split <math> 2n </math> into two groups of n. Then choosing 2 out of <math> 2n </math> can be seen as either choosing 2 from group 1 only
, which is <math>\binom{n}{2} </math> or 2 from group 2 only, which is also <math>\binom{n}{2} </math>, or one from each group, which is
<math> n^2 </math>. Their sum gives the total number of possibilities, which is exactly the right hand side of the equality.

15-344/Homework Assignment 9

2015-12-16T02:03:26Z

ChrisKim:

{{15-344/Navigation}}
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 and December 1. 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 2abde, 2c, 4abc, 4d, 12, 16, 20, and 25 in section 6.1 and problems 1, 2, 11abcd, 11e, 30, 32, and 43 in section 6.2, but submit only your solutions of the underlined problems.

'''In addition,''' solve the following problem. There is no need to submit your solution.

'''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 words made 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>.

''Hint.'' If <math>w</math> is such a word, let <math>k\geq 1</math> be the smallest such that if you cut <math>w</math> after <math>2k</math> letters, then the number of <math>a</math>'s before the cut is equal to the number of <math>b</math>'s before the cut. What can you say about the part of <math>w</math> before the cut, and the part of <math>w</math> after the cut?

'''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>.

''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of <math>k</math> of the matrices with the product of <math>n-k</math> of the matrices.

'''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>.

''Hint.'' Choose one edge of the <math>n</math>-gon, and consider the triangle on top of it, what's to its left, and what's to its right.

'''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}}

Homework Assignment 9 Solution

'''2) Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.'''

c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.

'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>

For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>

In total, we have <math>g(x) = (x^2+x^4+x^6)(x^3+x^5+x^7)(x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

'''4 d) Three different boxes with at most five objects in the first box'''

'''A)''' <math>e_{1}+e_{2}+e_{3} = r</math> with <math>0\leq e_{1} \leq 5</math>

For <math>e_{1}</math>, we have <math> (1+x+x^2+x^3+x^4+x^5) </math>

Note that for the other two, we don't have a limit, so:

<math>\sum_{k=0}^{\infty}x^{k} = \frac{1}{1-x} </math>

so, in total we have: <math> g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 </math>

'''16) Find a generating function for the number of integers between 0 and 999,999 whose sum of digits is <math> r </math>.'''

'''A)''' For each integer in the range, we can express them as a six digit number, including 0's in the front (5 will be 000005).
So this amounts to finding:

<math> e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6} = r , 0 \leq e_{i} \leq 9 , 1 \leq i \leq 6 </math>

So, we have <math> g(x) = (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^6 </math>

'''Section 6.1 2) Find the coefficient of <math> x^r </math> in <math> (x^5 + x^6 + x^7 +...)^8</math>'''

'''A)'''

<math>(x^5 + x^6 + x^7 +...)^8 = (x^5(1+ x + x^2 ...))^8 = x^{40} \frac{1}{(1-x)^8} </math>

The coefficient of <math> x^r </math> in this will be of <math> x^{r-40} </math> in <math> (1-x)^{-8} </math>, which is

<math>\binom{(r-40) + 8 - 1}{r-40} </math>

15-344/Homework Assignment 7

2015-12-16T02:01:04Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due at the tutorials on Thursday November 19. 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 5.1-5.4 of our textbook. 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''' sections 5.5 and 6.1, just to get a feel for the future.

'''Solve''' problems 8, 10, 15, 20, 24, 28, and 29 in section 5.3 and problems 1, 3, 16, 39, 40, 63, and 65 in section 5.4, but submit only your solutions of the underlined problems.

{{15-344:Dror/Students Divider}}

Homework Assignment 8 Solution

'''15 How many 8-digit sequences are there involving exactly six different digits?'''

'''A)'''
We have 2 cases: 1 digit repeated three times (for example, 11123456) and 2 digits repeated (for example, 11223456)

For the first case, there are <math> \binom{10}{6} </math> ways to choose 6 digits from 10 digit choice. Then there are
<math>\frac{8!}{3!}</math> arrangements involving a triple digit and and <math>\binom{6}{1}</math> different triple digits possible (111,222 and so on).So, in total, we have: <math>\binom{10}{6} \binom{6}{1}\frac{8!}{3!}</math>

Similarly, for the second case, we have: <math>\binom{10}{6} \binom{6}{2}\frac{8!}{2!2!}</math>

The sum of the two cases gives the answer:

<math>\binom{10}{6}(\binom{6}{1}\frac{8!}{3!}+ \binom{6}{2}\frac{8!}{2!2!})</math>

'''24 How many arrangements of the word PREPOSTEROUS are there in which the five vowels are consecutive? '''

'''A)'''

We have P-2, R-2, E-2, O-2, S-2, T-1,U-1

The vowels are OOUEE and its variations.

The number of all the possible variations of OOUEE is: <math>\frac{5!}{2!2!}</math>

The remaining 7 letters can be arranged in <math>\frac{7!}{2!2!2!}</math> ways.

Also, there are 8 different positions for the vowel group in the word. For example, OOUEE_ _ _ _ _ _ _ and _ _ _ _ _ _ _ OOUEE

In total, <math>8\frac{5!}{4}\frac{7!}{8} = 151200 </math>

'''28 How many ways are there to place nine different rings on the four fingers of your right hand if
a) the order of the rings on a finger does not matter
b) the order of the rings on a finger is considered'''

'''A) a)'''
For each ring, we have a choice of being on 1 - 4th finger. So, we have <math> 4^9 </math> possible such ways.

'''A) b)''' First, without considering the different types of the rings, consider the distribution of the nine rings to four fingers:
<math> \binom{n+k-1}{k-1} = \binom{9+4-1}{4-1} = \binom{12}{3} </math>
If we consider the fact that the rings are all different, we have the permutations <math>9!</math> So, in total, <math>9!\binom{12}{3}</math> ways.

15-344/Homework Assignment 7

2015-12-16T01:47:59Z

ChrisKim:

15-344/Homework Assignment 7

2015-12-16T01:47:34Z

ChrisKim:

15-344/Homework Assignment 7

2015-12-16T01:36:57Z

ChrisKim:

15-344/Homework Assignment 8

2015-12-16T01:24:24Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due at the tutorials on Thursday November 26. 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 5.1-5.5 of our textbook. 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''' sections 6.1-6.3, just to get a feel for the future.

'''Solve and submit''' problems 7, 9a, 11, and 15 in section 5.5. (9b was originally also assigned, but it is too difficult).

{{15-344:Dror/Students Divider}}

Homework Assignment 8 Solution

'''9a)''' Show by combinatorial argument that <math>\binom{2n}{n} = 2 \binom{n}{2} + n^2 </math>

'''A)'''Split <math> 2n </math> into two groups of n. Then choosing 2 out of <math> 2n </math> can be seen as either choosing 2 from group 1 only
, which is <math>\binom{n}{2} </math> or 2 from group 2 only, which is also <math>\binom{n}{2} </math>, or one from each group, which is
<math> n^2 </math>. Their sum gives the total number of possibilities, which is exactly the right hand side of the equality.

15-344/Homework Assignment 8

2015-12-16T01:24:10Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due at the tutorials on Thursday November 26. 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 5.1-5.5 of our textbook. 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''' sections 6.1-6.3, just to get a feel for the future.

'''Solve and submit''' problems 7, 9a, 11, and 15 in section 5.5. (9b was originally also assigned, but it is too difficult).

{{15-344:Dror/Students Divider}}

Homework Assignment 8 Solution

'''9a)''' Show by combinatorial argument that <math>\binom{2n}{n} = 2 \binom{n}{2} + n^2 </math>

Split <math> 2n </math> into two groups of n. Then choosing 2 out of <math> 2n </math> can be seen as either choosing 2 from group 1 only
, which is <math>\binom{n}{2} </math> or 2 from group 2 only, which is also <math>\binom{n}{2} </math>, or one from each group, which is
<math> n^2 </math>. Their sum gives the total number of possibilities, which is exactly the right hand side of the equality.

15-344/Homework Assignment 9

2015-12-16T00:50:30Z

ChrisKim:

{{15-344/Navigation}}
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 and December 1. 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 2abde, 2c, 4abc, 4d, 12, 16, 20, and 25 in section 6.1 and problems 1, 2, 11abcd, 11e, 30, 32, and 43 in section 6.2, but submit only your solutions of the underlined problems.

'''In addition,''' solve the following problem. There is no need to submit your solution.

'''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 words made 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>.

''Hint.'' If <math>w</math> is such a word, let <math>k\geq 1</math> be the smallest such that if you cut <math>w</math> after <math>2k</math> letters, then the number of <math>a</math>'s before the cut is equal to the number of <math>b</math>'s before the cut. What can you say about the part of <math>w</math> before the cut, and the part of <math>w</math> after the cut?

'''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>.

''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of <math>k</math> of the matrices with the product of <math>n-k</math> of the matrices.

'''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>.

''Hint.'' Choose one edge of the <math>n</math>-gon, and consider the triangle on top of it, what's to its left, and what's to its right.

'''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}}

Homework Assignment 9 Solution

'''2)''' Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.

c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.

'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>

For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>

In total, we have <math>g(x) = (x^2+x^4+x^6)(x^3+x^5+x^7)(x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

'''4 d) ''' Three different boxes with at most five objects in the first box

'''A)''' <math>e_{1}+e_{2}+e_{3} = r</math> with <math>0\leq e_{1} \leq 5</math>

For <math>e_{1}</math>, we have <math> (1+x+x^2+x^3+x^4+x^5) </math>

Note that for the other two, we don't have a limit, so:

<math>\sum_{k=0}^{\infty}x^{k} = \frac{1}{1-x} </math>

so, in total we have: <math> g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 </math>

'''16)''' Find a generating function for the number of integers between 0 and 999,999 whose sum of digits is <math> r </math>.

'''A)''' For each integer in the range, we can express them as a six digit number, including 0's in the front (5 will be 000005).
So this amounts to finding:

<math> e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6} = r , 0 \leq e_{i} \leq 9 , 1 \leq i \leq 6 </math>

So, we have <math> g(x) = (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^6 </math>

'''Section 6.1 2) Find the coefficient of <math> x^r </math> in <math> (x^5 + x^6 + x^7 +...)^8</math>'''

'''A)'''

<math>(x^5 + x^6 + x^7 +...)^8 = (x^5(1+ x + x^2 ...))^8 = x^{40} \frac{1}{(1-x)^8} </math>

The coefficient of <math> x^r </math> in this will be of <math> x^{r-40} </math> in <math> (1-x)^{-8} </math>, which is

<math>\binom{(r-40) + 8 - 1}{r-40} </math>

15-344/Homework Assignment 9

2015-12-16T00:49:58Z

ChrisKim:

{{15-344/Navigation}}
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 and December 1. 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 2abde, 2c, 4abc, 4d, 12, 16, 20, and 25 in section 6.1 and problems 1, 2, 11abcd, 11e, 30, 32, and 43 in section 6.2, but submit only your solutions of the underlined problems.

'''In addition,''' solve the following problem. There is no need to submit your solution.

'''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 words made 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>.

''Hint.'' If <math>w</math> is such a word, let <math>k\geq 1</math> be the smallest such that if you cut <math>w</math> after <math>2k</math> letters, then the number of <math>a</math>'s before the cut is equal to the number of <math>b</math>'s before the cut. What can you say about the part of <math>w</math> before the cut, and the part of <math>w</math> after the cut?

'''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>.

''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of <math>k</math> of the matrices with the product of <math>n-k</math> of the matrices.

'''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>.

''Hint.'' Choose one edge of the <math>n</math>-gon, and consider the triangle on top of it, what's to its left, and what's to its right.

'''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}}

Homework Assignment 9 Solution

'''2)''' Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.

c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.

'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>

For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>

In total, we have <math>g(x) = (x^2+x^4+x^6)(x^3+x^5+x^7)(x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

'''4 d) ''' Three different boxes with at most five objects in the first box

'''A)''' <math>e_{1}+e_{2}+e_{3} = r</math> with <math>0\leq e_{1} \leq 5</math>

For <math>e_{1}</math>, we have <math> (1+x+x^2+x^3+x^4+x^5) </math>

Note that for the other two, we don't have a limit, so:

<math>\sum_{k=0}^{\infty}x^{k} = \frac{1}{1-x} </math>

so, in total we have: <math> g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 </math>

'''16)''' Find a generating function for the number of integers between 0 and 999,999 whose sum of digits is <math> r </math>.

'''A)''' For each integer in the range, we can express them as a six digit number, including 0's in the front (5 will be 000005).
So this amounts to finding:

<math> e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6} = r , 0 \leq e_{i} \leq 9 , 1 \leq i \leq 6 </math>

So, we have <math> g(x) = (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^6 </math>

'''Section 6.1 2) Find the coefficient of <math> x^r </math> in <math> (x^5 + x^6 + x^7 +...)^8</math>'''

'''A'''

<math>(x^5 + x^6 + x^7 +...)^8 = (x^5(1+ x + x^2 ...))^8 = x^{40} \frac{1}{(1-x)^8} </math>

The coefficient of <math> x^r </math> in this will be of <math> x^{r-40} </math> in <math> (1-x)^{-8} </math>, which is

<math>\binom{(r-40) + 8 - 1}{r-40} </math>

15-344/Homework Assignment 9

2015-12-16T00:36:18Z

ChrisKim:

{{15-344/Navigation}}
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 and December 1. 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 2abde, 2c, 4abc, 4d, 12, 16, 20, and 25 in section 6.1 and problems 1, 2, 11abcd, 11e, 30, 32, and 43 in section 6.2, but submit only your solutions of the underlined problems.

'''In addition,''' solve the following problem. There is no need to submit your solution.

'''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 words made 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>.

''Hint.'' If <math>w</math> is such a word, let <math>k\geq 1</math> be the smallest such that if you cut <math>w</math> after <math>2k</math> letters, then the number of <math>a</math>'s before the cut is equal to the number of <math>b</math>'s before the cut. What can you say about the part of <math>w</math> before the cut, and the part of <math>w</math> after the cut?

'''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>.

''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of <math>k</math> of the matrices with the product of <math>n-k</math> of the matrices.

'''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>.

''Hint.'' Choose one edge of the <math>n</math>-gon, and consider the triangle on top of it, what's to its left, and what's to its right.

'''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}}

Homework Assignment 9 Solution

'''2)''' Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.

c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.

'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>

For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>

In total, we have <math>g(x) = (x^2+x^4+x^6)(x^3+x^5+x^7)(x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

'''4 d) ''' Three different boxes with at most five objects in the first box

'''A)''' <math>e_{1}+e_{2}+e_{3} = r</math> with <math>0\leq e_{1} \leq 5</math>

For <math>e_{1}</math>, we have <math> (1+x+x^2+x^3+x^4+x^5) </math>

Note that for the other two, we don't have a limit, so:

<math>\sum_{k=0}^{\infty}x^{k} = \frac{1}{1-x} </math>

so, in total we have: <math> g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 </math>

'''16)''' Find a generating function for the number of integers between 0 and 999,999 whose sum of digits is <math> r </math>.

'''A)''' For each integer in the range, we can express them as a six digit number, including 0's in the front (5 will be 000005).
So this amounts to finding:

<math>e_{1}+e_{2}+e_{3}+e_{4}+e_{5}+e_{6} = r , 0 \leq e_{i} \leq 9 , 1 \leq i \leq 6 </math>

So, we have <math> g(x) = (1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)^6

15-344/Homework Assignment 9

2015-12-16T00:31:12Z

ChrisKim:

{{15-344/Navigation}}
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 and December 1. 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 2abde, 2c, 4abc, 4d, 12, 16, 20, and 25 in section 6.1 and problems 1, 2, 11abcd, 11e, 30, 32, and 43 in section 6.2, but submit only your solutions of the underlined problems.

'''In addition,''' solve the following problem. There is no need to submit your solution.

'''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 words made 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>.

''Hint.'' If <math>w</math> is such a word, let <math>k\geq 1</math> be the smallest such that if you cut <math>w</math> after <math>2k</math> letters, then the number of <math>a</math>'s before the cut is equal to the number of <math>b</math>'s before the cut. What can you say about the part of <math>w</math> before the cut, and the part of <math>w</math> after the cut?

'''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>.

''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of <math>k</math> of the matrices with the product of <math>n-k</math> of the matrices.

'''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>.

''Hint.'' Choose one edge of the <math>n</math>-gon, and consider the triangle on top of it, what's to its left, and what's to its right.

'''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}}

Homework Assignment 9 Solution

'''2)''' Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.

c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.

'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>

For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>

In total, we have <math>g(x) = (x^2+x^4+x^6)(x^3+x^5+x^7)(x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

'''4 d) ''' Three different boxes with at most five objects in the first box

'''A)''' <math>e_{1}+e_{2}+e_{3} = r</math> with <math>0\leq e_{1} \leq 5</math>

For <math>e_{1}</math>, we have <math> (1+x+x^2+x^3+x^4+x^5) </math>

Note that for the other two, we don't have a limit, so:

<math>\sum_{k=0}^{\infty}x^{k} = \frac{1}{1-x} </math>

so, in total we have: <math> g(x) = (1+x+x^2+x^3+x^4+x^5)(\frac{1}{1-x})^2 </math>

15-344/Homework Assignment 9

2015-12-16T00:22:56Z

ChrisKim:

{{15-344/Navigation}}
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 and December 1. 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 2abde, 2c, 4abc, 4d, 12, 16, 20, and 25 in section 6.1 and problems 1, 2, 11abcd, 11e, 30, 32, and 43 in section 6.2, but submit only your solutions of the underlined problems.

'''In addition,''' solve the following problem. There is no need to submit your solution.

'''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 words made 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>.

''Hint.'' If <math>w</math> is such a word, let <math>k\geq 1</math> be the smallest such that if you cut <math>w</math> after <math>2k</math> letters, then the number of <math>a</math>'s before the cut is equal to the number of <math>b</math>'s before the cut. What can you say about the part of <math>w</math> before the cut, and the part of <math>w</math> after the cut?

'''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>.

''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of <math>k</math> of the matrices with the product of <math>n-k</math> of the matrices.

'''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>.

''Hint.'' Choose one edge of the <math>n</math>-gon, and consider the triangle on top of it, what's to its left, and what's to its right.

'''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}}

Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations

[http://drorbn.net/dbnvp/12-267-121106.php A Lecture From MAT267 (Also Taught by Professor Bar-Natan)]

Homework Assignment 9 Solution

'''2)''' Build a generating function for <math>a_{r}</math>, the number of integer solutions to the following equations.

c) <math>e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}</math> even <math> e_{2} </math> odd.

'''A)''' For <math>e_{3}</math> and <math>e_{4}</math> together, we have <math>g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

For <math>e_{1}</math>, we have <math>g_{2}(x) = (x^2+x^4+x^6) </math>

For <math>e_{2}</math>, we have <math>g_{3}(x) = (x^3+x^5+x^7) </math>

In total, we have <math>g(x) = (x^2+x^4+x^6)(x^3+x^5+x^7)(x^2+x^3+x^4+x^5+x^6+x^7)^2 </math>

15-344/Homework Assignment 10

2015-12-16T00:07:15Z

ChrisKim:

15-344/Homework Assignment 10

2015-12-15T23:48:55Z

ChrisKim:

{{15-344/Navigation}}
This assignment is due by Friday December 11 at 5PM. It can be submitted either to Gaurav during his office hours on Thursday December 10 at 3:30-5:30 or during his office hours on Friday December 11 at 4-5, both at 215 Huron room 1012. It can also be submitted to a drop box near Dror's office, Bahen 6178, at any time between Thursday December 10 at 5 and Friday December 11 at 5.

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''' your notes for November 26 through December 3. 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.

'''Solve''' and submit your solutions of the following three problems:

'''Problem 1.''' What is the probability that a soccer game with <math>2n</math> goals ends with a tie, and that this tie is the first tie in the game (except before the first goal)?

'''Problem 2.''' How many possible histories are there for a soccer game that ends with the score <math>(m,n)</math>, where <math>m>n</math>, if it is known that the first team is never behind the second?

'''Problem 3.''' Let <math>n</math> be a natural number. How many sequences of integers <math>0=a_1\leq a_2\leq\ldots\leq a_n</math> are there, such that <math>a_k<k</math> for every <math>1\leq k\leq n</math>? For example, for <math>n=3</math> the allowed sequences are 000, 001, 002, 011, and 012.

{{15-344:Dror/Students Divider}}

Homework Assignment 10 Solutions

'''1)What is the probability that a soccer game with <math>2n</math> goals ends with a tie, and that the tie is the first tie in the game (except before the first goal)?'''

A) <math>2n</math> goals ending with a tie means <math>n</math> goals each (<math>(n,n)</math> on the Catalan diagram). Number of possibilities with no tie before <math>(n,n)</math> is basically the number of possible paths to <math>(n,n)</math> without crossing the diagonal line. This is equal to:
<math>C_{n-1} = \frac{1}{n}\binom{2(n-1)}{n-1}</math>

Total number of possible games with <math>2n</math> goals is <math>\binom{2n}{n}</math>

The required probability is: <math>C_{n-1} = 2\frac{\frac{1}{n}\binom{2(n-1)}{n-1}}{\binom{2n}{n}}</math>

The reason why we multiply the probability by two is because there are two possible cases (either above the diagonal or below the diagonal).

'''2)How many possible histories are there for a soccer game that ends with the score <math>(m,n)</math>, where <math>m>n</math>, if it is known that the first team is never behind?'''

A) This can be thought of as an A-dominant game.
The total number of possibilities with end score <math>(n,m)</math> is <math>\binom{n+m}{n}</math>
Using Andre's Reflection, we need to find the number of good paths (A-dominant paths): Total paths - Bad paths (any paths that cross the diagonal) = Good Paths.

Number of Bad Paths to <math>(n,m) = \binom{n+m}{n-1}</math>, so using Andre's Reflection, we have

<math>\binom{n+m}{n} - \binom{n+m}{n-1} = \frac{(n+m)!}{n!m!} - \frac{(n+m)!}{(n-1)!(m+1)!}</math>

Simplifying it gives:

<math>\frac{(n+m)!(m-n+1)}{n!(m+1)!}</math>

15-344/Homework Assignment 10

2015-12-15T23:39:32Z

ChrisKim:

15-344/Classnotes for Thursday September 17

2015-09-18T01:52:52Z

ChrisKim: /* Lecture Notes for September 17 */

{{15-344/Navigation}}

== Scanned Lecture Notes for September 17 ==

(Files not beginning with "15-344" were deleted).

== Lecture Notes for September 17 ==
'''DEFINITION 7 Isomorphism''' A graph <math>G_1 = (V_1, E_1)</math> is called ''isomorphic'' to a graph <math>G_2 = (V_2, E_2)</math> whenever
there exists a bijection <math>\phi:V_1 \rightarrow V_2</math> such that <math>\forall a,b\in V_1</math> we have <math>(ab)\in E_1</math> if and
only if <math>( \phi (a) \phi (b))\in E_2</math>. <math>G_1\sim G_2</math> means they are isomorphic to each other.

*A ''bijection'' is a one-to-one and on-to function. https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection

*Isomorphism does not mean two things are identical but means they are mathematically the same.

The relationship of isomorphisms:

1. '''Reflexive''': <math>G \sim G</math> A graph is isomorphic to itself

2. '''Symmetric:''' <math>G_1 \sim G_2 \implies G_2 \sim G_1 </math> In other words, for every <math>\phi:V_1 \rightarrow V_2</math> we have
<math>\phi ^{-1} :V_2 \rightarrow V_1</math>

3. '''Transitive:''' <math>G_1 \sim G_2 , G_2 \sim G_3 \implies G_1 \sim G_3 </math>

CLAIM If two graphs are isomorphic, then they have:

1. same number of vertices

2. same number of edges

3. vertex degrees (valencies) are the same between the two. For example, if one graph has 3 vertices of degree 2, and 2 vertices of degree 1,
then the other graph should have the same

4. same number of subgraphs

5. same number of complements denoted by <math>G^c = (V,E^c)</math>

*Complement means <math>(ab)\in E^c \Longleftrightarrow (ab)\notin E</math>

'''DEFINITION 8''' '''Subgraph''' A subgraph of a graph <math>G = (V,E)</math> is a graph <math>G' = (V',E')</math> such that <math>V'\subset V</math> and
<math>E'\subset E</math>.

*Checking if two graphs are isomorphic is a hard problem

15-344/Classnotes for Thursday September 17

2015-09-18T01:44:27Z

ChrisKim: /* Lecture Notes for September 17 */

15-344/Classnotes for Thursday September 17

2015-09-18T01:38:29Z

ChrisKim: /* Lecture Notes for September 17 */

15-344/Classnotes for Thursday September 17

2015-09-18T01:28:38Z

ChrisKim: /* Scanned Lecture Notes for September 17 */

15-344/Classnotes for Tuesday September 15

2015-09-18T01:03:46Z

ChrisKim: /* Lecture Note for September 15 */

{{15-344/Navigation}}

We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today.

{{15-344:Dror/Students Divider}}

== Lecture Note for September 15 ==

'''DEFINITION 1''' '''Graph''' A graph <math>G = (V,E)</math> is a set <math>V = \{a,b,...\}</math> (usually finite, "vertices")
along with a set <math>E = \{(ab),(bc),(bd),...\}</math> ("edges") of unordered pairs of distinct elements of
<math>V</math>.

'''DEFINITION 2''' '''Incident''' If an edge <math>e = (ab)\in{E}</math>, we say that <math>e</math> is incident to <math>a</math>
''and'' <math>b</math>.

'''DEFINITION 3''' '''N-valent''' In a graph <math>G = (V,E)</math>, a vertex <math>u \in{V}</math> is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where <math>n = 0,1,2,.. </math>.

'''DEFINITION 4''' '''Edge Cover''' An edge cover for graph <math>G = (V,E)</math> is a subset <math>C\subset{V}</math> such that every edge of <math>G</math> incident to at least one vertex in <math>C</math>.

'''DEFINITION 5''' '''Independent''' Let <math>G = (V,E)</math> be a graph. A subset <math>I\subset{V}</math> is called independent if whenever <math>a,b\in{I}</math>, then <math>(ab)\notin{E}</math>.

'''THEOREM 1''' Edge covers are complementary to independent sets. In other words, <math>C\subset{V}</math> is an edge cover if and only if
the complementary subset <math>V-C</math> is an independent set.

'''''Proof'''''
<math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent.
Indeed, if <math>e=(ab)\in{E}</math>, then since <math>C</math> is an edge cover, either <math>a\in{C} \implies a\notin{I}</math> or
<math>b\in{C} \implies b\notin{I}</math>, which implies <math>e</math> does not connect any two elements of <math>I</math>.

<math>(\leftarrow)</math> Assume <math>I=V-C</math> is independent. Pick any edge <math>e = (ab)\in{E}</math>. As <math>I</math> is independent,
<math>(ab)</math> does not connect any two members of <math>I</math>. Hence, either <math>a\notin{I} \implies a\in{C}</math> or <math>b\notin{I} \implies b\in{C}</math>, which implies <math>e</math> is incident to an element of <math>C</math>. QED

'''DEFINITION 6''' '''Matching''' is a subset of edges of a graph where no two edges share a common vertex. A matching is said to be perfect if
all edges in a graph are matched.

== Scanned Lecture Note for September 15 ==

<gallery>
Image:15-344-Sept15-1.jpg|Page 1
Image:15-344-Sept15-2.jpg|Page 2
</gallery>

15-344/Classnotes for Tuesday September 15

2015-09-16T02:49:18Z

ChrisKim: /* Lecture Note for September 15 */

15-344/Classnotes for Tuesday September 15

2015-09-16T02:49:04Z

ChrisKim: /* Lecture Note for September 15 */

{{15-344/Navigation}}

We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today.

{{15-344:Dror/Students Divider}}

== Lecture Note for September 15 ==

'''DEFINITION 1''' '''Graph''' A graph <math>G = (V,E)</math> is a set <math>V = \{a,b,...\}</math> (usually finite, "vertices")
along with a set <math>E = \{(ab),(bc),(bd),...\}</math> ("edges") of unordered pairs of distinct elements of
<math>V</math>.

'''DEFINITION 2''' '''Incident''' If an edge <math>e = (ab)\in{E}</math>, we say that <math>e</math> is incident to <math>a</math>
''and'' <math>b</math>.

'''DEFINITION 3''' '''N-valent''' In a graph <math>G = (V,E)</math>, a vertex <math>u \in{V}</math> is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where <math>n = 0,1,2,.. </math>.

'''DEFINITION 4''' '''Edge Cover''' An edge cover for graph <math>G = (V,E)</math> is a subset <math>C\subset{V}</math> such that every edge of <math>G</math> incident to at least one vertex in <math>C</math>.

'''DEFINITION 5''' '''Independent''' Let <math>G = (V,E)</math> be a graph. A subset <math>I\subset{V}</math> is called independent if whenever <math>a,b\in{I}</math>, then <math>(ab)\notin{E}</math>.

'''THEOREM 1''' Edge covers are complementary to independent sets. In other words, <math>C\subset{V}</math> is an edge cover if and only if
the complementary subset <math>V-C</math> is an independent set.

'''''Proof'''''
<math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent.
Indeed, if <math>e=(ab)\in{E}</math>, then since <math>C</math> is an edge cover, either <math>a\in{C} \implies a\notin{I}</math> or
<math>b\in{C} \implies b\notin{I}</math>, which implies <math>e</math> does not connect any two elements of <math>I</math>

<math>(\leftarrow)</math> Assume <math>I=V-C</math> is independent. Pick any edge <math>e = (ab)\in{E}</math>. As <math>I</math> is independent,
<math>(ab)</math> does not connect any two members of <math>I</math>. Hence, either <math>a\notin{I} \implies a\in{C}</math> or <math>b\notin{I} \implies b\in{C}</math>, which implies <math>e</math> is incident to an element of <math>C</math>. QED

15-344/Classnotes for Tuesday September 15

2015-09-16T02:44:43Z

ChrisKim: /* Lecture Note for September 15 */

{{15-344/Navigation}}

We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today.

{{15-344:Dror/Students Divider}}

== Lecture Note for September 15 ==

'''DEFINITION 1''' '''Graph''' A graph <math>G = (V,E)</math> is a set <math>V = \{a,b,...\}</math> (usually finite, "vertices")
along with a set <math>E = \{(ab),(bc),(bd),...\}</math> ("edges") of unordered pairs of distinct elements of
<math>V</math>.

'''DEFINITION 2''' '''Incident''' If an edge <math>e = (ab)\in{E}</math>, we say that <math>e</math> is incident to <math>a</math>
''and'' <math>b</math>.

'''DEFINITION 3''' '''N-valent''' In a graph <math>G = (V,E)</math>, a vertex <math>u \in{V}</math> is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where <math>n = 0,1,2,.. </math>.

'''DEFINITION 4''' '''Edge Cover''' An edge cover for graph <math>G = (V,E)</math> is a subset <math>C\subset{V}</math> such that every edge of <math>G</math> incident to at least one vertex in <math>C</math>.

'''DEFINITION 5''' '''Independent''' Let <math>G = (V,E)</math> be a graph. A subset <math>I\subset{V}</math> is called independent if whenever <math>a,b\in{I}</math>, then <math>(ab)\notin{E}</math>.

'''THEOREM 1''' Edge covers are complementary to independent sets. In other words, <math>C\subset{V}</math> is an edge cover if and only if
the complementary subset <math>V-C</math> is an independent set.

'''''Proof'''''
<math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent.
Indeed, if <math>e=(ab)\in{E}</math>, then since <math>C</math> is an edge cover, either <math>a\in{C} \implies a\notin{I}</math> or
<math>b\in{C} \implies b\notin{I}</math>, which implies <math>a,b</math> are not connected.

<math>(\leftarrow)</math> Assume <math>I=V-C</math> is independent. Pick any edge <math>e = (ab)\in{E}</math>. As <math>I</math> is independent,
<math>(ab)</math> does not connect any two members of <math>I</math>. Hence, either <math>a\notin{I} \implies a\in{C}</math> or <math>b\notin{I} \implies b\in{C}</math>, which implies <math>e</math> is incident to an element of <math>C</math>. QED

15-344/Classnotes for Tuesday September 15

2015-09-16T02:42:46Z

ChrisKim: /* Lecture Note for September 15 */

{{15-344/Navigation}}

We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today.

{{15-344:Dror/Students Divider}}

== Lecture Note for September 15 ==

'''DEFINITION 1''' '''Graph''' A graph <math>G = (V,E)</math> is a set <math>V = \{a,b,...\}</math> (usually finite, "vertices")
along with a set <math>E = \{(ab),(bc),(bd),...\}</math> ("edges") of unordered pairs of distinct elements of
<math>V</math>.

'''DEFINITION 2''' '''Incident''' If an edge <math>e = (ab)\in{E}</math>, we say that <math>e</math> is incident to <math>a</math>
''and'' <math>b</math>.

'''DEFINITION 3''' '''N-valent''' In a graph <math>G = (V,E)</math>, a vertex <math>u \in{V}</math> is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where <math>n = 0,1,2,.. </math>.

'''DEFINITION 4''' '''Edge Cover''' An edge cover for graph <math>G = (V,E)</math> is a subset <math>C\subset{V}</math> such that every edge of <math>G</math> incident to at least one vertex in <math>C</math>.

'''DEFINITION 5''' '''Independent''' Let <math>G = (V,E)</math> be a graph. A subset <math>I\subset{V}</math> is called independent if whenever <math>a,b\in{I}</math>, then <math>(ab)\notin{E}</math>.

'''THEOREM 1''' Edge covers are complementary to independent sets. In other words, <math>C\subset{V}</math> is an edge cover if and only if
the complementary subset <math>V-C</math> is an independent set.

'''''Proof'''''
<math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent.
Indeed, if <math>e=(ab)\in{E}</math>, then since <math>C</math> is an edge cover, either <math>a\in{C} \implies a\notin{I}</math> or
<math>b\in{C} \implies b\notin{I}</math>, which implies <math>a,b</math> are not connected.

<math>(\leftarrow)</math> Assume <math>I=V-C</math> is independent. Pick any edge <math>e = (ab)\in{E}</math>. As <math>I</math> is independent,
<math>(ab)</math> does not connect <math>a,b</math>. Hence, either <math>a\notin{I} \implies a\in{C}</math> or <math>b\notin{I} \implies b\in{C}</math>, which implies <math>e</math> is incident to an element of <math>C</math>. QED

15-344/Classnotes for Tuesday September 15

2015-09-16T02:41:20Z

ChrisKim: /* Lecture Note for September 15 */

{{15-344/Navigation}}

We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today.

{{15-344:Dror/Students Divider}}

== Lecture Note for September 15 ==

'''DEFINITION 1''' '''Graph''' A graph <math>G = (V,E)</math> is a set <math>V = \{a,b,...\}</math> (usually finite, "vertices")
along with a set <math>E = \{(ab),(bc),(bd),...\}</math> ("edges") of unordered pairs of distinct elements of
<math>V</math>.

'''DEFINITION 2''' '''Incident''' If an edge <math>e = (ab)\in{E}</math>, we say that <math>e</math> is incident to <math>a</math>
''and'' <math>b</math>.

'''DEFINITION 3''' '''N-valent''' In a graph <math>G = (V,E)</math>, a vertex <math>u \in{V}</math> is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where <math>n = 0,1,2,.. </math>.

'''DEFINITION 4''' '''Edge Cover''' An edge cover for graph <math>G = (V,E)</math> is a subset <math>C\subset{V}</math> such that every edge of <math>G</math> incident to at least one vertex in <math>C</math>.

'''DEFINITION 5''' '''Independent''' Let <math>G = (V,E)</math> be a graph. A subset <math>I\subset{V}</math> is called independent if whenever <math>a,b\in{I}</math>, then <math>(ab)\notin{E}</math>.

'''THEOREM 1''' Edge covers are complementary to independent sets. In other words, <math>C\subset{V}</math> is an edge cover if and only if
the complementary subset <math>V-C</math> is an independent set.

'''''Proof'''''
<math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent.
Indeed, if <math>e=(ab)\in{E}</math>, then since <math>C</math> is an edge cover, either <math>a\in{C} \implies a\notin{I}</math> or
<math>b\in{C} \implies b\notin{I}</math>, which implies <math>a,b</math> are not connected.

<math>(\leftarrow)</math> Assume <math>I=V-C</math> is independent. Pick any edge <math>e = (ab)\in{E}</math>. As <math>I</math> is independent,
<math>(ab)</math> does not connect <math>a,b</math>. Hence, either <math>a\notin{I} \implies a\in{C}</math> or <math>b\notin{I} \implies b\in{C}</math>, which implies <math>e</math> is incident to an element of <math>C</math>. QED

15-344/Classnotes for Tuesday September 15

2015-09-16T02:34:23Z

ChrisKim:

{{15-344/Navigation}}

We mostly went over {{Pensieve link|Classes/15-344-Combinatorics/DayOne.html|Day One Handout}} today.

{{15-344:Dror/Students Divider}}

== Lecture Note for September 15 ==

'''DEFINITION 1''' '''Graph''' A graph <math>G = (V,E)</math> is a set <math>V = \{a,b,...\}</math> (usually finite, "vertices")
along with a set <math>E = \{(ab),(bc),(bd),...\}</math> ("edges") of unordered pairs of distinct elements of
<math>V</math>.

'''DEFINITION 2''' '''Incident''' If an edge <math>e = (ab)\in{E}</math>, we say that <math>e</math> is incident to <math>a</math>
''and'' <math>b</math>.

'''DEFINITION 3''' '''N-valent''' In a graph <math>G = (V,E)</math>, a vertex <math>u \in{V}</math> is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where <math>n = 0,1,2,.. </math>.

'''DEFINITION 4''' '''Edge Cover''' An edge cover for graph <math>G = (V,E)</math> is a subset <math>C\subset{V}</math> such that every edge of <math>G</math> incident to at least one vertex in <math>C</math>.

'''DEFINITION 5''' '''Independent''' Let <math>G = (V,E)</math> be a graph. A subset <math>I\subset{V}</math> is called independent if whenever <math>a,b\in{I}</math>, then <math>(ab)\notin{E}</math>.

'''THEOREM 1''' Edge covers are complementary to independent sets. In other words, <math>C\subset{V}</math> is an edge cover if and only if
the complementary subset <math>V-C</math> is an independent set.

'''''Proof''''' <math>(\rightarrow)</math> Assume <math>C</math> is an edge cover. I assert that <math>I = V-C</math> is independent.
Indeed, if <math>e=(ab)\in{E}</math>, then since <math>C</math> is an edge cover, either <math>a\in{C} \implies a\notin{I}</math> or
<math>b\in{C} \implies b\notin{I}</math>, which implies they are not connected.