(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 54147, 2101]*) (*NotebookOutlinePosition[ 58020, 2243]*) (* CellTagsIndexPosition[ 57408, 2215]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] 2004 K. Sutner ", "MR"], Cell[CellGroupData[{ Cell["Binomial Coefficients", "Title", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:1"], Cell[CellGroupData[{ Cell["Some Definitions", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:2"], Cell[CellGroupData[{ Cell["The Original Definition", "Subsubsection", CellTags->"c:3"], Cell["\<\ Here is a problem first tackled by the eleventh century Persian \ astronomer Omar Khayyam:\ \>", "Text"], Cell[TextData[{ StyleBox["Problem:", FontWeight->"Bold"], " Expand ", Cell[BoxData[ \(TraditionalForm\`\((a + b)\)\^n\)]], "." }], "Text"], Cell["\<\ This sounds silly in modern mathematical language, but 900 years \ ago nothing was obvious.\ \>", "Text"], Cell["\<\ Expand[(a+b)^2] Expand[(a+b)^3] Expand[(a+b)^4] Expand[(a+b)^10]\ \>", "Input"], Cell["We would like a simple closed form for those coefficients.", "Text"], Cell[TextData[{ "A minor simplification: we get the same coefficicients if we replace ", Cell[BoxData[ \(TraditionalForm\`\(\(b\)\(\ \)\)\)]], "by ", Cell[BoxData[ \(TraditionalForm\`1\)]], ":" }], "Text"], Cell["Expand[(1+a)^10]", "Input"], Cell[TextData[{ StyleBox["Definition:", FontWeight->"Bold"], " \nThe coefficient of ", Cell[BoxData[ \(TraditionalForm\`x\^k\)]], " in the expansion of ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\((1 + x)\)\^n\)\)\)]], " is called the ", StyleBox["binomial coefficient", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\(n, k\)\)\)]], ". \n\n", StyleBox["It is denoted as ", "Text"], Cell[BoxData[ FormBox[ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], TraditionalForm]]], " or", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(C\_k\%n\)\)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`C(n, k)\)]], ". \nRead", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], " "}], TraditionalForm]]], "as \"n choose k\".\nThis makes sense a priori only for ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ k\ \[LessEqual] \ n\)]], ", but we can extend the definition to other values of ", Cell[BoxData[ \(TraditionalForm\`k\)]], " by assuming a value of 0 for the binomial coefficient. \n\nMathematica \ function: " }], "Text"], Cell["Binomial[ 10, 5 ]", "Input"], Cell["Binomial[ 10, Range[0,10] ]", "Input"], Cell["\<\ ListPlot[ Log@Binomial[ 20, Range[0,20] ], PlotStyle->{Blue, \ PointSize[0.02]}];\ \>", "Input"], Cell["\<\ Note how the coefficients first increase, and then decrease (a \ so-called unimodal sequence). \ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell["An Alternative Definition", "Subsubsection", CellTags->"c:4"], Cell[TextData[{ "Another popular definition for ", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], " "}], TraditionalForm]]], " is the number of ", Cell[BoxData[ \(TraditionalForm\`k\)]], "-element subsets of an ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-element set. \n" }], "Text"], Cell[TextData[{ "This makes sense a priori only for ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ k\ \[LessEqual] \ n\)]], ", but we can extend the definition to other values of ", Cell[BoxData[ \(TraditionalForm\`k\)]], " by assuming a value of 0 for the binomial coefficient. \n\nNeedless to \ say, we will have to check that the number of ", Cell[BoxData[ \(TraditionalForm\`k\)]], "-element subsets of an ", Cell[BoxData[ \(TraditionalForm\`n\)]], "-element set is indeed the same as the exponent of ", Cell[BoxData[ \(TraditionalForm\`x\^\(\(\ \)\(k\)\)\)]], " in the expansion of ", Cell[BoxData[ \(TraditionalForm\`\((x\ + \ 1)\)\^\(\(\ \)\(n\)\)\)]], ". " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Factorials and Binomial Coefficients", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:5"], Cell[TextData[{ "Here is another way of computing binomial coefficients. This is one is \ based on cosidering a slightly more complicated situation. The terms ", Cell[BoxData[ \(\(a\^i\) b\^\(n - i\)\)]], " in the expansion of ", Cell[BoxData[ \(\((a + b)\)\^n\)]], " are obtained by rearranging products of the form, say, ", Cell[BoxData[ \(a\[CenterDot]a\[CenterDot]a\[CenterDot]b\[CenterDot]a\[CenterDot] a\[CenterDot]b\[CenterDot]b\[CenterDot]a\[CenterDot]b == \(a\^6\) b\^4\)]], ". The term ", Cell[BoxData[ \(\(a\^6\) b\^4\)]], " appears in the expansion of ", Cell[BoxData[ \(\((a + b)\)\^10\)]], ". You can think of the sequence ", Cell[BoxData[ \(a\ a\ a\ b\ a\ a\ b\ b\ a\ b\)]], " as a ", StyleBox["choice sequence", FontWeight->"Bold"], ", selecting an ", Cell[BoxData[ \(a\)]], " or ", Cell[BoxData[ \(b\)]], " from each of the 10 terms ", Cell[BoxData[ \(\((a + b)\)\)]], ". If we consider the choice sequence as a product, it simply turns into \ ", Cell[BoxData[ \(\(a\^6\) b\^4\)]], ". Hence, ", Cell[BoxData[ \(Binomial[n, k]\)]], " is the number of choice sequences that contain exactly ", Cell[BoxData[ \(k\)]], " occurences of ", Cell[BoxData[ \(a\)]], ", and ", Cell[BoxData[ \(n - k\)]], " occurences of ", Cell[BoxData[ \(b\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["How can we count choice sequences.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Imagine you have ", Cell[BoxData[ \(k\)]], " distinct copies of ", Cell[BoxData[ \(a\)]], ", i.e., ", Cell[BoxData[ \(a\_1, a\_2, ... , a\_k\)]], " and ", Cell[BoxData[ \(n - k\)]], " distinct copies of ", Cell[BoxData[ \(b\)]], ", i.e., ", Cell[BoxData[ \(b\_1, \ b\_2, \ ... , b\_\(n - k\)\)]], ". We can arrange these ", Cell[BoxData[ \(n\)]], " different object in ", Cell[BoxData[ \(\(n!\)\)]], " different ways. But any two ways which only differ in how the indices are \ placed on the copies of ", Cell[BoxData[ \(a\)]], " are actually the same unindexed version of a choice sequence, and \ similarly for ", Cell[BoxData[ \(b\)]], "'s. Because there are ", Cell[BoxData[ \(\(k!\)\)]], " ways to arrange ", Cell[BoxData[ \(k\)]], " indices on ", Cell[BoxData[ \(a\)]], "'s, and there are ", Cell[BoxData[ \(\(\((n - k)\)!\)\)]], " ways to arrange ", Cell[BoxData[ \(n - k\)]], " indices on ", Cell[BoxData[ \(b\)]], "'s, we must divide by ", Cell[BoxData[ \(\(k!\)\[CenterDot]\(\((n - k)\)!\)\)]], " because that's how many times we counted each unindexed sequence. The \ final answer is then:" }], "Text"], Cell[TextData[Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], "=", \(\(n!\)\/\(\(k!\)\[CenterDot]\(\((n - k)\)!\)\)\)}]]]], "Text", TextAlignment->Center], Cell["We have proved the following theorem:", "Text"], Cell[TextData[{ StyleBox["Theorem: ", FontWeight->"Bold"], Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], "=", \(\(n!\)\/\(\(k!\)\[CenterDot]\(\((n - k)\)!\)\)\)}]]] }], "Theorem"] }, Closed]], Cell[CellGroupData[{ Cell["Sets and Binomial Coefficients", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:6"], Cell[TextData[{ "A slight modification of the argument in the last section produces yet \ another important characterization of binomial coefficients. We know that ", Cell[BoxData[ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}]]], "is the number of sequences with ", Cell[BoxData[ \(k\)]], " occurences of ", Cell[BoxData[ \(a\)]], " and ", Cell[BoxData[ \(n - k\)]], " occurences of ", Cell[BoxData[ \(b\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "This is the same as having ", Cell[BoxData[ \(n\)]], " places and deciding into which ", Cell[BoxData[ \(k\)]], " of them we shall place ", Cell[BoxData[ \(a\)]], "'s (the remaining places get filled by ", Cell[BoxData[ \(b\)]], "'s). But this is the same as having a set of ", Cell[BoxData[ \(n\)]], " positions and picking ", Cell[BoxData[ \(k\)]], " of them, which is the same as having a set of size ", Cell[BoxData[ \(n\)]], " and picking a subset of size ", Cell[BoxData[ \(k\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["Hence we have shown the following. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Theorem:", FontWeight->"Bold"], " ", StyleBox["A set with of size ", FontFamily->"Times"], Cell[BoxData[Cell["n"]], FontFamily->"Times"], StyleBox[" has ", FontFamily->"Times"], Cell[BoxData[ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}]], FontFamily->"Times"], StyleBox[" subsets of size ", FontFamily->"Times"], Cell[BoxData[ FormBox[ StyleBox["k", FontFamily->"Times"], TraditionalForm]]], StyleBox[".", FontFamily->"Times"] }], "Text"], Cell["Example: Here is a simple demonstration with Mathematica.", "Example"], Cell[BoxData[{ \(bin63 = Cases[PowerSet[Range[6]], {_, _, _}]\), "\n", \(Length[bin63]\)}], "Input"], Cell["Binomial[6,3]", "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Pascal's Triangle", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:7"], Cell["\<\ The standard arrangement for binomial coefficients is the \ triangular pattern below. This device is called Pascal's triangle:\ \>", \ "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 ...\ \>", "Text", Evaluatable->False, AspectRatioFixed->True, FontFamily->"Courier", FontWeight->"Bold"], Cell["\<\ On the screen, it is easier to deal with a rectangular arrangement \ as in \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Table[ ", StyleBox["Binomial[i,j]", FontColor->RGBColor[0, 0, 1]], ", {i,0,8}, {j,0,8} ] // TableForm[#,TableSpacing->{2,2}]&" }], "Input"], Cell["This looks better modulo 2:", "Text"], Cell[TextData[{ "tab = Table[ Mod[", StyleBox["Binomial[i,j],2]", FontColor->RGBColor[0, 0, 1]], ", {i,0,50},{j,0,50} ];\ntab // TableForm[#,TableSpacing->{0,0}]&" }], "Input"], Cell["PlotMatrix[tab];", "Input"], Cell["\<\ Computing large binomial coefficients in order to check whether \ they are even or odd is rather wasteful. Here is a better approach (see the \ section on recursive binomials below):\ \>", "Text"], Cell[BoxData[{ \(\(ClearAll[bin2];\)\), "\n", \(\(bin2[n_, 0] := 1;\)\), "\n", \(\(bin2[n_, n_] := 1;\)\), "\n", \(\(bin2[n_, k_] := \((bin2[n, k] = Mod[bin2[n - 1, k] + bin2[n - 1, k - 1], 2])\) /; 0 < k < n;\)\), "\n", \(\(bin2[n_, k_] := 0;\)\)}], "Input"], Cell[BoxData[{ \(\(tab = Table[bin2[i, j], {i, 0, 100}, {j, 0, 100}];\)\), "\n", \(\(PlotMatrix[tab];\)\)}], "Input"], Cell[CellGroupData[{ Cell["Empty Triangles", "Subsubsection", CellTags->"c:8"], Cell[TextData[{ "If you look at the picture carefully, you will see that there is a \ sequence of big empty triangles. The lower side of the largest such triangle \ is around row number ", Cell[BoxData[ \(30\)]], ", and the next such smaller row is around ", Cell[BoxData[ \(15\)]], ". These rows are completely black, except for the first and the last \ pixel." }], "Text"], Cell[TextData[{ StyleBox["Question", FontWeight->"Bold"], ":", StyleBox[" For what values of ", FontWeight->"Plain"], Cell[BoxData[ \(n\)]], " does the ", Cell[BoxData[ \(n\)]], "\[Dash]th row of Pascal's triangle mod ", Cell[BoxData[ \(2\)]], " consist of only ", Cell[BoxData[ \(0\)]], "'s (except for the initial and final ", Cell[BoxData[ \(1\)]], " which are always there?)" }], "Text"], Cell["\<\ The following Mathematica code returns the numbers of such \ rows:\ \>", "Text"], Cell["\<\ Position[Map[ Function[row, Count[row, 1]], Table[bin2[i,j], {i,0,42}, {j,0,42}] ], 2] - 1 // Flatten\ \>", "Input"], Cell[TextData[{ "It seems like those would be powers of ", Cell[BoxData[ \(2\)]], "." }], "Text"], Cell["Exercise:", "Exercise"], Cell[TextData[{ "Prove that ", Cell[BoxData[ RowBox[{"(", GridBox[{ {\(2\^k\)}, {"i"} }], ")"}]]], " is an even number for every ", Cell[BoxData[ \(TraditionalForm\`0 < i < 2\^k - 1\)]], "." }], "Text"], Cell[TextData[{ StyleBox["Hint", FontWeight->"Bold"], ":", StyleBox[" By induction on ", FontWeight->"Plain"], Cell[BoxData[ \(k\)]], " and use the identity ", Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {\(2\^k\)}, {"i"} }], ")"}], "\[Equal]", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->18], \(j = 0\), "i"], RowBox[{"(", RowBox[{ RowBox[{"(", GridBox[{ {\(2\^\(k - 1\)\)}, {\(i - j\)} }], ")"}], "+", RowBox[{"(", GridBox[{ {\(2\^\(k - 1\)\)}, {"j"} }], ")"}]}], ")"}]}]}]]], "." }], "Text"], Cell["Sub\[Dash]Exercise:", "Exercise"], Cell[TextData[{ "Prove the identity ", Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {\(a + b\)}, {"i"} }], ")"}], "\[Equal]", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->18], \(j = 0\), "i"], RowBox[{"(", RowBox[{ RowBox[{"(", GridBox[{ {"a"}, {\(i - j\)} }], ")"}], "+", RowBox[{"(", GridBox[{ {"b"}, {"j"} }], ")"}]}], ")"}]}]}]]], ", which is a generalized version of the identity used in the previous \ exercise." }], "Text"], Cell[TextData[{ StyleBox["Hint:", FontWeight->"Bold"], " Suppose ", Cell[BoxData[ \(A\)]], " is a set with ", Cell[BoxData[ \(a\)]], " elements, ", Cell[BoxData[ \(B\)]], " is a set with ", Cell[BoxData[ \(b\)]], " elements, and the sets ", Cell[BoxData[ \(A\)]], " and ", Cell[BoxData[ \(B\)]], " are disjoint. How many subsets of size ", Cell[BoxData[ \(i\)]], " does the sets ", Cell[BoxData[ \(A \[Union] B\)]], " have? For the right\[Dash]hand side of the identity, think about how each \ ", Cell[BoxData[ \(i\)]], "\[Dash]element subset of ", Cell[BoxData[ \(A \[Union] B\)]], " gets ", Cell[BoxData[ \(i - j\)]], " elements from ", Cell[BoxData[ \(A\)]], " and ", Cell[BoxData[ \(j\)]], " elements from ", Cell[BoxData[ \(B\)]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Summing up", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:9"], Cell[TextData[{ "The number of ", StyleBox["1", FontWeight->"Bold"], "'s in the n-th row is obviously a complicated function of n in general, \ though we have simple values for ", StyleBox[" n == 2", FontWeight->"Bold"], StyleBox["k", FontWeight->"Bold", FontVariations->{"CompatibilityType"->"Superscript"}], StyleBox[" (-1)", FontWeight->"Bold"], ". Perhaps surprisingly, if we add up all the values up to a power of ", StyleBox["2", FontWeight->"Bold"], ", we obtain a simple result. Let us write ", StyleBox["c", FontWeight->"Bold"], StyleBox["i", FontWeight->"Bold", FontVariations->{"CompatibilityType"->"Subscript"}], " for the number of ", StyleBox["1", FontWeight->"Bold"], "'s in row ", StyleBox["i", FontWeight->"Bold"], ".\n\nHere are the sums of the cnt values ", Cell[BoxData[ \(TraditionalForm\`c\_i\)]], " for ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(0\ \[LessEqual] \ i\ < \ 2\^k\)\)\)]], "." }], "Text"], Cell["\<\ cnt = Map[ Function[row, Count[row, 1]], Table[bin2[i,j], {i,0,42}, {j,0,42}] ];\ \>", "Input"], Cell[BoxData[ \(\((Plus @@ Take[cnt, #1] &)\) /@ \(2\^Range[5]\)\)], "Input"], Cell[TextData[{ "These should look quite familiar. Right, powers of ", StyleBox["3", FontWeight->"Bold"], ". \n\n", StyleBox["Claim:", FontWeight->"Bold"], " ", Cell[BoxData[ \(TraditionalForm\`\[Sum]\+\(i = 0\)\%\(2\^\(\(\ \)\(k\)\)\)\ c\_i\ = \ 3\^k\)]], "." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Recursive Binomials", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:10"], Cell[TextData[{ StyleBox["\n", FontFamily->"Times"], StyleBox["Theorem", FontFamily->"Times", FontWeight->"Bold"], StyleBox[":", FontFamily->"Times"], "\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], "=", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n - 1\)}, {"k"} }], ")"}], " ", "+", " ", RowBox[{"(", GridBox[{ {\(n - 1\)}, {\(k - 1\)} }], ")"}]}]}], TraditionalForm]]], "\n\t" }], "Text"], Cell[TextData[StyleBox["Proof:", FontWeight->"Bold"]], "MR"], Cell[TextData[{ "The theorem says that the coefficient at ", Cell[BoxData[ \(x\^\(k + 1\)\)]], "in the expansion of ", Cell[BoxData[ \(\((1 + x)\)\^\(n + 1\)\)]], " is the sum of coefficients at ", Cell[BoxData[ \(x\^k\)]], " and ", Cell[BoxData[ \(x\^\(k + 1\)\)]], " in the expansion of ", Cell[BoxData[ \(\((1 + x)\)\^n\)]], ". The best way to prove this is to get a connection between ", Cell[BoxData[ \(\((1 + x)\)\^\(n + 1\)\)]], " and ", Cell[BoxData[ \(\((1 + x)\)\^n\)]], ", preferably in the form of an equation:" }], "Text"], Cell[TextData[Cell[BoxData[ \(\((1 + x)\)\^\(n + 1\) = \(\((1 + x)\)\[CenterDot]\((1 + x)\)\^n = \((1 + x)\)\^n + x\[CenterDot]\((1 + x)\)\^n\)\)]]], "Text", TextAlignment->Center], Cell[TextData[{ "Imagine what happens when we expand both sides of the equation. What is \ the coefficient at ", Cell[BoxData[ \(x\^\(k + 1\)\)]], "on the left? Well, ", Cell[BoxData[ RowBox[{"(", GridBox[{ {\(n + 1\)}, {\(k + 1\)} }], ")"}]]], " of course. What is the coefficient at ", Cell[BoxData[ \(x\^\(k + 1\)\)]], "on the right? One part of it comes from ", Cell[BoxData[ \(\((1 + x)\)\^n\)]], " and a second one from ", Cell[BoxData[ \(x\[CenterDot]\((1 + x)\)\^n\)]], ". The first part is ", Cell[BoxData[ RowBox[{"(", GridBox[{ {"n"}, {\(k + 1\)} }], ")"}]]], ", and the second part is ", Cell[BoxData[ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}]]], " because multiplying ", Cell[BoxData[ \(\((1 + x)\)\^n\)]], " by ", Cell[BoxData[ \(x\)]], " shifts all coefficients by one. Since coefficients on the left must match \ coefficients on the right, we get" }], "Text"], Cell[TextData[Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {\(n + 1\)}, {\(k + 1\)} }], ")"}], "=", RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], "+", RowBox[{"(", GridBox[{ {"n"}, {\(k + 1\)} }], ")"}]}]}]]]], "Text", TextAlignment->Center], Cell[TextData[StyleBox["QED", FontWeight->"Bold"]], "Text"], Cell["To discover what use the theorem is, read the next section.", "Text"], Cell[TextData[{ StyleBox["\nCan check our basic recurrence:\n", FontFamily->"Times"], "\n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], "=", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n - 1\)}, {"k"} }], ")"}], " ", "+", " ", RowBox[{"(", GridBox[{ {\(n - 1\)}, {\(k - 1\)} }], ")"}]}]}], TraditionalForm]]], "\n\t" }], "Text"], Cell["\<\ ClearAll[bin]; bin[n_, k_] := 0 /; ( k<0 || k>n ); bin[n_, 0] := 1 bin[n_, n_] := 1 bin[n_, k_] := \tbin[n, k] = bin[n-1, k] + bin[n-1, k-1]\ \>", "Input"], Cell["\<\ Table[ bin[i,j], {i,0,8}, {j,0,8} ] // \ TableForm[#,TableSpacing->{2,2}]&\ \>", "Input"], Cell[TextData[{ "\nWe have an alternative way to express binomials in terms of \"earlier\" \ ones:\n\n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], "=", " ", RowBox[{ StyleBox[\(\(n - k + 1\)\/k\), FontSize->23], " ", RowBox[{"(", GridBox[{ {"n"}, {\(k - 1\)} }], ")"}]}]}], " "}], TraditionalForm]]] }], "Text"], Cell[BoxData[{ \(\(ClearAll[bin];\)\), "\n", \(\(bin[n_, k_] := 0 /; k < 0 || k > n;\)\), "\n", \(bin[n_, 0] := 1\), "\n", \(bin[n_, n_] := 1\), "\n", \(bin[n_, k_] := \((n - k + 1)\)\ bin[n, k - 1]/k\)}], "Input"], Cell["\<\ Table[ bin[i,j], {i,0,8}, {j,0,8} ] // \ TableForm[#,TableSpacing->{2,2}]&\ \>", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Manhattan", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:11"], Cell[CellGroupData[{ Cell["Geometry and Algebra", "Subsubsection", CellTags->"c:12"], Cell[TextData[{ "Binomial coefficients play an important role in many combinatorial \ problems. A particularly well known application is that of counting paths in \ a rectangular grid. Suppose we have a ", Cell[BoxData[ \(n\)]], " by ", Cell[BoxData[ \(m\)]], " grid, and think of the lines as being one\[Dash]way streets. Movement is \ allowed only in directions North and East. If you start at the \ South\[Dash]West corner, how many ways are there to get to the \ North\[Dash]East corner?" }], "Text"], Cell[TextData[{ "It is not too hard to generate all possible paths by a little recursive \ program such as the following one. The key idea is:\n\[Bullet] there is only \ one path to points with coordinates", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\((0, i)\)\(\ \)\)\)]], "or ", Cell[BoxData[ \(TraditionalForm\`\((i, 0)\)\)]], ",\n\[Bullet] any path to point ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\((i, j)\)\)\)]], " must consist of a path to", Cell[BoxData[ \(TraditionalForm\`\(\(\ \ \)\((i - 1, j)\)\(\ \)\)\)]], "or ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\((j - 1, i)\)\)\)]], ", plus one edge. " }], "Text"], Cell[BoxData[{ \(\(ClearAll[paths];\)\), "\n", \(paths[i_, 0] := {Table[{k, 0}, {k, 0, i}]}\), "\n", \(paths[0, i_] := {Table[{0, k}, {k, 0, i}]}\), "\n", \(paths[n_, m_] := \(paths[n, m] = Function[p, Append[p, {n, m}]] /@ Join[paths[n - 1, m], paths[n, m - 1]]\)\)}], "Input"], Cell["paths[2, 3] // ColumnForm", "Input"], Cell[TextData[{ "Thus, there are 10 paths from ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\((0, 0)\)\(\ \)\)\)]], " to ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\((2, 3)\)\)\)]], ":" }], "Text"], Cell["Length[paths[2, 3]]", "Input"], Cell["In general, the numbers a slightly confusing:", "Text"], Cell["Length[paths[3,4]]", "Input"], Cell["Map[ Length[paths[3,#]]&, Range[5] ]", "Input"], Cell["\<\ Let us make a table of the number of paths to various points:\ \>", \ "Text"], Cell["\<\ Table[Length[paths[n,m]], {n, 0, 7}, {m, 0, 7}] // \ TableForm[#,TableSpacing->{1,1}]&\ \>", "Input"], Cell[TextData[{ StyleBox["Theorem", FontWeight->"Bold"], ": \nThe number of up/right paths from the origin ", Cell[BoxData[ \(TraditionalForm\`\((0, 0)\)\)]], " to point ", Cell[BoxData[ \(TraditionalForm\`\((n, m)\)\)]], " is ", Cell[BoxData[ FormBox[ RowBox[{" ", RowBox[{"(", GridBox[{ {\(n + m\)}, {"n"} }], ")"}]}], TraditionalForm]]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Pictures", "Subsubsection", CellTags->"c:13"], Cell["\<\ One advantage of the path approach to binomial coefficients is that \ one can easily produce pictures. The pictures can be used to prove, or at \ least motivate, some interesting summation formulae involving binomial \ coefficients, but we won't get into that here. \ \>", "Text"], Cell["\<\ ClearAll[PathToGraphics]; PathToGraphics[L_List] := Graphics[ \tJoin[{Red, AbsoluteThickness[3], Line[L], \t\tBlue, AbsolutePointSize[4]}, \t\tMap[Point, L]], \tAspectRatio\[Rule]Automatic, \tGridLines\[Rule]{Range[Max[First/@L]],Range[Max[Last/@L]]}, \tAxes\[Rule]True, Ticks->False ]\ \>", "Input"], Cell["\<\ gr = Show[PathToGraphics[paths[5,4]\[LeftDoubleBracket]30\ \[RightDoubleBracket]]];\ \>", "Input"], Cell["\<\ We can even produce a movie that shows all paths, as enumerated by \ the path algorithm. \ \>", "Text"], Cell["\<\ ClearAll[Movie]; Movie[n_, m_] := Map[PathToGraphics, paths[n,m]]\ \>", "Input"], Cell[BoxData[ \(Movie[3, 3]\)], "Input"], Cell[BoxData[ \(ShowArray[%]\)], "Input"], Cell[TextData[{ "To watch the movie, evaluate the following cell, select its output and \ choose ", StyleBox["Format::Animate Selected Graphics", FontSlant->"Italic"], " from the menu." }], "Text"], Cell["Map[Show, Movie[3,3]];", "Input"], Cell["ShowArray[ Movie[4,3] ];", "Input"], Cell["\<\ And here is a function which converts a path into a list of \"north\ \" and \"east\" directions.\ \>", "Text"], Cell["\<\ ClearAll[PathToDirections]; PathToDirections[L_] := Map[ Function[pair, Apply[Subtract, pair]], \t\tPartition[L, 2, 1]] /. \t{ {-1,0}\[Rule]\"E\", {0,-1}\[Rule]\"N\" }\ \>", "Input"], Cell["\<\ p = paths[4,4]\[LeftDoubleBracket]25\[RightDoubleBracket] PathToDirections[p]\ \>", "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Summation Identities", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:14"], Cell["\<\ Counting paths in a grid and coming up with a binomial is \ interesting, but if that were the end of the whole story it would hardly be \ worth the effort. However, there are a number of summation formul\[AE] \ involving binomials that are somewhat difficult to grasp abstractly, but \ become very clear once you think about paths in a grid. Here are three of \ them. \ \>", "Text"], Cell[CellGroupData[{ Cell["Theorem 1", "Subsection", CellTags->"c:15"], Cell[TextData[{ StyleBox["Theorem 1: ", FontWeight->"Bold"], " ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Sum]\_\(i = 0\)\%n\), " \[VeryThinSpace]", SuperscriptBox[ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"i"} }], ")"}], "\[ThinSpace]"}], "2"]}], "=", " ", RowBox[{"(", GridBox[{ {\(2 n\)}, {"n"} }], ")"}]}], TraditionalForm]]] }], "Theorem", FontColor->GrayLevel[0]], Cell["Proof:", "Sub3section"], Cell["\<\ The trick is the following. We count something in two different \ ways. The first time we count we get the left\[Dash]hand side of the \ identity, the second time we get the right\[Dash]hand side. Since we counted \ the same thing, the two sides must be equal. But what do we count?\ \>", \ "Text"], Cell["Consider the following picture:", "Text"], Cell["\<\ n = 7; gr = Show[Graphics[Join[ {AbsolutePointSize[10], Green, Point[{0,0}], Red, Point[{n,n}], Blue}, Table[Point[{k,n-k}], {k,0,n}] ], AspectRatio\[Rule]Automatic, GridLines\[Rule]Automatic, \ Axes\[Rule]True]];\ \>", "Input"], Cell["\<\ A very good question: what is a cheap way to generate a picture of \ a path to a diagonal point, and then its symmetric continuation on the other \ side? \ \>", "Text"], Cell["\<\ Clear[diff] diff[L_List] := Drop[L,1] - Drop[L,-1]; diffToPath[ xx_, dd_ ] := FoldList[ Plus, xx, dd ];\ \>", "Input"], Cell["\<\ pp = paths[4,3][[17]]; ppp = diffToPath[ Last[pp], \t\t\t\tReverse[Reverse /@ diff[pp] ] ]; grr = PathToGraphics[Join[pp,Rest[ppp]]]; gg = Show[ {gr,grr} ];\ \>", "Input"], Cell[TextData[{ "This is a grid of size ", Cell[BoxData[ \(\((n + 1)\)\[Cross]\((n + 1)\)\)]], ", in the picture ", Cell[BoxData[ \(n \[Equal] 7\)]], ". How many paths are there from the green point to the red point? By a \ theorem in the previous section, there are ", Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {\(n + n\)}, {"n"} }], ")"}], "\[Equal]", RowBox[{"(", GridBox[{ {\(2\[CenterDot]n\)}, {"n"} }], ")"}]}]]], " such paths. OK, we have the right\[Dash]hand side of the equation." }], "Text"], Cell[TextData[{ "Now, what are the blue points doing there? ", StyleBox["Every path from the green point to the red point passes through \ exactly one blue point.", FontWeight->"Bold"], " There are ", Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {\(n - i + i\)}, {"i"} }], ")"}], "\[Equal]", RowBox[{"(", GridBox[{ {"n"}, {"i"} }], ")"}]}]]], " paths from the green point to a blue point with coordinates ", Cell[BoxData[ \(\((i, \ n - i)\)\)]], ". There are also ", Cell[BoxData[ RowBox[{"(", GridBox[{ {"n"}, {"i"} }], ")"}]]], " points from the blue point with coordinates ", Cell[BoxData[ \(\((i, n - i)\)\)]], " to the red point. Therefore, there are ", Cell[BoxData[ RowBox[{ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"i"} }], ")"}], "\[CenterDot]", RowBox[{"(", GridBox[{ {"n"}, {"i"} }], ")"}]}], "\[Equal]", SuperscriptBox[ RowBox[{"(", GridBox[{ {"n"}, {"i"} }], ")"}], "2"]}]]], " paths that start at the green point, pass through the blue point ", Cell[BoxData[ \(\((i, n - i)\)\)]], ", and end in the red point. But if we add up all the paths that pass \ through each blue point, we get the number of all paths from the green to the \ red point. When we add up, we get the sum ", Cell[BoxData[Cell[TextData[Cell[BoxData[ FormBox[Cell[TextData[Cell[BoxData[ FormBox[ RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(i = 0\), "n"], SuperscriptBox[ RowBox[{"(", GridBox[{ {"n"}, {"i"} }], ")"}], "2"]}], TraditionalForm]]]]], TraditionalForm]]]]]]], ", which is exactly the left\[Dash]hand side." }], "Text"], Cell["\<\ So, to repeat, the right\[Dash]hand side is the number of all paths \ from the green point to the red point. The left\[Dash]hand side is the number \ of all paths from the green point to the red point, where we count paths \ through each of the blue points separately. Clearly, the left\[Dash]hand side \ must then be equal to the right\[Dash]hand side.\ \>", "Text"], Cell["QED", "Text"], Cell["\<\ By the way, Mathematica can do it, too:\ \>", "Text"], Cell[BoxData[{ \(\[Sum]\_\(i\ = 0\)\%n Binomial[n, i]\^2 - \ Binomial[2 n, n]\ \), "\[IndentingNewLine]", \(% // \ FullSimplify\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Theorem 2", "Subsection", CellTags->"c:16"], Cell[TextData[{ StyleBox["Theorem 2: ", FontWeight->"Bold"], " ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Sum]\_\(i = 0\)\%n\), " ", RowBox[{"(", GridBox[{ {\(r + i\)}, {"i"} }], ")"}]}], "=", " ", RowBox[{"(", GridBox[{ {\(n + r + 1\)}, {\(r + 1\)} }], ")"}]}], TraditionalForm]]] }], "Theorem", FontColor->GrayLevel[0]], Cell["First, let us see what Mathematica says:", "Text"], Cell["\<\ Sum[Binomial[r+i, i], {i,0,n}] - Binomial[n+r+1, r+1] // \ FullSimplify\ \>", "Input"], Cell[TextData[{ "OK, we believe the theorem. And now let us do it by hand. We already know \ the trick. We interpret the right\[Dash]hand side as the number of paths in a \ grid of size ", Cell[BoxData[ \(\((n + 1)\)\[Cross]\((r + 2)\)\)]], ". Remember, the grid starts at point ", Cell[BoxData[ \(\((0, 0)\)\)]], ", so if the upper\[Dash]right corner is supposed to be ", Cell[BoxData[ \(\((n, r + 1)\)\)]], ", then that makes a grid of size ", Cell[BoxData[ \(\((n + 1)\)\[Cross]\((r + 2)\)\)]], "." }], "Text"], Cell[TextData[{ "How do we interpret the left\[Dash]hand side? The expression ", Cell[BoxData[ RowBox[{"(", GridBox[{ {\(r + i\)}, {"i"} }], ")"}]]], " suggests that we should look at all the paths through the point with \ coordinates ", Cell[BoxData[ \(\((i, r)\)\)]], ", where ", Cell[BoxData[ \(i\)]], " goes from ", Cell[BoxData[ \(0\)]], " to ", Cell[BoxData[ \(n\)]], "." }], "Text"], Cell["\<\ n = 7; r = 3; Show[Graphics[Join[ {AbsolutePointSize[9], Green, Point[{0,0}], Red, Point[{n,r+1}], Blue}, Table[Point[{k,r}], {k,0,n}] ], AspectRatio\[Rule]Automatic, GridLines\[Rule]Automatic, \ Axes\[Rule]True]];\ \>", "Input"], Cell[TextData[{ "Complete the proof, with the following idea in mind: ", StyleBox["every path from the green point to the red point goes upward at \ exactly one of the blue points", FontWeight->"Bold"], ", i.e., it may pass through more than one blue point, but it will go \ upward at exactly one of them." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Theorem 3", "Subsection", CellTags->"c:17"], Cell[TextData[{ StyleBox["Theorem 3", FontWeight->"Bold"], ": For all ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ": ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Sum]\_\(i = 0\)\%\(n/2\)\), " ", RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}]}], " ", "=", " ", \(F\_\(n + 1\)\)}], TraditionalForm]]], " \nwhere ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], " is the ", Cell[BoxData[ \(TraditionalForm\`n\)]], "th Fibonacci number. " }], "Text"], Cell["A little test:", "Text"], Cell[TextData[StyleBox["n = Random[Integer,{100,200}]\nSum[ Binomial[ n-i, i \ ], {i, 0, n/2} ]\nFibonacci[n+1]", FontWeight->"Bold"]], "Input"], Cell["Proof:", "Sub3section"], Cell["Let us see what Mathematica says:", "Text"], Cell["\<\ Clear[n] Sum[Binomial[n - i, i], {i, 0, n/2}]\ \>", "Input"], Cell["\<\ Ugh, we do not really want to deal with Chebyshev polynomials. Let \ us define:\ \>", "Text"], Cell[TextData[Cell[BoxData[ RowBox[{\(G\_n\), "\[Equal]", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(i = 0\), \(n/2\)], RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}]}]}]]]], "Text"], Cell[TextData[{ "If we can prove that ", Cell[BoxData[ \(G\_n\)]], " satisfies the same recurrence equations as ", Cell[BoxData[ \(F\_n\)]], " then ", Cell[BoxData[ \(G\_n \[Equal] F\_n\)]], " and we are done. Thus, we have to check three equations:" }], "Text"], Cell[TextData[Cell[BoxData[ \(G\_0 \[Equal] 1\)]]], "Text"], Cell[TextData[Cell[BoxData[ \(G\_1 \[Equal] 1\)]]], "Text"], Cell[TextData[Cell[BoxData[ \(G\_\(n + 2\) \[Equal] G\_\(n + 1\) + G\_n\)]]], "Text"], Cell["The first two are easy:", "Text"], Cell["\<\ ClearAll[G]; G[n_]:= Sum[Binomial[n - i, i], {i, 0, n/2}]\ \>", "Input"], Cell["\<\ G[0] == 1 G[1] == 1\ \>", "Input"], Cell[TextData[{ "How about the third one? We try to prove that ", Cell[BoxData[ \(G\_\(n + 2\) - G\_\(n + 1\) - G\_n \[Equal] 0\)]], ". First we consider the case when ", Cell[BoxData[ \(n\)]], " is an even number, because then ", Cell[BoxData[ RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->24], \(i = 0\), \(\((n + 1)\)/2\)], RowBox[{"\[Equal]", UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->24], \(i = 0\), \(n/2\)]}]}]]], ". Can you follow the steps in the following manipulation? Describe what \ happens at each step:" }], "Text"], Cell[TextData[Cell[BoxData[ \(\(\(G\_\(n + 2\) - G\_\(n + 1\) - G\_n\)\(\[Equal]\)\)\)]]], "Text"], Cell[TextData[{ "[use the definition of ", Cell[BoxData[ \(G\_n\)]], "]" }], "MR"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", RowBox[{ RowBox[{\(\[Sum]\+\(i = 0\)\%\(\((n + 2)\)/2\)\), RowBox[{"(", GridBox[{ {\(n + 2 - i\)}, {"i"} }], ")"}]}], "-", RowBox[{\(\[Sum]\+\(i = 0\)\%\(n/2\)\), RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}]}], "-", RowBox[{\(\[Sum]\+\(i = 0\)\%\(\((n + 1)\)/2\)\), RowBox[{"(", GridBox[{ {\(n + 1 - i\)}, {"i"} }], ")"}]}]}]}]]]], "Text"], Cell[TextData[{ "[merge the second and the third sum because they have the same bounds \ \[LongDash] ", Cell[BoxData[ \(n\)]], " is even]" }], "Text"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{\(\[Sum]\+\(i = 0\)\%\(\((n/2)\) + 1\)\), RowBox[{"(", GridBox[{ {\(n + 2 - i\)}, {"i"} }], ")"}]}], "-", RowBox[{\(\[Sum]\+\(i = 0\)\%\(n/2\)\), RowBox[{"(", RowBox[{ RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}], "+", RowBox[{"(", GridBox[{ {\(n + 1 - i\)}, {"i"} }], ")"}]}], ")"}]}]}]}]]]], "Text"], Cell["\<\ [extract the last term from the first sum, then both sums have the \ same bound so we can merge them]\ \>", "Text"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - \((n/2)\) - 1\)}, {\(n/2 + 1\)} }], ")"}], "+", RowBox[{\(\[Sum]\+\(i = 0\)\%\(n/2\)\), RowBox[{"(", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - i\)}, {"i"} }], ")"}], "-", RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}], "-", RowBox[{"(", GridBox[{ {\(n + 1 - i\)}, {"i"} }], ")"}]}], ")"}]}]}]}]]]], "Text"], Cell[TextData[{ "[simplify the term inside the sum, using the fact that ", Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - i\)}, {"i"} }], ")"}], "\[Equal]", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 1 - i\)}, {"i"} }], ")"}], "+", RowBox[{"(", GridBox[{ {\(n + 1 - i\)}, {\(i - 1\)} }], ")"}]}]}]]], "]" }], "MR"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - \((n/2)\) - 1\)}, {\(n/2 + 1\)} }], ")"}], "+", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(i = 0\), \(n/2\)], RowBox[{"(", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 1 - i\)}, {\(i - 1\)} }], ")"}], "-", RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}]}], ")"}]}]}]}]]]], "Text"], Cell["[split the sum into two sums]", "MR"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - \((n/2)\) - 1\)}, {\(n/2 + 1\)} }], ")"}], "+", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(i = 0\), \(n/2\)], RowBox[{"(", GridBox[{ {\(n + 1 - i\)}, {\(i - 1\)} }], ")"}]}], "-", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(i = 0\), \(n/2\)], RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}]}]}]}]]]], "Text"], Cell["[shift the index in the first sum]", "MR"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - \((n/2)\) - 1\)}, {\(n/2 + 1\)} }], ")"}], "+", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(j = \(-1\)\), \(\((n/2)\) - 1\)], RowBox[{"(", GridBox[{ {\(n - j\)}, {"j"} }], ")"}]}], "-", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(i = 0\), \(n/2\)], RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}]}]}]}]]]], "Text"], Cell[TextData[{ "[use the fact that ", Cell[BoxData[ RowBox[{ RowBox[{"(", GridBox[{ {\(n - j\)}, {"j"} }], ")"}], "\[Equal]", "0"}]]], " when ", Cell[BoxData[ \(j \[Equal] \(-1\)\)]], " and extract the last term in the second sum]" }], "MR"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - \((n/2)\) - 1\)}, {\(n/2 + 1\)} }], ")"}], "+", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(j = 0\), \(\((n/2)\) - 1\)], RowBox[{"(", GridBox[{ {\(n - j\)}, {"j"} }], ")"}]}], "-", RowBox[{ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->12], \(i = 0\), \(\((n/2)\) - 1\)], RowBox[{"(", GridBox[{ {\(n - i\)}, {"i"} }], ")"}]}], "-", RowBox[{"(", GridBox[{ {\(n - \((n/2)\)\)}, {\(n/2\)} }], ")"}]}]}]]]], "Text"], Cell["[cancel the sums and simplify]", "MR"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n + 2 - \((n/2)\) - 1\)}, {\(n/2 + 1\)} }], ")"}], "-", RowBox[{"(", GridBox[{ {\(n - \((n/2)\)\)}, {\(n/2\)} }], ")"}]}]}]]]], "Text"], Cell[TextData[Cell[BoxData[ RowBox[{"\[Equal]", " ", RowBox[{ RowBox[{"(", GridBox[{ {\(n/2 + 1\)}, {\(n/2 + 1\)} }], ")"}], "-", RowBox[{"(", GridBox[{ {\(n/2\)}, {\(n/2\)} }], ")"}]}]}]]]], "Text"], Cell[TextData[Cell[BoxData[ \(\(\(\[Equal]\)\(\ \)\(1 - 1\)\)\)]]], "Text"], Cell[TextData[Cell[BoxData[ \(\(\(\[Equal]\)\(\ \)\(0\)\)\)]]], "Text"], Cell["Problem:", "Problem"], Cell[TextData[{ "Consider the case when ", Cell[BoxData[ \(n\)]], " is odd. Then ", Cell[BoxData[ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->24], \(i = 0\), \(\((n + 1)\)/2\)]]], " has one more term than ", Cell[BoxData[ UnderoverscriptBox[ StyleBox["\[Sum]", FontSize->24], \(i = 0\), \(n/2\)]]], ", so you will probably need to extract it before you can merge the two \ sums. Otherwise, it is pretty much the same as the case when ", Cell[BoxData[ \(n\)]], " is even." }], "Text"], Cell["QED", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Multinomial Coefficients", "Section", CellTags->"c:18"], Cell["\<\ There is a natural generalization of binomial coefficients that \ suggests itself when one deals with polynomial expressions in more than 2 \ variables. For example,\ \>", "Text"], Cell["\<\ Clear[a,b,c] pol = (a + b + c)^4 // Expand CoefficientList[pol,{a,b,c}] // MatrixForm\ \>", "Input"], Cell["\<\ Multinomial[1,1,2] Coefficient[ pol, a b c^2 ]\ \>", "Input"], Cell[TextData[{ "\nIn Mathematics, multinomial coefficients are usually denoted ", Cell[BoxData[ \(TraditionalForm\`\((n; n\_1, n\_2, ... , n\_k)\)\)], "InlineFormula"], " or \n\t\t", Cell[BoxData[ FormBox[ RowBox[{"(", GridBox[{ {"n"}, {\(n\_1, n\_2, \[Ellipsis], n\_k\)} }], ")"}], TraditionalForm]]], "\nwhere ", Cell[BoxData[ \(TraditionalForm\`n = \[Sum]\_\(i = 1\)\%k n\_i\)]], ". This is the coefficient of the monomial ", Cell[BoxData[ \(TraditionalForm\`\(x\_1\%\(n\_1\)\) \(x\_2\%\(n\_2\)\) \ \[Ellipsis]x\_k\%\(n\_k\)\)]], " in the expansion of ", Cell[BoxData[ \(TraditionalForm\`\((x\_1 + \ x\_2 + \ \[Ellipsis]\ + \ \ x\_k)\)\^n\)]], ".\nAlternatively, on can think of this number as the number of ways of \ partitioning ", Cell[BoxData[ \(TraditionalForm\`n\)], "InlineFormula"], " distinct objects into ", Cell[BoxData[ \(TraditionalForm\`k\)], "InlineFormula"], " sets of cardinality ", Cell[BoxData[ \(TraditionalForm\`n\_i\)], "InlineFormula"], ", respectively. " }], "Text"], Cell["\<\ It is a bit more complicated to display the coefficents for such \ higher order polynomials in any meaningful way. \ \>", "Text"], Cell["CoefficientList[pol,{a}] // MatrixForm", "Input"], Cell["CoefficientList[pol,{a,b}] // MatrixForm", "Input"], Cell["CoefficientList[pol,{a,b,c}] // MatrixForm", "Input"], Cell[TextData[{ "Note that in ", StyleBox["Mathematica", FontSlant->"Italic"], " only the ", Cell[BoxData[ \(TraditionalForm\`n\_i\)]], " are entered, since the ", Cell[BoxData[ \(TraditionalForm\`n\)]], " is redundant." }], "Text"], Cell["\<\ Multinomial[1,1,2] Coefficient[ pol, a b c^2 ]\ \>", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Problems", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:19"], Cell[CellGroupData[{ Cell["Even Subsets", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:20"], Cell[TextData[{ "\nShow that the total number of subsets of even cardinality of an \ n-element set is ", Cell[BoxData[ \(TraditionalForm\`2\^\(n - 1\)\)]], ". \n\nIn other words, show that \n ", StyleBox["Sum[ Binomial[ n, 2i ], {i,0,n/2} ] == 2", FontWeight->"Bold"], StyleBox["n-1", FontWeight->"Bold", FontVariations->{"CompatibilityType"->"Superscript"}], "." }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Subsubsets", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:21"], Cell[TextData[{ "\n(1) Show that \n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"m"} }], ")"}], RowBox[{"(", GridBox[{ {"m"}, {"k"} }], ")"}]}], " ", "=", RowBox[{ RowBox[{"(", GridBox[{ {"n"}, {"k"} }], ")"}], RowBox[{"(", GridBox[{ {\(n - k\)}, {\(m - k\)} }], ")"}]}]}], TraditionalForm]]], "\nfor ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ k\ \[LessEqual] \ m \[LessEqual] \ n\)]], " by counting the number of pairs ", Cell[BoxData[ \(TraditionalForm\`\((A, B)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`A\ \[SubsetEqual] \ B \[SubsetEqual] \ \([n]\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(\ \)\(\(A\)\(|\)\)\) = k\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(|\)\(\(B\)\(|\)\)\) = m\)]], " in two different ways. \n(2) Then provide an alernative proof by \ manipulating the factorial representation of binomials.\nNote that ", StyleBox["Mathematica", FontSlant->"Italic"], " can do this (though I don't know how the simplification works \ internally):" }], "Text"], Cell["\<\ Binomial[n,m] Binomial[m,k] - Binomial[n,k] Binomial[n-k,m-k] // \ FullSimplify\ \>", "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Summing binomials", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:22"], Cell["Prove the identity suggested by the following computation", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(m = Random[Integer, {1, 20}]\), "\n", \(n = m + Random[Integer, {1, 20}]\), "\n", \(\[Sum]\+\(k = m\)\%n Binomial[k, m]\), "\n", \(Binomial[n + 1, m + 1]\)}], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["A hard sum", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:23"], Cell["Prove the identity suggested by the following computation", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(m = Random[Integer, {1, 20}]\), "\n", \(r = m + Random[Integer, {1, 20}]\), "\n", \(\[Sum]\+\(k = 0\)\%m Binomial[r, k]\ \((r\/2 - k)\)\), "\n", \(1\/2\ \((m + 1)\)\ Binomial[r, m + 1]\)}], "Input", AspectRatioFixed->True] }, Closed]] }, Closed]] }, Open ]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, ScreenStyleEnvironment->"Working", WindowToolbars->{}, CellGrouping->Automatic, WindowSize->{984, 740}, WindowMargins->{{Automatic, 13}, {Automatic, 23}}, PrintingStartingPageNumber->20, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, 256}}, ShowCellLabel->True, ShowCellTags->False, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False}, CharacterEncoding->Automatic, Magnification->1.5, StyleDefinitions -> "Classic.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "c:1"->{ Cell[1821, 55, 105, 3, 125, "Title", Evaluatable->False, CellTags->"c:1"]}, "c:2"->{ Cell[1951, 62, 102, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"]}, "c:3"->{ Cell[2078, 69, 67, 1, 70, "Subsubsection", CellTags->"c:3"]}, "c:4"->{ Cell[4634, 175, 69, 1, 70, "Subsubsection", CellTags->"c:4"]}, "c:5"->{ Cell[5913, 222, 128, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:5"]}, "c:6"->{ Cell[9567, 373, 122, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:6"]}, "c:7"->{ Cell[11860, 475, 103, 3, 47, "Section", Evaluatable->False, CellTags->"c:7"]}, "c:8"->{ Cell[13881, 552, 59, 1, 70, "Subsubsection", CellTags->"c:8"]}, "c:9"->{ Cell[17984, 737, 102, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:9"]}, "c:10"->{ Cell[19706, 806, 106, 3, 47, "Section", Evaluatable->False, CellTags->"c:10"]}, "c:11"->{ Cell[24828, 1010, 96, 3, 47, "Section", Evaluatable->False, CellTags->"c:11"]}, "c:12"->{ Cell[24949, 1017, 66, 1, 70, "Subsubsection", CellTags->"c:12"]}, "c:13"->{ Cell[27716, 1117, 53, 1, 70, "Subsubsection", CellTags->"c:13"]}, "c:14"->{ Cell[29592, 1198, 107, 3, 47, "Section", Evaluatable->False, CellTags->"c:14"]}, "c:15"->{ Cell[30120, 1214, 51, 1, 70, "Subsection", CellTags->"c:15"]}, "c:16"->{ Cell[35389, 1393, 51, 1, 70, "Subsection", CellTags->"c:16"]}, "c:17"->{ Cell[37744, 1487, 51, 1, 70, "Subsection", CellTags->"c:17"]}, "c:18"->{ Cell[48434, 1884, 63, 1, 47, "Section", CellTags->"c:18"]}, "c:19"->{ Cell[50714, 1972, 95, 3, 47, "Section", Evaluatable->False, CellTags->"c:19"]}, "c:20"->{ Cell[50834, 1979, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:20"]}, "c:21"->{ Cell[51440, 2003, 103, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:21"]}, "c:22"->{ Cell[53114, 2063, 110, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:22"]}, "c:23"->{ Cell[53617, 2082, 103, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:23"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 55089, 2128}, {"c:2", 55192, 2132}, {"c:3", 55296, 2136}, {"c:4", 55379, 2139}, {"c:5", 55463, 2142}, {"c:6", 55574, 2146}, {"c:7", 55685, 2150}, {"c:8", 55791, 2154}, {"c:9", 55876, 2157}, {"c:10", 55989, 2161}, {"c:11", 56097, 2165}, {"c:12", 56205, 2169}, {"c:13", 56293, 2172}, {"c:14", 56381, 2175}, {"c:15", 56490, 2179}, {"c:16", 56575, 2182}, {"c:17", 56660, 2185}, {"c:18", 56745, 2188}, {"c:19", 56827, 2191}, {"c:20", 56935, 2195}, {"c:21", 57050, 2199}, {"c:22", 57165, 2203}, {"c:23", 57280, 2207} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 42, 0, 32, "MR"], Cell[CellGroupData[{ Cell[1821, 55, 105, 3, 125, "Title", Evaluatable->False, CellTags->"c:1"], Cell[CellGroupData[{ Cell[1951, 62, 102, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"], Cell[CellGroupData[{ Cell[2078, 69, 67, 1, 70, "Subsubsection", CellTags->"c:3"], Cell[2148, 72, 114, 3, 70, "Text"], Cell[2265, 77, 157, 7, 70, "Text"], Cell[2425, 86, 115, 3, 70, "Text"], Cell[2543, 91, 89, 5, 70, "Input"], Cell[2635, 98, 74, 0, 70, "Text"], Cell[2712, 100, 227, 8, 70, "Text"], Cell[2942, 110, 33, 0, 70, "Input"], Cell[2978, 112, 1304, 44, 70, "Text"], Cell[4285, 158, 34, 0, 70, "Input"], Cell[4322, 160, 44, 0, 70, "Input"], Cell[4369, 162, 106, 3, 70, "Input"], Cell[4478, 167, 119, 3, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[4634, 175, 69, 1, 70, "Subsubsection", CellTags->"c:4"], Cell[4706, 178, 419, 16, 70, "Text"], Cell[5128, 196, 748, 21, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[5913, 222, 128, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:5"], Cell[6044, 227, 1510, 56, 70, "Text", Evaluatable->False], Cell[7557, 285, 98, 2, 70, "Text", Evaluatable->False], Cell[7658, 289, 1303, 56, 70, "Text"], Cell[8964, 347, 231, 7, 70, "Text"], Cell[9198, 356, 53, 0, 70, "Text"], Cell[9254, 358, 276, 10, 70, "Theorem"] }, Closed]], Cell[CellGroupData[{ Cell[9567, 373, 122, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:6"], Cell[9692, 378, 560, 23, 70, "Text", Evaluatable->False], Cell[10255, 403, 649, 28, 70, "Text", Evaluatable->False], Cell[10907, 433, 99, 2, 70, "Text", Evaluatable->False], Cell[11009, 437, 577, 24, 70, "Text"], Cell[11589, 463, 77, 0, 70, "Example"], Cell[11669, 465, 109, 2, 70, "Input"], Cell[11781, 469, 30, 0, 70, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[11860, 475, 103, 3, 47, "Section", Evaluatable->False, CellTags->"c:7"], Cell[11966, 480, 202, 6, 70, "Text", Evaluatable->False], Cell[12171, 488, 434, 15, 70, "Text", Evaluatable->False], Cell[12608, 505, 147, 5, 70, "Text", Evaluatable->False], Cell[12758, 512, 166, 5, 70, "Input"], Cell[12927, 519, 43, 0, 70, "Text"], Cell[12973, 521, 186, 5, 70, "Input"], Cell[13162, 528, 33, 0, 70, "Input"], Cell[13198, 530, 206, 4, 70, "Text"], Cell[13407, 536, 320, 8, 70, "Input"], Cell[13730, 546, 126, 2, 70, "Input"], Cell[CellGroupData[{ Cell[13881, 552, 59, 1, 70, "Subsubsection", CellTags->"c:8"], Cell[13943, 555, 396, 11, 70, "Text"], Cell[14342, 568, 455, 21, 70, "Text"], Cell[14800, 591, 90, 3, 70, "Text"], Cell[14893, 596, 161, 5, 70, "Input"], Cell[15057, 603, 109, 5, 70, "Text"], Cell[15169, 610, 29, 0, 70, "Exercise"], Cell[15201, 612, 260, 11, 70, "Text"], Cell[15464, 625, 812, 30, 70, "Text"], Cell[16279, 657, 39, 0, 70, "Exercise"], Cell[16321, 659, 724, 24, 70, "Text"], Cell[17048, 685, 899, 47, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[17984, 737, 102, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:9"], Cell[18089, 742, 1031, 35, 70, "Text"], Cell[19123, 779, 131, 4, 70, "Input"], Cell[19257, 785, 81, 1, 70, "Input"], Cell[19341, 788, 316, 12, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[19706, 806, 106, 3, 47, "Section", Evaluatable->False, CellTags->"c:10"], Cell[19815, 811, 668, 26, 70, "Text"], Cell[20486, 839, 62, 1, 70, "MR"], Cell[20551, 842, 607, 23, 70, "Text"], Cell[21161, 867, 212, 4, 70, "Text"], Cell[21376, 873, 1079, 40, 70, "Text"], Cell[22458, 915, 408, 15, 70, "Text"], Cell[22869, 932, 61, 1, 70, "Text"], Cell[22933, 935, 75, 0, 70, "Text"], Cell[23011, 937, 589, 21, 70, "Text"], Cell[23603, 960, 169, 8, 70, "Input"], Cell[23775, 970, 99, 3, 70, "Input"], Cell[23877, 975, 571, 18, 70, "Text"], Cell[24451, 995, 238, 5, 70, "Input"], Cell[24692, 1002, 99, 3, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[24828, 1010, 96, 3, 47, "Section", Evaluatable->False, CellTags->"c:11"], Cell[CellGroupData[{ Cell[24949, 1017, 66, 1, 70, "Subsubsection", CellTags->"c:12"], Cell[25018, 1020, 526, 13, 70, "Text"], Cell[25547, 1035, 680, 19, 70, "Text"], Cell[26230, 1056, 317, 6, 70, "Input"], Cell[26550, 1064, 42, 0, 70, "Input"], Cell[26595, 1066, 219, 8, 70, "Text"], Cell[26817, 1076, 36, 0, 70, "Input"], Cell[26856, 1078, 61, 0, 70, "Text"], Cell[26920, 1080, 35, 0, 70, "Input"], Cell[26958, 1082, 53, 0, 70, "Input"], Cell[27014, 1084, 87, 3, 70, "Text"], Cell[27104, 1089, 111, 3, 70, "Input"], Cell[27218, 1094, 461, 18, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[27716, 1117, 53, 1, 70, "Subsubsection", CellTags->"c:13"], Cell[27772, 1120, 290, 5, 70, "Text"], Cell[28065, 1127, 332, 11, 70, "Input"], Cell[28400, 1140, 108, 3, 70, "Input"], Cell[28511, 1145, 113, 3, 70, "Text"], Cell[28627, 1150, 91, 4, 70, "Input"], Cell[28721, 1156, 44, 1, 70, "Input"], Cell[28768, 1159, 45, 1, 70, "Input"], Cell[28816, 1162, 207, 6, 70, "Text"], Cell[29026, 1170, 39, 0, 70, "Input"], Cell[29068, 1172, 41, 0, 70, "Input"], Cell[29112, 1174, 120, 3, 70, "Text"], Cell[29235, 1179, 202, 7, 70, "Input"], Cell[29440, 1188, 103, 4, 70, "Input"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[29592, 1198, 107, 3, 47, "Section", Evaluatable->False, CellTags->"c:14"], Cell[29702, 1203, 393, 7, 70, "Text"], Cell[CellGroupData[{ Cell[30120, 1214, 51, 1, 70, "Subsection", CellTags->"c:15"], Cell[30174, 1217, 580, 19, 70, "Theorem"], Cell[30757, 1238, 29, 0, 70, "Sub3section"], Cell[30789, 1240, 308, 6, 70, "Text"], Cell[31100, 1248, 47, 0, 70, "Text"], Cell[31150, 1250, 243, 9, 70, "Input"], Cell[31396, 1261, 179, 4, 70, "Text"], Cell[31578, 1267, 128, 4, 70, "Input"], Cell[31709, 1273, 182, 6, 70, "Input"], Cell[31894, 1281, 638, 20, 70, "Text"], Cell[32535, 1303, 2186, 65, 70, "Text"], Cell[34724, 1370, 377, 6, 70, "Text"], Cell[35104, 1378, 19, 0, 70, "Text"], Cell[35126, 1380, 64, 3, 70, "Text"], Cell[35193, 1385, 159, 3, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[35389, 1393, 51, 1, 70, "Subsection", CellTags->"c:16"], Cell[35443, 1396, 490, 17, 70, "Theorem"], Cell[35936, 1415, 56, 0, 70, "Text"], Cell[35995, 1417, 96, 3, 70, "Input"], Cell[36094, 1422, 555, 16, 70, "Text"], Cell[36652, 1440, 477, 21, 70, "Text"], Cell[37132, 1463, 244, 10, 70, "Input"], Cell[37379, 1475, 328, 7, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[37744, 1487, 51, 1, 70, "Subsection", CellTags->"c:17"], Cell[37798, 1490, 617, 23, 70, "Text"], Cell[38418, 1515, 30, 0, 70, "Text"], Cell[38451, 1517, 146, 2, 70, "Input"], Cell[38600, 1521, 29, 0, 70, "Sub3section"], Cell[38632, 1523, 49, 0, 70, "Text"], Cell[38684, 1525, 70, 3, 70, "Input"], Cell[38757, 1530, 103, 3, 70, "Text"], Cell[38863, 1535, 301, 9, 70, "Text"], Cell[39167, 1546, 294, 11, 70, "Text"], Cell[39464, 1559, 63, 1, 70, "Text"], Cell[39530, 1562, 63, 1, 70, "Text"], Cell[39596, 1565, 89, 1, 70, "Text"], Cell[39688, 1568, 39, 0, 70, "Text"], Cell[39730, 1570, 83, 4, 70, "Input"], Cell[39816, 1576, 44, 3, 70, "Input"], Cell[39863, 1581, 657, 19, 70, "Text"], Cell[40523, 1602, 102, 1, 70, "Text"], Cell[40628, 1605, 94, 5, 70, "MR"], Cell[40725, 1612, 608, 17, 70, "Text"], Cell[41336, 1631, 162, 6, 70, "Text"], Cell[41501, 1639, 638, 18, 70, "Text"], Cell[42142, 1659, 125, 3, 70, "Text"], Cell[42270, 1664, 726, 21, 70, "Text"], Cell[42999, 1687, 508, 18, 70, "MR"], Cell[43510, 1707, 675, 20, 70, "Text"], Cell[44188, 1729, 43, 0, 70, "MR"], Cell[44234, 1731, 720, 22, 70, "Text"], Cell[44957, 1755, 48, 0, 70, "MR"], Cell[45008, 1757, 725, 22, 70, "Text"], Cell[45736, 1781, 314, 12, 70, "MR"], Cell[46053, 1795, 851, 26, 70, "Text"], Cell[46907, 1823, 44, 0, 70, "MR"], Cell[46954, 1825, 335, 10, 70, "Text"], Cell[47292, 1837, 311, 10, 70, "Text"], Cell[47606, 1849, 79, 1, 70, "Text"], Cell[47688, 1852, 75, 1, 70, "Text"], Cell[47766, 1855, 27, 0, 70, "Problem"], Cell[47796, 1857, 567, 19, 70, "Text"], Cell[48366, 1878, 19, 0, 70, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[48434, 1884, 63, 1, 47, "Section", CellTags->"c:18"], Cell[48500, 1887, 189, 4, 70, "Text"], Cell[48692, 1893, 110, 4, 70, "Input"], Cell[48805, 1899, 71, 3, 70, "Input"], Cell[48879, 1904, 1137, 34, 70, "Text"], Cell[50019, 1940, 139, 3, 70, "Text"], Cell[50161, 1945, 55, 0, 70, "Input"], Cell[50219, 1947, 57, 0, 70, "Input"], Cell[50279, 1949, 59, 0, 70, "Input"], Cell[50341, 1951, 262, 11, 70, "Text"], Cell[50606, 1964, 71, 3, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[50714, 1972, 95, 3, 47, "Section", Evaluatable->False, CellTags->"c:19"], Cell[CellGroupData[{ Cell[50834, 1979, 105, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:20"], Cell[50942, 1984, 461, 14, 70, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[51440, 2003, 103, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:21"], Cell[51546, 2008, 1424, 45, 70, "Text"], Cell[52973, 2055, 104, 3, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[53114, 2063, 110, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:22"], Cell[53227, 2068, 121, 2, 70, "Text", Evaluatable->False], Cell[53351, 2072, 229, 5, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[53617, 2082, 103, 3, 70, "Subsubsection", Evaluatable->False, CellTags->"c:23"], Cell[53723, 2087, 121, 2, 70, "Text", Evaluatable->False], Cell[53847, 2091, 260, 5, 70, "Input"] }, Closed]] }, Closed]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)