https://drorbn.net/api.php?action=feedcontributions&feedformat=atom&user=Tonglin 2026-05-05T14:17:54Z User contributions MediaWiki 1.39.6 https://drorbn.net/index.php?title=15-344/Register_of_Good_Deeds&diff=15234 2016-01-04T14:53:04Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> '''Important.''' The good deed points are extra, bonus, a treat. If you got some you should be happy. But if you got none, so what? You are still eligible to get an A+ in this class just going the normal routes.<br /> <br /> {| align=center border=1 cellspacing=0 cellpadding=3<br /> |- align=center<br /> !User id<br /> !Deed or deeds<br /> !All contributions<br /> !Points<br /> {{15-344/Good Deeds|uid=Alibadba|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Andrewtam|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=ChrisKim|points=&lt;nowiki&gt;12&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely wiki notes for 2 classes; last minute wiki solutions for 4 HW assignments.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Cindy.pratt|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Cjcowx|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Com138|points=&lt;nowiki&gt;25&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely scanned notes for about 10 classes and one tutorial, 4 more at last minute.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Ellenho|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Feghali|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=GUO|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Guanyi.lin|points=&lt;nowiki&gt;2&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Last minute scanned solutions of one HW assignment; one last minute figure; several other contributions deleted as unreadable or unlinked.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Guosi2|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Haikunqiu1017|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Jack.rimmer|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Jhuang|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=JonathanYip|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Joyceng|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Jpark1230|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Judy|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Jungsung|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Justin0311|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Kostar6|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=LizElle|points=&lt;nowiki&gt;5&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely scanned notes for one class.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Lolo|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Lxuechen|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Manyuet|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Mi.liu|points=&lt;nowiki&gt;8&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely but barely readable notes for 2 classes.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Minheather|points=&lt;nowiki&gt;24&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely low-contrast scanned class notes for Oct 6, Oct 8, Oct 29, Nov 12, Dec 1, Dec 3, Dec 8.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Octopusheng|points=&lt;nowiki&gt;3&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Last minute scanned solutions for 5 assignments.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Orange|points=&lt;nowiki&gt;4&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely low-contrast scanned tutorial notes for Oct 1.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Rhoda.lam|points=&lt;nowiki&gt;4&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely photographed class notes for Nov 3.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Roroyap|points=&lt;nowiki&gt;18&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Timely mixed-quality scanned class notes for Oct 1, Oct 22, Nov 6, and two tutorials.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Sddlyze|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Semovski|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Shona.luke|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Tonglin|points=&lt;nowiki&gt;15&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;Typed up &quot;Solution For Circle Coloring Problem&quot; and &quot;Plane Division&quot;, three wiki links to external references, wiki discussion of HW7, etc.&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Viviies|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Xingyu.Zhou|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Xinran.xiang|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Z.fang|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> {{15-344/Good Deeds|uid=Zhaoyume|points=&lt;nowiki&gt;-&lt;/nowiki&gt;|deeds=&lt;nowiki&gt;-&lt;/nowiki&gt;}}<br /> |}</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15202 2015-12-16T14:52:04Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> <br /> '''(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.<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]<br /> <br /> <br /> '''Homework Problems Revisited: Explore the Textbook'''<br /> <br /> (Originally posted in the homework sectors after the corresponding homework was assigned, but moved to here for the readers' convenience.)<br /> <br /> <br /> '''(2).''' For Problem 10, Section 2.3, you may wonder how to untangle the knot without induction. Here is a possible way.<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]<br /> <br /> <br /> '''(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.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]<br /> <br /> <br /> '''(4).'''In problem 29, Section 5.3, we were asked to prove that <br /> <br /> &lt;math&gt;\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}&lt;/math&gt;, where &lt;math&gt;k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}&lt;/math&gt;.<br /> <br /> It is tempting to think that this is a special case of some identity and that a general pattern can be found.<br /> <br /> Replacing &lt;math&gt;3&lt;/math&gt; with any &lt;math&gt;m \in \mathbb{Z}_{&gt;0}&lt;/math&gt; and &lt;math&gt;10&lt;/math&gt; with any &lt;math&gt;n \in \mathbb{Z}_{\geq0}&lt;/math&gt; gives<br /> <br /> &lt;math&gt;\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n&lt;/math&gt;<br /> <br /> Does it hold, or can it be generalized to a greater extent?<br /> <br /> Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].<br /> <br /> &lt;math&gt;(\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}}&lt;/math&gt;, where &lt;math&gt;m \in \mathbb{Z}_{&gt;0}, n \in \mathbb{Z}_{\geq0}&lt;/math&gt; and &lt;math&gt;x_1, \ldots, x_m\in \mathbb{R}&lt;/math&gt;.<br /> <br /> For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].<br /> <br /> <br /> '''(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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem (Tong Lin)]]</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15185 2015-12-16T03:14:16Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> <br /> '''(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.<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]<br /> <br /> <br /> '''Explore the Textbook'''<br /> <br /> (Originally posted in the homework sectors after the corresponding homework was assigned, but moved to here for the readers' convenience.)<br /> <br /> <br /> '''(2).''' For Problem 10, Section 2.3, you may wonder how to untangle the knot without induction. Here is a possible way.<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]<br /> <br /> <br /> '''(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.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]<br /> <br /> <br /> '''(4).'''In problem 29, Section 5.3, we were asked to prove that <br /> <br /> &lt;math&gt;\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}&lt;/math&gt;, where &lt;math&gt;k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}&lt;/math&gt;.<br /> <br /> It is tempting to think that this is a special case of some identity and that a general pattern can be found.<br /> <br /> Replacing &lt;math&gt;3&lt;/math&gt; with any &lt;math&gt;m \in \mathbb{Z}_{&gt;0}&lt;/math&gt; and &lt;math&gt;10&lt;/math&gt; with any &lt;math&gt;n \in \mathbb{Z}_{\geq0}&lt;/math&gt; gives<br /> <br /> &lt;math&gt;\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n&lt;/math&gt;<br /> <br /> Does it hold, or can it be generalized to a greater extent?<br /> <br /> Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].<br /> <br /> &lt;math&gt;(\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}}&lt;/math&gt;, where &lt;math&gt;m \in \mathbb{Z}_{&gt;0}, n \in \mathbb{Z}_{\geq0}&lt;/math&gt; and &lt;math&gt;x_1, \ldots, x_m\in \mathbb{R}&lt;/math&gt;.<br /> <br /> For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].<br /> <br /> <br /> '''(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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem (Tong Lin)]]</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15165 2015-12-16T00:58:13Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> <br /> '''(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.<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]<br /> <br /> <br /> '''Explore the Textbook'''<br /> <br /> (Originally posted in the homework sectors after the corresponding homework was assigned, but moved to here for the readers' convenience.)<br /> <br /> <br /> '''(2).''' For Problem 10, Section 2.3, you may wonder how to untangle the knot without induction. Here is a possible way.<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]<br /> <br /> <br /> '''(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.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]<br /> <br /> <br /> '''(4).'''In problem 29, Section 5.3, we were asked to prove that <br /> <br /> &lt;math&gt;\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}&lt;/math&gt;, where &lt;math&gt;k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}&lt;/math&gt;.<br /> <br /> It is tempting to think that this is a special case of some identity and that a general pattern can be found.<br /> <br /> Replacing &lt;math&gt;3&lt;/math&gt; with any &lt;math&gt;m \in \mathbb{Z}_{&gt;0}&lt;/math&gt; and &lt;math&gt;10&lt;/math&gt; with any &lt;math&gt;n \in \mathbb{Z}_{\geq0}&lt;/math&gt; gives<br /> <br /> &lt;math&gt;\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n&lt;/math&gt;<br /> <br /> Does it hold, or can it be generalized to a greater extent?<br /> <br /> Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].<br /> <br /> &lt;math&gt;(\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}}&lt;/math&gt;, where &lt;math&gt;m \in \mathbb{Z}_{&gt;0}, n \in \mathbb{Z}_{\geq0}&lt;/math&gt; and &lt;math&gt;x_1, \ldots, x_m\in \mathbb{R}&lt;/math&gt;.<br /> <br /> For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].<br /> <br /> <br /> '''(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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15164 2015-12-16T00:55:42Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> <br /> '''(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.<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]<br /> <br /> <br /> '''Explore the Textbook'''<br /> <br /> (Originally posted in the homework sectors, but moved to here for the readers' convenience)<br /> <br /> <br /> '''(2).''' For Problem 10, Section 2.3, you may wonder how to untangle the knot without induction. Here is a possible way.<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]<br /> <br /> <br /> '''(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.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]<br /> <br /> <br /> '''(4).'''In problem 29, Section 5.3, we were asked to prove that <br /> <br /> &lt;math&gt;\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}&lt;/math&gt;, where &lt;math&gt;k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}&lt;/math&gt;.<br /> <br /> It is tempting to think that this is a special case of some identity and that a general pattern can be found.<br /> <br /> Replacing &lt;math&gt;3&lt;/math&gt; with any &lt;math&gt;m \in \mathbb{Z}_{&gt;0}&lt;/math&gt; and &lt;math&gt;10&lt;/math&gt; with any &lt;math&gt;n \in \mathbb{Z}_{\geq0}&lt;/math&gt; gives<br /> <br /> &lt;math&gt;\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n&lt;/math&gt;<br /> <br /> Does it hold, or can it be generalized to a greater extent?<br /> <br /> Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].<br /> <br /> &lt;math&gt;(\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}}&lt;/math&gt;, where &lt;math&gt;m \in \mathbb{Z}_{&gt;0}, n \in \mathbb{Z}_{\geq0}&lt;/math&gt; and &lt;math&gt;x_1, \ldots, x_m\in \mathbb{R}&lt;/math&gt;.<br /> <br /> For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].<br /> <br /> <br /> '''(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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15161 2015-12-16T00:48:52Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> <br /> '''(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.<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]<br /> <br /> <br /> '''Explore the Textbook'''<br /> <br /> <br /> '''(2).''' For Problem 10, Section 2.3, you may wonder how to untangle the knot without induction. Here is a possible way.<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]<br /> <br /> <br /> '''(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.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]<br /> <br /> <br /> '''(4).'''In problem 29, Section 5.3, we were asked to prove that <br /> <br /> &lt;math&gt;\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}&lt;/math&gt;, where &lt;math&gt;k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}&lt;/math&gt;.<br /> <br /> It is tempting to think that this is a special case of some identity and that a general pattern can be found.<br /> <br /> Replacing &lt;math&gt;3&lt;/math&gt; with any &lt;math&gt;m \in \mathbb{Z}_{&gt;0}&lt;/math&gt; and &lt;math&gt;10&lt;/math&gt; with any &lt;math&gt;n \in \mathbb{Z}_{\geq0}&lt;/math&gt; gives<br /> <br /> &lt;math&gt;\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n&lt;/math&gt;<br /> <br /> Does it hold, or can it be generalized to a greater extent?<br /> <br /> Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].<br /> <br /> &lt;math&gt;(\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}}&lt;/math&gt;, where &lt;math&gt;m \in \mathbb{Z}_{&gt;0}, n \in \mathbb{Z}_{\geq0}&lt;/math&gt; and &lt;math&gt;x_1, \ldots, x_m\in \mathbb{R}&lt;/math&gt;.<br /> <br /> For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].<br /> <br /> <br /> '''(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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15160 2015-12-16T00:46:48Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> <br /> '''(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.<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]<br /> <br /> <br /> '''Explore the Textbook'''<br /> <br /> <br /> '''(2).''' For Problem 10, Section 2.3, you may wonder how to untangle the knot without induction. Here is a possible way.<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]<br /> <br /> <br /> '''(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.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]<br /> <br /> <br /> '''(4).'''In problem 29, Section 5.3, we were asked to prove that <br /> <br /> &lt;math&gt;\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}&lt;/math&gt;, where &lt;math&gt;k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}&lt;/math&gt;.<br /> <br /> It is tempting to think that this is a special case of some identity and that a general pattern can be found.<br /> <br /> Replacing &lt;math&gt;3&lt;/math&gt; with any &lt;math&gt;m \in \mathbb{Z}_{&gt;0}&lt;/math&gt; and &lt;math&gt;10&lt;/math&gt; with any &lt;math&gt;n \in \mathbb{Z}_{\geq0}&lt;/math&gt; gives<br /> <br /> &lt;math&gt;\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n&lt;/math&gt;<br /> <br /> Does it hold, or can it be generalized to a greater extent?<br /> <br /> Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].<br /> <br /> &lt;math&gt;(\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}}&lt;/math&gt;, where &lt;math&gt;m \in \mathbb{Z}_{&gt;0}, n \in \mathbb{Z}_{\geq0}&lt;/math&gt; and &lt;math&gt;x_1, \ldots, x_m\in \mathbb{R}&lt;/math&gt;.<br /> <br /> For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].<br /> <br /> <br /> '''(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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15159 2015-12-16T00:42:51Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_6&diff=15158 2015-12-16T00:39:39Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday November 12&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 4, 8, &lt;u&gt;18&lt;/u&gt;, &lt;u&gt;39&lt;/u&gt;, &lt;u&gt;46&lt;/u&gt;, and 49 in section 5.1, problems 4, 9, 16, 23, &lt;u&gt;31&lt;/u&gt;, 38, &lt;u&gt;56&lt;/u&gt;, 68, &lt;u&gt;72&lt;/u&gt;, and &lt;u&gt;85&lt;/u&gt; in section 5.2, and problems &lt;u&gt;5&lt;/u&gt;, and 29 in section 5.3, but submit only your solutions of the underlined problems.<br /> <br /> Sorry for again posting an assignment a bit late.<br /> <br /> ----<br /> <br /> An unrelated matter - I was asked to distribute the following, and I hereby comply:<br /> <br /> Subject: COMC Markers Needed<br /> <br /> We need people to help us mark the 2015 Canadian Open Mathematics Contest. Anyone can help mark (including non-math students so please feel free to pass this message onto your friends and invite them to help too).<br /> <br /> We are having a marking party on November 21 and 22 complete with pizza, pop and other snacks. However we need markers to help the week before and after this as well. Anyone who assists will gain hours towards CCR recognition and certificates are provided to those that wish them.<br /> <br /> If you are able to help please send an email to outreach@math.toronto.edu with &quot;COMC Marker&quot; as the subject and we'll add your name to the list. We're also happy to answer any questions you may have.<br /> <br /> Sincerely,<br /> <br /> Pamela Brittain<br /> &lt;br/&gt;Outreach and Special Projects Officer<br /> &lt;br/&gt;Department of Mathematics<br /> &lt;br/&gt;University of Toronto<br /> <br /> {{15-344:Dror/Students Divider}}</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_7&diff=15157 2015-12-16T00:39:30Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday November 19&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 8, 10, &lt;u&gt;15&lt;/u&gt;, 20, &lt;u&gt;24&lt;/u&gt;, &lt;u&gt;28&lt;/u&gt;, and &lt;u&gt;29&lt;/u&gt; in section 5.3 and problems 1, &lt;u&gt;3&lt;/u&gt;, 16, &lt;u&gt;39&lt;/u&gt;, 40, &lt;u&gt;63&lt;/u&gt;, and &lt;u&gt;65&lt;/u&gt; in section 5.4, but submit only your solutions of the underlined problems.<br /> <br /> {{15-344:Dror/Students Divider}}</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15155 2015-12-16T00:35:13Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> '''(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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]<br /> <br /> '''(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.<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_9&diff=15153 2015-12-16T00:30:31Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday December 3&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 2abde, &lt;u&gt;2c&lt;/u&gt;, 4abc, &lt;u&gt;4d&lt;/u&gt;, 12, &lt;u&gt;16&lt;/u&gt;, 20, and 25 in section 6.1 and problems 1, &lt;u&gt;2&lt;/u&gt;, 11abcd, &lt;u&gt;11e&lt;/u&gt;, 30, &lt;u&gt;32&lt;/u&gt;, and &lt;u&gt;43&lt;/u&gt; in section 6.2, but submit only your solutions of the underlined problems.<br /> <br /> '''In addition,''' solve the following problem. There is no need to submit your solution.<br /> <br /> '''Part 1.''' For &lt;math&gt;n\geq 0&lt;/math&gt;, let &lt;math&gt;C_n&lt;/math&gt; be the &lt;math&gt;n&lt;/math&gt;'th Catalan number, defined as the number of words made of &lt;math&gt;n&lt;/math&gt; &lt;math&gt;a&lt;/math&gt;'s and &lt;math&gt;n&lt;/math&gt; &lt;math&gt;b&lt;/math&gt;'s in which in every initial segment there are at least as many &lt;math&gt;a&lt;/math&gt;'s as &lt;math&gt;b&lt;/math&gt;'s. Prove that for &lt;math&gt;n\geq 1&lt;/math&gt;, &lt;math&gt;C_n=C_0C_{n-1}+C_1C_{n-2}+C_2C_{n-3}+\ldots+C_{n-1}C_0&lt;/math&gt;.<br /> <br /> ''Hint.'' If &lt;math&gt;w&lt;/math&gt; is such a word, let &lt;math&gt;k\geq 1&lt;/math&gt; be the smallest such that if you cut &lt;math&gt;w&lt;/math&gt; after &lt;math&gt;2k&lt;/math&gt; letters, then the number of &lt;math&gt;a&lt;/math&gt;'s before the cut is equal to the number of &lt;math&gt;b&lt;/math&gt;'s before the cut. What can you say about the part of &lt;math&gt;w&lt;/math&gt; before the cut, and the part of &lt;math&gt;w&lt;/math&gt; after the cut?<br /> <br /> '''Part 2.''' For &lt;math&gt;n\geq 1&lt;/math&gt;, let &lt;math&gt;D_n&lt;/math&gt; be the number of different ways of computing the product &lt;math&gt;A_1A_2\cdots A_n&lt;/math&gt; of &lt;math&gt;n&lt;/math&gt; matrices. Prove that for &lt;math&gt;n\geq 2&lt;/math&gt;, &lt;math&gt;D_n=D_1D_{n-1}+D_2D_{n-2}+D_3D_{n-3}+\ldots+D_{n-1}D_1&lt;/math&gt;.<br /> <br /> ''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of &lt;math&gt;k&lt;/math&gt; of the matrices with the product of &lt;math&gt;n-k&lt;/math&gt; of the matrices.<br /> <br /> '''Part 3.''' Let &lt;math&gt;E_2=1&lt;/math&gt; and for &lt;math&gt;n\geq 3&lt;/math&gt; let &lt;math&gt;E_n&lt;/math&gt; be the number of triangulations of a convex &lt;math&gt;n&lt;/math&gt;-gon using non-crossing diagonals. Prove that for &lt;math&gt;n\geq 3&lt;/math&gt;, &lt;math&gt;E_n=E_2E_{n-1}+E_3E_{n-2}+E_4E_{n-3}+\ldots+E_{n-1}E_2&lt;/math&gt;.<br /> <br /> ''Hint.'' Choose one edge of the &lt;math&gt;n&lt;/math&gt;-gon, and consider the triangle on top of it, what's to its left, and what's to its right.<br /> <br /> '''Part 4.''' Use the above three assertions to prove that for any &lt;math&gt;n\geq 0&lt;/math&gt;, &lt;math&gt;C_n=D_{n+1}=E_{n+2}&lt;/math&gt;.<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> Homework Assignment 9 Solution<br /> <br /> '''2)''' Build a generating function for &lt;math&gt;a_{r}&lt;/math&gt;, the number of integer solutions to the following equations.<br /> <br /> c) &lt;math&gt;e_{1}+e_{2}+e_{3}+e_{4} = r, 2\leq e_{i} \leq 7, e_{1}&lt;/math&gt; even &lt;math&gt; e_{2} &lt;/math&gt; odd.<br /> <br /> '''A)''' For &lt;math&gt;e_{3}&lt;/math&gt; and &lt;math&gt;e_{4}&lt;/math&gt; together, we have &lt;math&gt;g_{1}(x) = (x^2+x^3+x^4+x^5+x^6+x^7)^2 &lt;/math&gt;<br /> <br /> For &lt;math&gt;e_{1}&lt;/math&gt;, we have &lt;math&gt;g_{2}(x) = (x^2+x^4+x^6) &lt;/math&gt;<br /> <br /> For &lt;math&gt;e_{2}&lt;/math&gt;, we have &lt;math&gt;g_{3}(x) = (x^3+x^5+x^7) &lt;/math&gt;<br /> <br /> In total, we have &lt;math&gt;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 &lt;/math&gt;</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15152 2015-12-16T00:28:51Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> 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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]</div>

