AOCP/Binomial Coefficients - Revision history

Admin: Fix mathematical errors and typos: (1) Binomial theorem: fix (x+y)^n → (x+y)^r; fix "caes" → "case"; fix |x|<0 → |x|<1. (2) Problem 36: fix incorrect claim that C(n, n-1)=2 (it equals n); fix algebraic error 2(2^n-1) → 2(2^{n-1}-1); add alternating signs solution. (3) Sum of Sequence: fix same algebraic error; replace sloppy sum-over-fractions derivation with symmetry argument. (4) Fix "Rleated" → "Related". (5) Zeta: fix n(n+1)/2 → n(n-1)/2. (via update-page on MediaWiki MCP Server)

2026-06-20T04:35:07Z

Fix mathematical errors and typos: (1) Binomial theorem: fix (x+y)^n → (x+y)^r; fix "caes" → "case"; fix |x|<0 → |x|<1. (2) Problem 36: fix incorrect claim that C(n, n-1)=2 (it equals n); fix algebraic error 2(2^n-1) → 2(2^{n-1}-1); add alternating signs solution. (3) Sum of Sequence: fix same algebraic error; replace sloppy sum-over-fractions derivation with symmetry argument. (4) Fix "Rleated" → "Related". (5) Zeta: fix n(n+1)/2 → n(n-1)/2. (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 04:35, 20 June 2026
Line 32:		Line 32:
	* Summation formulas		* Summation formulas
	* Binomial theorem		* Binomial theorem
	* ~~negating~~ upper index		* Negating upper index
	* Sums of products		* Sums of products

Line 146:		Line 146:

	<math>		<math>
	\left( x + y \right)^n = \sum_{0 \leq k \leq r} \binom{r}{k} x^k y^{r-k}		\left( x + y \right)^r = \sum_{0 \leq k \leq r} \binom{r}{k} x^k y^{r-k}
	</math>		</math>

Line 159:		Line 159:
	since if k < 0 or k > r the expressions go to zero.		since if k < 0 or k > r the expressions go to zero.

	The ~~caes~~ of y = 1 is:		The case of y = 1 is:

	<math>		<math>
Line 165:		Line 165:
	</math>		</math>

	for integer r >= 0 or \|x\| < 0		for integer r >= 0 or \|x\| < 1

	Isaac Newton discovered the binomial theorem in 1676. First attempted proof was by Euler in 1774. Gauss gave first actual proof in 1812.		Isaac Newton discovered the binomial theorem in 1676. First attempted proof was by Euler in 1774. Gauss gave first actual proof in 1812.
Line 278:		Line 278:
	</math>		</math>

	Furthermore, we know that <math>\binom{n}{n-1}</math> ~~can only be 2 (if we have 10 slots and 9 items, there are only 2 configurations possible)~~. Thus, if we see sums that are missing ~~one term~~, such as		Furthermore, we know that <math>\binom{n}{n} = 1</math> and <math>\binom{n}{0} = 1</math>. Thus, if we see sums that are missing these two terms, such as

	<math>		<math>
Line 284:		Line 284:
	</math>		</math>

	we can use the properties of series~~, and the numerical value of the last coefficient,~~ to write:		we can use the properties of series to write:

	<math>		<math>
	\sum_{k=1}^{n-1} \binom{n}{k} = \sum_{k=1}^{n} \binom{n}{k} - 2 = 2^n - 2 = 2(2^n-1)		\sum_{k=1}^{n-1} \binom{n}{k} = \sum_{k=0}^{n} \binom{n}{k} - \binom{n}{0} - \binom{n}{n} = 2^n - 1 - 1 = 2^n - 2 = 2(2^{n-1} - 1)
	</math>		</math>

	See the [[#Sum of Sequence]] problem below~~, where we use this fact to address the alternating signs part of the question~~.		For the alternating signs part, we note that <math>\sum_k \binom{n}{k} (-1)^k = (1-1)^n = 0^n = 0</math> for n > 0, or 1 for n = 0.

			See the [[#Sum of Sequence]] problem below.

	==The Zeta Family==		==The Zeta Family==
Line 309:		Line 311:

	<math>		<math>
	\binom{25}{2} = \dfrac{25!}{23! 2!} = \dfrac{25 \times 24}{2} = \dfrac{n(n+1)}{2}		\binom{25}{2} = \dfrac{25!}{23! 2!} = \dfrac{25 \times 24}{2} = \dfrac{n(n-1)}{2}
	</math>		</math>

	This is the sum of all of the integers from 1 to n.		This is the sum of all of the integers from 1 to n-1 (with n=25).

	This solution to the problem can be interpreted as follows: for our first choice of letter, we have 25 possible choices. For our choice of second letter, it depends on our first choice. If we choose A, we have 24 remaining choices. If we choose B, we have 23 remaining choices. If we choose C, we have 22 remaining choices. And so on.		This solution to the problem can be interpreted as follows: for our first choice of letter, we have 25 possible choices. For our choice of second letter, it depends on our first choice. If we choose A, we have 24 remaining choices. If we choose B, we have 23 remaining choices. If we choose C, we have 22 remaining choices. And so on.
Line 338:		Line 340:
	We use a trick to show if the sequence has an odd number of odd terms:		We use a trick to show if the sequence has an odd number of odd terms:

	Sum up all terms in the sequence. If the entire sequence is odd, then we know the sequence must have an odd number of odd terms.		Sum up all terms in the sequence. If the entire sequence sum is odd, then we know the sequence must have an odd number of odd terms.

	Summing the sequence:		Summing the sequence:
Line 346:		Line 348:
	</math>		</math>

	Now, ~~through a change~~ of ~~variables in~~ the ~~summation, we can write this as~~:		Now, by the symmetry of binomial coefficients <math>\binom{n}{k} = \binom{n}{n-k}</math>, for odd n the terms from k=1 to <math>\frac{n-1}{2}</math> pair exactly with terms from <math>\frac{n+1}{2}</math> to n-1. Therefore the sum of the first half equals half the sum from k=1 to n-1:

	<math>		<math>
	\sum_{k=1}^{n-1} \binom{n}~~{\frac~~{k~~}{2}~~} = \dfrac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k}		\sum_{k=1}^{\frac{n-1}{2}} \binom{n}{k} = \dfrac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k}
	</math>		</math>

Line 359:		Line 361:

	<math>		<math>
	\sum_{k=1}^{n-1} \binom{n}{k} = \~~sum_~~{~~k=1~~}^{n} \binom{n}{k} ~~- 2~~ = 2^n - 2 = 2(2^n-1)		\sum_{k=1}^{n-1} \binom{n}{k} = 2^n - \binom{n}{0} - \binom{n}{n} = 2^n - 1 - 1 = 2^n - 2
	</math>		</math>

	to write the entire sequence as		to write the entire sequence sum as

	<math>		<math>
Line 370:		Line 372:
	This is indeed an odd number, so the statement is proven.		This is indeed an odd number, so the statement is proven.

	=~~Rleated~~=		=Related=

	[[Cards]] - probabilities of outcomes for playing cards		[[Cards]] - probabilities of outcomes for playing cards

Admin: Fix math syntax errors: lowercase Math tag, fix \binom with 4 args to two separate \binom calls, fix &=& to &= in align, fix \sum{k to \sum_{k (via update-page on MediaWiki MCP Server)

2026-06-06T00:46:29Z

Fix math syntax errors: lowercase Math tag, fix \binom with 4 args to two separate \binom calls, fix &=& to &= in align, fix \sum{k to \sum_{k (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 00:46, 6 June 2026
Line 161:		Line 161:
	The caes of y = 1 is:		The caes of y = 1 is:

	<~~Math~~>		<math>
	\sum_k \binom{r}{k} x^k = \left( 1 + x \right)^r		\sum_k \binom{r}{k} x^k = \left( 1 + x \right)^r
	</math>		</math>
Line 219:		Line 219:
	<math>		<math>
	\begin{align}		\begin{align}
	\binom{r}{m}{m}{k} &=& \dfrac{r! m!}{ m! (r-m)! k! (m-k)! } \\		\binom{r}{m} \binom{m}{k} &= \dfrac{r! m!}{ m! (r-m)! k! (m-k)! } \\
	&=& \dfrac{r!(r-k)!}{k!(r-k)! (m-k)! (r-m)!}		&= \dfrac{r!(r-k)!}{k!(r-k)! (m-k)! (r-m)!}
	\end{align}		\end{align}
	</math>		</math>
Line 349:		Line 349:

	<math>		<math>
	\sum_{k=1}^{n-1} \binom{n}{\frac{k}{2}} = \dfrac{1}{2} \~~sum~~{k=1}^{n-1} \binom{n}{k}		\sum_{k=1}^{n-1} \binom{n}{\frac{k}{2}} = \dfrac{1}{2} \sum_{k=1}^{n-1} \binom{n}{k}
	</math>		</math>

Admin: /* Knuth AOCP Section 1.2.5 Problem 36 */

2019-02-23T18:23:14Z

Knuth AOCP Section 1.2.5 Problem 36

← Older revision		Revision as of 18:23, 23 February 2019
Line 290:		Line 290:
	</math>		</math>

	~~We will~~ use this fact ~~in a later problem~~.		See the [[#Sum of Sequence]] problem below, where we use this fact to address the alternating signs part of the question.

	==The Zeta Family==		==The Zeta Family==

Admin: /* Solution using binomial coefficient properties */

2019-02-23T18:21:36Z

Solution using binomial coefficient properties

← Older revision		Revision as of 18:21, 23 February 2019
Line 336:		Line 336:
	The solution given here uses a few binomial coefficient properties not covered by Knuth, plus a few that Knuth covered in the exercise.		The solution given here uses a few binomial coefficient properties not covered by Knuth, plus a few that Knuth covered in the exercise.

	~~Start with~~ the ~~sum of the members~~ of the sequence~~: if we can show that the sum of~~ the entire sequence is odd, then we know ~~there~~ must be an odd number of ~~numbers in the sequence~~.		We use a trick to show if the sequence has an odd number of odd terms:

			Sum up all terms in the sequence. If the entire sequence is odd, then we know the sequence must have an odd number of odd terms.

	Summing the sequence:		Summing the sequence:

Admin: /* Solution using binomial coefficient */

2019-02-23T18:17:52Z

Solution using binomial coefficient

← Older revision		Revision as of 18:17, 23 February 2019
Line 312:		Line 312:
	</math>		</math>

	This is the sum of all of the integers from 1 to n. This solution to the problem can be interpreted as follows: for our first choice of letter, we have 25 possible choices. For our choice of second letter, it depends on our first choice. If we choose A, we have 24 remaining choices. If we choose B, we have 23 remaining choices. If we sum up all possible choices, we get		This is the sum of all of the integers from 1 to n.

			This solution to the problem can be interpreted as follows: for our first choice of letter, we have 25 possible choices. For our choice of second letter, it depends on our first choice. If we choose A, we have 24 remaining choices. If we choose B, we have 23 remaining choices. If we choose C, we have 22 remaining choices. And so on.

			If we sum up all of our possible choices, we get

	<math>		<math>
	24 + 23 + 22 + \dots + 1 = \dfrac{24 (24+1)}{2} = \dfrac{600}{2} = 300		24 + 23 + 22 + \dots + 1 = \dfrac{24 (24+1)}{2} = \dfrac{600}{2} = 300
	</math>		</math>

			300 possible choices of monogram.

	==Sum of Sequence==		==Sum of Sequence==

Admin: /* Summation formulas */

2019-02-22T19:20:04Z

Summation formulas

← Older revision		Revision as of 19:20, 22 February 2019
Line 110:		Line 110:

	<math>		<math>
	\sum_{0 \leq k \leq m} \binom{k}{m} = \binom{0}{m} + \binom{1}{m} + \dots + \binom{n}{m} = \binom{n+1}{m+1}		\sum_{0 \leq k \leq n} \binom{k}{m} = \binom{0}{m} + \binom{1}{m} + \dots + \binom{n}{m} = \binom{n+1}{m+1}
	</math>		</math>

Admin: /* Rleated */

2017-07-24T10:09:16Z

Rleated

← Older revision		Revision as of 10:09, 24 July 2017
Line 363:		Line 363:

	=Rleated=		=Rleated=

			[[Cards]] - probabilities of outcomes for playing cards

	[[AOCP/Multinomial Coefficients]]		[[AOCP/Multinomial Coefficients]]

Admin: /* Flags */

2017-07-24T08:14:53Z

Flags

← Older revision		Revision as of 08:14, 24 July 2017
Line 361:		Line 361:

	This is indeed an odd number, so the statement is proven.		This is indeed an odd number, so the statement is proven.

			=Rleated=

			[[AOCP/Multinomial Coefficients]]

			[[AOCP/Multisets]]

	=Flags=		=Flags=

Admin at 08:11, 24 July 2017

2017-07-24T08:11:14Z

← Older revision		Revision as of 08:11, 24 July 2017
Line 370:		Line 370:
	[[Category:AOCP]]		[[Category:AOCP]]
	[[Category:Algorithms]]		[[Category:Algorithms]]
			[[Category:Combinatorics]]
			[[Category:Binomial]]

Admin: /* Flags */

2017-07-22T00:03:57Z

Flags

← Older revision		Revision as of 00:03, 22 July 2017
Line 366:		Line 366:
	{{AOCPFlag}}		{{AOCPFlag}}

	{{~~Algorithms~~}}		{{AlgorithmsFlag}}

	[[Category:AOCP]]		[[Category:AOCP]]
	[[Category:Algorithms]]		[[Category:Algorithms]]