AOCP/Permutations - Revision history

Admin: Fix LaTeX/math syntax errors: (1) replaced broken `&=&` align syntax with proper `&=` alignment, (2) replaced `&\quad&` align with cleaner `\begin{array}{ll}`, (3) added missing floor(1000/729) term to match the 6-term sum, (4) changed `\mbox{floor}` to `\operatorname{floor}` for proper math-operator spacing (via update-page on MediaWiki MCP Server)

2026-06-14T22:56:37Z

Fix LaTeX/math syntax errors: (1) replaced broken `&=&` align syntax with proper `&=` alignment, (2) replaced `&\quad&` align with cleaner `\begin{array}{ll}`, (3) added missing floor(1000/729) term to match the 6-term sum, (4) changed `\mbox{floor}` to `\operatorname{floor}` for proper math-operator spacing (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 22:56, 14 June 2026
Line 46:		Line 46:

	<math>		<math>
	\begin{~~align~~}		\begin{array}{ll}
	a_1 a_2 \dots a_{n-1} ~~&\quad~~& \frac{1}{2} \\		a_1 a_2 \dots a_{n-1} & \frac{1}{2} \\
	a_1 a_2 \dots a_{n-1} ~~&\quad~~& \frac{3}{2} \\		a_1 a_2 \dots a_{n-1} & \frac{3}{2} \\
	&\dots& \\		\dots & \dots \\
	a_1 a_2 \dots a_{n-1} ~~&\quad~~& (n - \frac{1}{2})		a_1 a_2 \dots a_{n-1} & (n - \frac{1}{2})
	\end{~~align~~}		\end{array}
	</math>		</math>

Line 102:		Line 102:
	<math>		<math>
	\begin{align}		\begin{align}
	\mu &=& \~~mbox~~{floor}(\frac{n}{p}) + \~~mbox~~{floor}(\frac{n}{p^2}) + \~~mbox~~{floor}(\frac{n}{p^3}) + \dots \\		\mu &= \operatorname{floor}\left(\frac{n}{p}\right) + \operatorname{floor}\left(\frac{n}{p^2}\right) + \operatorname{floor}\left(\frac{n}{p^3}\right) + \dots \\
	&=& \sum_{k>0} \~~mbox~~{floor}(\frac{n}{p^k})		&= \sum_{k>0} \operatorname{floor}\left(\frac{n}{p^k}\right)
	\end{align}		\end{align}
	</math>		</math>
Line 110:		Line 110:

	<math>		<math>
	\mu = \~~mbox~~{floor}(\frac{1000}{3}) + \~~mbox~~{floor}(\frac{1000}{9}) + \~~mbox~~{floor}(\frac{1000}{27}) + \~~mbox~~{floor}(\frac{1000}{81}) + \~~mbox~~{floor}(\frac{1000}{243})		\mu = \operatorname{floor}\left(\frac{1000}{3}\right) + \operatorname{floor}\left(\frac{1000}{9}\right) + \operatorname{floor}\left(\frac{1000}{27}\right) + \operatorname{floor}\left(\frac{1000}{81}\right) + \operatorname{floor}\left(\frac{1000}{243}\right) + \operatorname{floor}\left(\frac{1000}{729}\right)
	</math>		</math>

Line 124:		Line 124:

	<math>		<math>
	\~~mbox~~{floor}\left(\frac{n}{p^{k+1}} \right) = \~~mbox~~{floor}\left( \frac{\~~mbox~~{floor}( \frac{n}{p^k} )}{p} \right)		\operatorname{floor}\left(\frac{n}{p^{k+1}} \right) = \operatorname{floor}\left( \frac{\operatorname{floor}\left( \frac{n}{p^k} \right)}{p} \right)
	</math>		</math>

Admin: /* Multinomial Coefficients */

2017-07-20T09:36:33Z

Multinomial Coefficients

← Older revision		Revision as of 09:36, 20 July 2017
Line 134:		Line 134:

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

			===Generating Functions===

			See [[AOCP/Generating Functions]]

	=Flags=		=Flags=

Admin: /* Flags */

2017-07-20T09:26:48Z

Flags

← Older revision		Revision as of 09:26, 20 July 2017
Line 146:		Line 146:
	[[Category:Algorithms]]		[[Category:Algorithms]]
	[[Category:Reading]]		[[Category:Reading]]
			[[Category:Sequences]]

Admin: /* Binomial Coefficients */

2017-07-20T06:48:01Z

Binomial Coefficients

← Older revision		Revision as of 06:48, 20 July 2017
Line 130:		Line 130:

	See [[AOCP/Binomial Coefficients]]		See [[AOCP/Binomial Coefficients]]

			===Multinomial Coefficients===

			See [[AOCP/Multinomial Coefficients]]

	=Flags=		=Flags=

Admin: /* Binomial Coefficients */

2017-07-20T06:47:40Z

Binomial Coefficients

Show changes

Admin: /* Sums of Products */

2017-07-20T06:32:20Z

Sums of Products

← Older revision		Revision as of 06:32, 20 July 2017
Line 371:		Line 371:

	<math>		<math>
	\sum_{k} \binom{r}{k} \binom{s}{n+k} = \binom{r+s}{r+n} \qquad r, n \in \mathbb{Z}, r \eq 0		\sum_{k} \binom{r}{k} \binom{s}{n+k} = \binom{r+s}{r+n} \qquad r, n \in \mathbb{Z}, r \neq 0
	</math>		</math>

Admin: /* Sums of Products */

2017-07-20T06:30:03Z

Sums of Products

← Older revision		Revision as of 06:30, 20 July 2017
Line 355:		Line 355:

	====Sums of Products====		====Sums of Products====

			If we need to sum over the products of binomial coefficients, we have several identities, of which the most important is:

			<math>
			\sum_k \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}
			</math>

			This should be memorized. Interpret the right hand side as the number of ways to select n people from among r men and s women.

			Each term on the left side is a number of ways to choose k of the men and n-k of the women.

			Vandermonde's convolution - published by Vandermonde in 1772.

			Further identities:

			<math>
			\sum_{k} \binom{r}{k} \binom{s}{n+k} = \binom{r+s}{r+n} \qquad r, n \in \mathbb{Z}, r \eq 0
			</math>

			<math>
			\sum_{k} \binom{r}{k} \binom{s+k}{n} (-1)^k = (-1)^r \binom{s}{n-r} \qquad n, r \in \mathbb{Z}, r \geq 0
			</math>

	=Flags=		=Flags=