Tonglin https://drorbn.net/index.php?title=15-344&diff=15151 2015-12-16T00:26:31Z

<p>Tonglin: </p> <hr /> <div>__NOEDITSECTION__<br /> __NOTOC__<br /> {{15-344/Navigation}}<br /> ==Introduction to Combinatorics==<br /> ===Department of Mathematics, University of Toronto, Fall 2015===<br /> <br /> {{15-344/Crucial Information}}<br /> <br /> ===Text===<br /> Our main text book will be ''Applied Combinatorics'' (sixth edition) by Alan Tucker, ISBN 978-0-470-45838-9; it is a required reading.<br /> <br /> ===Further Resources===<br /> <br /> * [http://www.math.toronto.edu/cms/undergraduate-program/ Undergraduate Information] at the [http://www.math.toronto.edu/ UofT Math Department]<br /> <br /> * [http://www.artsandscience.utoronto.ca/ofr/calendar/crs_mat.htm Undergraduate Course Descriptions].<br /> <br /> * [http://www.math.toronto.edu/courses/344.old/ 1999 class], by Steve Tanny.<br /> <br /> * [http://www.math.toronto.edu/courses/344/ 2002 class], by Andres Del Junco.<br /> <br /> * [http://www.math.toronto.edu/raghavan/344/ 2008 class], by Dilip Raghavan.<br /> <br /> * My {{Pensieve Link|Classes/15-344-Combinatorics/|15-344 notebook}}.<br /> <br /> * [http://drorbn.net/bbs/show?prefix=15-344 Some blackboard shots].<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> 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). <br /> <br /> [[Media:15-344-Plane Division.pdf | Graph Theory Revisited: Euler's Formula and a Combinatorial Problem]]</div>

Tonglin https://drorbn.net/index.php?title=File:15-344-Plane_Division.pdf&diff=15150 2015-12-16T00:24:36Z

<p>Tonglin: </p> <hr /> <div></div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_9&diff=15121 2015-12-05T17:49:47Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday December 3&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 2abde, &lt;u&gt;2c&lt;/u&gt;, 4abc, &lt;u&gt;4d&lt;/u&gt;, 12, &lt;u&gt;16&lt;/u&gt;, 20, and 25 in section 6.1 and problems 1, &lt;u&gt;2&lt;/u&gt;, 11abcd, &lt;u&gt;11e&lt;/u&gt;, 30, &lt;u&gt;32&lt;/u&gt;, and &lt;u&gt;43&lt;/u&gt; in section 6.2, but submit only your solutions of the underlined problems.<br /> <br /> '''In addition,''' solve the following problem. There is no need to submit your solution.<br /> <br /> '''Part 1.''' For &lt;math&gt;n\geq 0&lt;/math&gt;, let &lt;math&gt;C_n&lt;/math&gt; be the &lt;math&gt;n&lt;/math&gt;'th Catalan number, defined as the number of words made of &lt;math&gt;n&lt;/math&gt; &lt;math&gt;a&lt;/math&gt;'s and &lt;math&gt;n&lt;/math&gt; &lt;math&gt;b&lt;/math&gt;'s in which in every initial segment there are at least as many &lt;math&gt;a&lt;/math&gt;'s as &lt;math&gt;b&lt;/math&gt;'s. Prove that for &lt;math&gt;n\geq 1&lt;/math&gt;, &lt;math&gt;C_n=C_0C_{n-1}+C_1C_{n-2}+C_2C_{n-3}+\ldots+C_{n-1}C_0&lt;/math&gt;.<br /> <br /> ''Hint.'' If &lt;math&gt;w&lt;/math&gt; is such a word, let &lt;math&gt;k\geq 1&lt;/math&gt; be the smallest such that if you cut &lt;math&gt;w&lt;/math&gt; after &lt;math&gt;2k&lt;/math&gt; letters, then the number of &lt;math&gt;a&lt;/math&gt;'s before the cut is equal to the number of &lt;math&gt;b&lt;/math&gt;'s before the cut. What can you say about the part of &lt;math&gt;w&lt;/math&gt; before the cut, and the part of &lt;math&gt;w&lt;/math&gt; after the cut?<br /> <br /> '''Part 2.''' For &lt;math&gt;n\geq 1&lt;/math&gt;, let &lt;math&gt;D_n&lt;/math&gt; be the number of different ways of computing the product &lt;math&gt;A_1A_2\cdots A_n&lt;/math&gt; of &lt;math&gt;n&lt;/math&gt; matrices. Prove that for &lt;math&gt;n\geq 2&lt;/math&gt;, &lt;math&gt;D_n=D_1D_{n-1}+D_2D_{n-2}+D_3D_{n-3}+\ldots+D_{n-1}D_1&lt;/math&gt;.<br /> <br /> ''Hint.'' In the last matrix multiplication to be carried out, you'd be multiplying the product of &lt;math&gt;k&lt;/math&gt; of the matrices with the product of &lt;math&gt;n-k&lt;/math&gt; of the matrices.<br /> <br /> '''Part 3.''' Let &lt;math&gt;E_2=1&lt;/math&gt; and for &lt;math&gt;n\geq 3&lt;/math&gt; let &lt;math&gt;E_n&lt;/math&gt; be the number of triangulations of a convex &lt;math&gt;n&lt;/math&gt;-gon using non-crossing diagonals. Prove that for &lt;math&gt;n\geq 3&lt;/math&gt;, &lt;math&gt;E_n=E_2E_{n-1}+E_3E_{n-2}+E_4E_{n-3}+\ldots+E_{n-1}E_2&lt;/math&gt;.<br /> <br /> ''Hint.'' Choose one edge of the &lt;math&gt;n&lt;/math&gt;-gon, and consider the triangle on top of it, what's to its left, and what's to its right.<br /> <br /> '''Part 4.''' Use the above three assertions to prove that for any &lt;math&gt;n\geq 0&lt;/math&gt;, &lt;math&gt;C_n=D_{n+1}=E_{n+2}&lt;/math&gt;.<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> Catalan Number Revisited: Power Series, Combinatorial Information and Ordinary Differential Equations<br /> <br /> [http://drorbn.net/dbnvp/12-267-121106.php A Lecture From MAT267 (Also Taught by Professor Bar-Natan)]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15091 2015-11-20T18:12:06Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15090 2015-11-20T18:11:17Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution for Circle Coloring Problem.pdf|Solution to Circle Coloring Problem (Tong Lin)]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15089 2015-11-20T18:10:54Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution to Circle Coloring Problem.pdf|Solution For Circle Coloring Problem (Tong Lin)]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_7&diff=15088 2015-11-20T18:07:49Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday November 19&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 8, 10, &lt;u&gt;15&lt;/u&gt;, 20, &lt;u&gt;24&lt;/u&gt;, &lt;u&gt;28&lt;/u&gt;, and &lt;u&gt;29&lt;/u&gt; in section 5.3 and problems 1, &lt;u&gt;3&lt;/u&gt;, 16, &lt;u&gt;39&lt;/u&gt;, 40, &lt;u&gt;63&lt;/u&gt;, and &lt;u&gt;65&lt;/u&gt; in section 5.4, but submit only your solutions of the underlined problems.<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> In problem 29, Section 5.3, we were asked to prove that <br /> <br /> &lt;math&gt;\sum_{k_1 + k_2 + k_3 = 10} P(10, k_1, k_2, k_3) = 3^{10}&lt;/math&gt;, where &lt;math&gt;k_1, k_2, k_3 \in \mathbb{Z}_{\geq 0}&lt;/math&gt;.<br /> <br /> It is tempting to think that this is a special case of some identity and that a general pattern can be found.<br /> <br /> Replacing &lt;math&gt;3&lt;/math&gt; with any &lt;math&gt;m \in \mathbb{Z}_{&gt;0}&lt;/math&gt; and &lt;math&gt;10&lt;/math&gt; with any &lt;math&gt;n \in \mathbb{Z}_{\geq0}&lt;/math&gt; gives<br /> <br /> &lt;math&gt;\sum_{k_1+k_2+\cdots+k_m=n} P(n, k_1, k_2, \ldots, k_m) = m^n&lt;/math&gt;<br /> <br /> Does it hold, or can it be generalized to a greater extent?<br /> <br /> Yes. We have the [https://en.wikipedia.org/wiki/Multinomial_theorem Multinomial_theorem].<br /> <br /> &lt;math&gt;(\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}}&lt;/math&gt;, where &lt;math&gt;m \in \mathbb{Z}_{&gt;0}, n \in \mathbb{Z}_{\geq0}&lt;/math&gt; and &lt;math&gt;x_1, \ldots, x_m\in \mathbb{R}&lt;/math&gt;.<br /> <br /> For a proof by induction, see [https://proofwiki.org/wiki/Multinomial_Theorem here].</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_6&diff=15046 2015-11-13T04:25:22Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday November 12&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 4, 8, &lt;u&gt;18&lt;/u&gt;, &lt;u&gt;39&lt;/u&gt;, &lt;u&gt;46&lt;/u&gt;, and 49 in section 5.1, problems 4, 9, 16, 23, &lt;u&gt;31&lt;/u&gt;, 38, &lt;u&gt;56&lt;/u&gt;, 68, &lt;u&gt;72&lt;/u&gt;, and &lt;u&gt;85&lt;/u&gt; in section 5.2, and problems &lt;u&gt;5&lt;/u&gt;, and 29 in section 5.3, but submit only your solutions of the underlined problems.<br /> <br /> Sorry for again posting an assignment a bit late.<br /> <br /> ----<br /> <br /> An unrelated matter - I was asked to distribute the following, and I hereby comply:<br /> <br /> Subject: COMC Markers Needed<br /> <br /> We need people to help us mark the 2015 Canadian Open Mathematics Contest. Anyone can help mark (including non-math students so please feel free to pass this message onto your friends and invite them to help too).<br /> <br /> We are having a marking party on November 21 and 22 complete with pizza, pop and other snacks. However we need markers to help the week before and after this as well. Anyone who assists will gain hours towards CCR recognition and certificates are provided to those that wish them.<br /> <br /> If you are able to help please send an email to outreach@math.toronto.edu with &quot;COMC Marker&quot; as the subject and we'll add your name to the list. We're also happy to answer any questions you may have.<br /> <br /> Sincerely,<br /> <br /> Pamela Brittain<br /> &lt;br/&gt;Outreach and Special Projects Officer<br /> &lt;br/&gt;Department of Mathematics<br /> &lt;br/&gt;University of Toronto<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> 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.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_6&diff=15045 2015-11-13T01:09:32Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday November 12&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 4, 8, &lt;u&gt;18&lt;/u&gt;, &lt;u&gt;39&lt;/u&gt;, &lt;u&gt;46&lt;/u&gt;, and 49 in section 5.1, problems 4, 9, 16, 23, &lt;u&gt;31&lt;/u&gt;, 38, &lt;u&gt;56&lt;/u&gt;, 68, &lt;u&gt;72&lt;/u&gt;, and &lt;u&gt;85&lt;/u&gt; in section 5.2, and problems &lt;u&gt;5&lt;/u&gt;, and 29 in section 5.3, but submit only your solutions of the underlined problems.<br /> <br /> Sorry for again posting an assignment a bit late.<br /> <br /> ----<br /> <br /> An unrelated matter - I was asked to distribute the following, and I hereby comply:<br /> <br /> Subject: COMC Markers Needed<br /> <br /> We need people to help us mark the 2015 Canadian Open Mathematics Contest. Anyone can help mark (including non-math students so please feel free to pass this message onto your friends and invite them to help too).<br /> <br /> We are having a marking party on November 21 and 22 complete with pizza, pop and other snacks. However we need markers to help the week before and after this as well. Anyone who assists will gain hours towards CCR recognition and certificates are provided to those that wish them.<br /> <br /> If you are able to help please send an email to outreach@math.toronto.edu with &quot;COMC Marker&quot; as the subject and we'll add your name to the list. We're also happy to answer any questions you may have.<br /> <br /> Sincerely,<br /> <br /> Pamela Brittain<br /> &lt;br/&gt;Outreach and Special Projects Officer<br /> &lt;br/&gt;Department of Mathematics<br /> &lt;br/&gt;University of Toronto<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> 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 articles that presented some general results.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_6&diff=15044 2015-11-13T01:08:44Z

<p>Tonglin: </p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday November 12&lt;/span&gt;. 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.<br /> <br /> '''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.<br /> <br /> '''Solve''' problems 4, 8, &lt;u&gt;18&lt;/u&gt;, &lt;u&gt;39&lt;/u&gt;, &lt;u&gt;46&lt;/u&gt;, and 49 in section 5.1, problems 4, 9, 16, 23, &lt;u&gt;31&lt;/u&gt;, 38, &lt;u&gt;56&lt;/u&gt;, 68, &lt;u&gt;72&lt;/u&gt;, and &lt;u&gt;85&lt;/u&gt; in section 5.2, and problems &lt;u&gt;5&lt;/u&gt;, and 29 in section 5.3, but submit only your solutions of the underlined problems.<br /> <br /> Sorry for again posting an assignment a bit late.<br /> <br /> ----<br /> <br /> An unrelated matter - I was asked to distribute the following, and I hereby comply:<br /> <br /> Subject: COMC Markers Needed<br /> <br /> We need people to help us mark the 2015 Canadian Open Mathematics Contest. Anyone can help mark (including non-math students so please feel free to pass this message onto your friends and invite them to help too).<br /> <br /> We are having a marking party on November 21 and 22 complete with pizza, pop and other snacks. However we need markers to help the week before and after this as well. Anyone who assists will gain hours towards CCR recognition and certificates are provided to those that wish them.<br /> <br /> If you are able to help please send an email to outreach@math.toronto.edu with &quot;COMC Marker&quot; as the subject and we'll add your name to the list. We're also happy to answer any questions you may have.<br /> <br /> Sincerely,<br /> <br /> Pamela Brittain<br /> &lt;br/&gt;Outreach and Special Projects Officer<br /> &lt;br/&gt;Department of Mathematics<br /> &lt;br/&gt;University of Toronto<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> 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 if no such constraint? Attached are two articles that presented some general results.<br /> <br /> [https://cs.uwaterloo.ca/journals/JIS/sommars/newtriangle.html 15-344/The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon]<br /> <br /> [http://www-math.mit.edu/~poonen/papers/ngon.pdf 15-344/The Number of Intersection Points Made by the Diagonals of a Regular Polygon]</div>

Tonglin https://drorbn.net/index.php?title=File:15-344-Solution_For_Circle_Coloring_Problem.pdf&diff=15029 2015-11-08T15:54:50Z

<p>Tonglin: Tonglin uploaded a new version of &amp;quot;File:15-344-Solution For Circle Coloring Problem.pdf&amp;quot;</p> <hr /> <div></div>

Tonglin https://drorbn.net/index.php?title=File:15-344-Solution_For_Circle_Coloring_Problem.pdf&diff=15028 2015-11-08T15:44:12Z

<p>Tonglin: Tonglin uploaded a new version of &amp;quot;File:15-344-Solution For Circle Coloring Problem.pdf&amp;quot;</p> <hr /> <div></div>

Tonglin https://drorbn.net/index.php?title=File:15-344-Solution_For_Circle_Coloring_Problem.pdf&diff=15027 2015-11-08T03:34:13Z

<p>Tonglin: Tonglin uploaded a new version of &amp;quot;File:15-344-Solution For Circle Coloring Problem.pdf&amp;quot;</p> <hr /> <div></div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15026 2015-11-08T03:29:25Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution For Circle Coloring Problem (Tong Lin)]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15025 2015-11-08T03:20:47Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|Solution For Circle Coloring Problem (Tong Lin).pdf]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15024 2015-11-08T03:17:54Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|15-344-Solution For Circle Coloring Problem (Tong Lin).pdf]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15023 2015-11-08T03:15:48Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf|15-344-Solution For Circle Coloring Problem.pdf]]</div>

