15-344 - Revision history

Tonglin at 14:52, 16 December 2015

2015-12-16T14:52:04Z

← Older revision		Revision as of 10:52, 16 December 2015
Line 34:		Line 34:


	'''Explore the Textbook'''		'''Homework Problems Revisited: Explore the Textbook'''

	(Originally posted in the homework sectors after the corresponding homework was assigned, but moved to here for the readers' convenience.)		(Originally posted in the homework sectors after the corresponding homework was assigned, but moved to here for the readers' convenience.)

Tonglin at 03:14, 16 December 2015

2015-12-16T03:14:16Z

← Older revision		Revision as of 23:14, 15 December 2015
Line 72:		Line 72:
	'''(5).''' If you are reading section 7.1 in our textbook, you may find example 3 intriguing. Attempting to solve the problem without looking for a recurrence relation, I found a solution using graph theoretic tools (to be precise, Euler's formula).		'''(5).''' If you are reading section 7.1 in our textbook, you may find example 3 intriguing. Attempting to solve the problem without looking for a recurrence relation, I found a solution using graph theoretic tools (to be precise, Euler's formula).

	[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]		[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem (Tong Lin)]]

Tonglin at 00:58, 16 December 2015

2015-12-16T00:58:13Z

← Older revision		Revision as of 20:58, 15 December 2015
Line 36:		Line 36:
	'''Explore the Textbook'''		'''Explore the Textbook'''

	(Originally posted in the homework sectors, but moved to here for the readers' convenience)		(Originally posted in the homework sectors after the corresponding homework was assigned, but moved to here for the readers' convenience.)

Tonglin at 00:55, 16 December 2015

2015-12-16T00:55:42Z

← Older revision		Revision as of 20:55, 15 December 2015
Line 35:		Line 35:

	'''Explore the Textbook'''		'''Explore the Textbook'''

			(Originally posted in the homework sectors, but moved to here for the readers' convenience)

Tonglin at 00:48, 16 December 2015

2015-12-16T00:48:52Z

← Older revision		Revision as of 20:48, 15 December 2015
Line 29:		Line 29:


	'''(1).''' If you took [http://drorbn.net/?title=12-267 MAT267] (~~Also~~ ~~Taught~~ by Professor Bar-Natan), you may remember that Catalan number was discussed in a lecture.		'''(1).''' If you took [http://drorbn.net/?title=12-267 MAT267] (also taught by Professor Bar-Natan), you may remember that Catalan number was discussed in a lecture.

	[http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]		[http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]

Tonglin at 00:46, 16 December 2015

2015-12-16T00:46:48Z

← Older revision		Revision as of 20:46, 15 December 2015
Line 28:		Line 28:
	{{15-344:Dror/Students Divider}}		{{15-344:Dror/Students Divider}}

⚫	'''(1).''' If you are reading section 7.1 in our textbook, you may find example 3 intriguing. Attempting to solve the problem without looking for a recurrence relation, I found a solution using graph theoretic tools (to be precise, Euler's formula).

		⚫	'''(1).''' If you took [http://drorbn.net/?title=12-267 MAT267] (Also Taught by Professor Bar-Natan), you may remember that Catalan number was discussed in a lecture.
⚫	[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]

⚫	'''(2).''' If you took [http://drorbn.net/?title=12-267 MAT267] (Also Taught by Professor Bar-Natan), you may remember that Catalan number was discussed in a lecture.

	[http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]		[http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]


			'''Explore the Textbook'''


			'''(2).''' For Problem 10, Section 2.3, you may wonder how to untangle the knot without induction. Here is a possible way.

			[[Media:15-344-Solution For Circle Coloring Problem.pdf\|Solution to Circle Coloring Problem (Tong Lin)]]


			'''(3).''' In Problem 85, Section 5.2, we were asked to find the number of triangles formed by pieces of diagonals or outside edges of an n-gon, assuming throughout that no three lines were collinear. What if there is no such constraint? Attached are two papers that presented some general results.

			[https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]

			[http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]


			'''(4).'''In problem 29, Section 5.3, we were asked to prove that

			<math>\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}</math>, where <math>k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}</math>.

			It is tempting to think that this is a special case of some identity and that a general pattern can be found.

			Replacing <math>3</math> with any <math>m \in \mathbb{Z}_{>0}</math> and <math>10</math> with any <math>n \in \mathbb{Z}_{\geq0}</math> gives

			<math>\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n</math>

			Does it hold, or can it be generalized to a greater extent?

			Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].

			<math>(\sum_{i=1}^m x_i)^n = \sum_{k_1 + k_2 + \cdots + k_m = n} P(n, k_1, k_2, \ldots, k_m) \prod_{j=1}^m x_{j}^{k_{j}}</math>, where <math>m \in \mathbb{Z}_{>0}, n \in \mathbb{Z}_{\geq0}</math> and <math>x_1, \ldots, x_m\in \mathbb{R}</math>.

			For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].


		⚫	'''(5).''' If you are reading section 7.1 in our textbook, you may find example 3 intriguing. Attempting to solve the problem without looking for a recurrence relation, I found a solution using graph theoretic tools (to be precise, Euler's formula).

		⚫	[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]

Tonglin at 00:35, 16 December 2015

2015-12-16T00:35:13Z

← Older revision		Revision as of 20:35, 15 December 2015
Line 28:		Line 28:
	{{15-344:Dror/Students Divider}}		{{15-344:Dror/Students Divider}}

	If you are reading section 7.1 in our textbook, you may find example 3 intriguing. Attempting to solve the problem without looking for a recurrence relation, I found a solution using graph theoretic tools (to be precise, Euler's formula).		'''(1).''' If you are reading section 7.1 in our textbook, you may find example 3 intriguing. Attempting to solve the problem without looking for a recurrence relation, I found a solution using graph theoretic tools (to be precise, Euler's formula).

	[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]		[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]

			'''(2).''' If you took [http://drorbn.net/?title=12-267 MAT267] (Also Taught by Professor Bar-Natan), you may remember that Catalan number was discussed in a lecture.

			[http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]

Tonglin at 00:28, 16 December 2015

2015-12-16T00:28:51Z

← Older revision		Revision as of 20:28, 15 December 2015
Line 28:		Line 28:
	{{15-344:Dror/Students Divider}}		{{15-344:Dror/Students Divider}}

	If you are reading section 7.1 in our textbook, you may find example 3 intriguing. ~~There~~ is ~~actually~~ a ~~solution~~ to ~~this~~ ~~problem~~ using graph theoretic tools (to be precise, Euler's formula).		If you are reading section 7.1 in our textbook, you may find example 3 intriguing. Attempting to solve the problem without looking for a recurrence relation, I found a solution using graph theoretic tools (to be precise, Euler's formula).

	[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]		[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]

Tonglin at 00:26, 16 December 2015

2015-12-16T00:26:31Z

← Older revision		Revision as of 20:26, 15 December 2015
Line 27:		Line 27:

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

			If you are reading section 7.1 in our textbook, you may find example 3 intriguing. There is actually a solution to this problem using graph theoretic tools (to be precise, Euler's formula).

			[[Media:15-344-Plane Division.pdf \| Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]

Drorbn at 17:35, 5 November 2015

2015-11-05T17:35:26Z

← Older revision		Revision as of 13:35, 5 November 2015
Line 23:		Line 23:

	* My {{Pensieve Link\|Classes/15-344-Combinatorics/\|15-344 notebook}}.		* My {{Pensieve Link\|Classes/15-344-Combinatorics/\|15-344 notebook}}.

			* [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].

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