Admin: /* Simplifying Products */

2017-07-20T06:25:02Z

Simplifying Products

← Older revision		Revision as of 06:25, 20 July 2017
Line 351:		Line 351:

	<math>		<math>
	\binom{r}{m}{m}{k} = \binom{r}{k} \binom{r-k}{m-k}		\binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}
	</math>		</math>

Admin: /* Simplifying Products */

2017-07-20T06:24:44Z

Simplifying Products

← Older revision		Revision as of 06:24, 20 July 2017
Line 345:		Line 345:
	\binom{r}{m}{m}{k} &=& \dfrac{r! m!}{ m! (r-m)! k! (m-k)! } \\		\binom{r}{m}{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}
	</math>		</math>

Admin: /* Simplifying Products */

2017-07-20T06:24:19Z

Simplifying Products

← Older revision		Revision as of 06:24, 20 July 2017
Line 338:		Line 338:

	This holds for integer m and integer k.		This holds for integer m and integer k.

			If we know <math>r \geq m, 0 \leq k \leq m</math>, then the following identity holds:

			<math>
			\begin{align}
			\binom{r}{m}{m}{k} &=& \dfrac{r! m!}{ m! (r-m)! k! (m-k)! } \\
			&=& \dfrac{r!(r-k)!}{k!(r-k)! (m-k)! (r-m)!}
			</math>

			all of which leads to:

			<math>
			\binom{r}{m}{m}{k} = \binom{r}{k} \binom{r-k}{m-k}
			</math>

			====Sums of Products====

	=Flags=		=Flags=