Tonglin https://drorbn.net/index.php?title=15-344/Homework_Assignment_3&diff=15022 2015-11-08T03:14:05Z

<p>Tonglin: /* Comments by Gaurav Patil on Problem 10 of Section 2.3 */</p> <hr /> <div>{{15-344/Navigation}}<br /> This assignment is due &lt;span style=&quot;color: blue;&quot;&gt;at the tutorials on Thursday October 15&lt;/span&gt;. 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.<br /> <br /> '''Add''' your name to the [[15-344/Class Photo|Class Photo]] page! (This of course is not mandatory, but it is fun).<br /> <br /> '''Reread''' sections 2.2-2.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''' chapter 3, just to get a feel for the future.<br /> <br /> '''Solve''' problems &lt;u&gt;1&lt;/u&gt;, 9, 19, 20, &lt;u&gt;21&lt;/u&gt;, and 22 in section 2.2, problems 1abcdfghijklnoqr, &lt;u&gt;1emp&lt;/u&gt;, &lt;u&gt;10&lt;/u&gt;, and 12 in section 2.3, and problems 1, 3, &lt;u&gt;5&lt;/u&gt;, and &lt;u&gt;9&lt;/u&gt; in section 2.4, but submit only your solutions of the underlined problems.<br /> <br /> ===Comments by Gaurav Patil on Problem 10 of Section 2.3===<br /> {{Pensieve link|Classes/15-344-Combinatorics/CircleColoringProblem@.pdf|CircleColoringProblem@.pdf}}<br /> <br /> {{15-344:Dror/Students Divider}}<br /> <br /> [[Media:15-344-Solution For Circle Coloring Problem.pdf]]</div>

Tonglin https://drorbn.net/index.php?title=File:15-344-Solution_For_Circle_Coloring_Problem.pdf&diff=15021 2015-11-08T02:58:28Z

<p>Tonglin: </p> <hr /> <div></div>

Tonglin https://drorbn.net/index.php?title=15-344/Class_Photo&diff=14841 2015-10-04T06:45:45Z

<p>Tonglin: /* Who We Are... */</p> <hr /> <div>Our class on October 1, 2015:<br /> <br /> [[Image:15-344-ClassPhoto.jpg|thumb|centre|800px|Class Photo: click to enlarge]]<br /> {{15-344/Navigation}}<br /> <br /> Please identify yourself in this photo! There are two ways to do that:<br /> <br /> * [[Special:Userlogin|Log in]] to this Wiki and edit this page. Put your name, userid, email address and location in the picture in the alphabetical list below.<br /> * Send [[User:Drorbn|Dror]] an email message with this information.<br /> <br /> The first option is more fun but less private.<br /> <br /> ===Who We Are...===<br /> <br /> {| align=center border=1 cellspacing=<br /> <br /> {{Photo Entry|last=Bar-Natan|first=Dror|userid=Drorbn|email=drorbn@ math. toronto. edu|location=facing everybody, as the photographer|comments=Take this entry as a model and leave it first. Otherwise alphabetize by last name. Feel free to leave some fields blank. For better line-breaking, leave a space next to the &quot;@&quot; in email addresses.}}<br /> <br /> &lt;!--PLEASE KEEP IN ALPHABETICAL ORDER, BY LAST NAME--&gt;<br /> {{Photo Entry|last=Lin|first=Tong|userid=TongLin|email=tong.lin@ mail. utoronto. ca|location= on the very left of the second row from the front, in a gray and black sweater|comments=}}<br /> <br /> {{Photo Entry|last=Rimmer|first=Jack|userid=Jack.rimmer|email=jack.rimmer@ mail. utoronto. ca|location= 2nd row from the front, one person from the left, grey t-shirt and glasses. Looks a bit sleepy.|comments=}}<br /> <br /> {{Photo Entry|last=Semovski|first=Julian|userid=Semovski|email=julian.semovski@ mail. utoronto. ca|location= 3rd row from the front, very left, blue and black stripe sweater. Struggling with life|comments=}}<br /> <br /> {{Photo Entry|last=Yoo|first=Seungmin|userid=minheather|email=seungmin.yoo@ mail. utoronto. ca|location= left side of a third row from the back. A girl with short hair|comments=}}<br /> <br /> {{Photo Entry|last=Zibert|first=Vincent|userid=orange|email=vincent.zibert@ mail. utoronto. ca|location= front row in the white shirt|comments=}}<br /> <br /> &lt;!--PLEASE KEEP IN ALPHABETICAL ORDER, BY LAST NAME--&gt;</div>

Tonglin