AOCP/Multisets - Revision history

Admin: Fix typos ("an umber" → "a number", "Tthe" → "The"), fix LaTeX double-factorial typo (k!! → k!), correct formula error ("exactly A columns" → "exactly A-m columns" for a/c form), and clarify Lilavati formula context (via update-page on MediaWiki MCP Server)

2026-06-09T05:00:10Z

Fix typos ("an umber" → "a number", "Tthe" → "The"), fix LaTeX double-factorial typo (k!! → k!), correct formula error ("exactly A columns" → "exactly A-m columns" for a/c form), and clarify Lilavati formula context (via update-page on MediaWiki MCP Server)

← Older revision		Revision as of 05:00, 9 June 2026
Line 39:		Line 39:
	First appearance of permutations of multisets were in 1150, ''Lilavati'' of Bhascara Acharya.		First appearance of permutations of multisets were in 1150, ''Lilavati'' of Bhascara Acharya.

	Interesting note: he gives the formula for the sum of the ~~permutations~~ of ~~this~~ multiset as:		Interesting note: he gives the formula for the sum of the numbers formed by permuting the digits of a multiset (for example, the digits 4, 8, 5, 5, 5) as:

	<math>		<math>
Line 90:		Line 90:
	</pre>		</pre>

	When we use this representation, we can turn each row (corresponding to each symbol a, b, c) into ~~an umber~~ of possible ways to permute that letter.		When we use this representation, we can turn each row (corresponding to each symbol a, b, c) into a number of possible ways to permute that letter.

	'''enumeration of a'''		'''enumeration of a'''
Line 144:		Line 144:
	'''enumeration of c'''		'''enumeration of c'''

	~~Tthe~~ remaining positions that are still vacant must be filled by c's,		The remaining positions that are still vacant must be filled by c's,

	<math>		<math>
Line 180:		Line 180:
	</math>		</math>

	Then it follows that there are exactly A columns of the form		Then it follows that there are exactly A-m columns of the form

	<pre>		<pre>
Line 201:		Line 201:
	</pre>		</pre>

	exactly C-A+m of the form		exactly C - A + m of the form

	<pre>		<pre>
Line 228:		Line 228:

	<math>		<math>
	N(A,B,C,m) = \sum_{k}{ \dfrac{(C+m-k)!}{ (m-k)!(C-A+m-k)!(C-B+m-k)!k!!(A+B-C-2m+k)!} }		N(A,B,C,m) = \sum_{k}{ \dfrac{(C+m-k)!}{ (m-k)!(C-A+m-k)!(C-B+m-k)! k! (A+B-C-2m+k)!} }
	</math>		</math>

Admin: /* Complicated Multiset Counting Example */

2019-02-23T18:27:24Z

Complicated Multiset Counting Example

← Older revision		Revision as of 18:27, 23 February 2019
Line 73:		Line 73:
	* B occurrences of b		* B occurrences of b
	* C occurrences of c		* C occurrences of c
	* k occurrences of adjacent pair ca		* k occurrences of adjacent pair ca or ac
	* l occurrences of adjacent pair cb		* l occurrences of adjacent pair cb or bc
	* m occurrences of adjacent pair ba		* m occurrences of adjacent pair ba or ab

	This can be thought of as two-line arrays of the form:		This can be thought of as two-line arrays of the form:

Admin: /* Complicated Multiset Example */

2019-02-23T18:25:32Z

Complicated Multiset Example

← Older revision		Revision as of 18:25, 23 February 2019
Line 67:		Line 67:
	</pre>		</pre>

	===Complicated Multiset Example===		===Complicated Multiset Counting Example===

	Suppose we have a string of characters a, b, c that has exactly:		Suppose we have a string of characters a, b, c that has exactly:

Admin: /* Multiset Example */

2018-01-08T08:02:22Z

Multiset Example

← Older revision		Revision as of 08:02, 8 January 2018
Line 67:		Line 67:
	</pre>		</pre>

	===Multiset Example===		===Complicated Multiset Example===

	Suppose we have a string of characters a, b, c that has exactly:		Suppose we have a string of characters a, b, c that has exactly:

Admin: /* Flags */

2017-07-24T08:13:15Z

Flags

← Older revision		Revision as of 08:13, 24 July 2017
Line 252:		Line 252:
	\sum_{t} \binom{D}{A-t} \binom{A+B+E+F}{t} \binom{A+B+C+E+F-t}{B} \binom{C+D+E+F}{C,D,E,F}		\sum_{t} \binom{D}{A-t} \binom{A+B+E+F}{t} \binom{A+B+C+E+F-t}{B} \binom{C+D+E+F}{C,D,E,F}
	</math>		</math>

			=Related=

			[[AOCP/Binomial Coefficients]]

			[[AOCP/Multinomial Coefficients]]

	=Flags=		=Flags=

Admin at 08:12, 24 July 2017

2017-07-24T08:12:51Z

← Older revision		Revision as of 08:12, 24 July 2017
Line 256:		Line 256:

	{{AOCPFlag}}		{{AOCPFlag}}

			[[Category:Binomial]]
			[[Category:Multinomial]]
			[[Category:Hypergeometric]]
			[[Category:Combinatorics]]

Admin: /* Chapter 5: Combinatorics */

2017-07-20T07:05:40Z

Chapter 5: Combinatorics

← Older revision		Revision as of 07:05, 20 July 2017
Line 29:		Line 29:
	See [[AOCP/Binomial Coefficients]] and [[AOCP/Multinomial Coefficients]].		See [[AOCP/Binomial Coefficients]] and [[AOCP/Multinomial Coefficients]].

	Knuth notes that these were known in ancient times: "The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says 'Go on and obtain numbers which the mount cannot express and the ear cannot hear.'"		Knuth notes that these were known in ancient times:

	First appearance of permutations of multisets ~~appeared~~ in 1150, ''Lilavati'' of Bhascara Acharya.		{{Quote\|
			The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says "Go on and obtain numbers which the mount cannot express and the ear cannot hear."

			- Knuth, AOCP V3 Section 5.1
			}}

			First appearance of permutations of multisets were in 1150, ''Lilavati'' of Bhascara Acharya.

	Interesting note: he gives the formula for the sum of the permutations of this multiset as:		Interesting note: he gives the formula for the sum of the permutations of this multiset as:
Line 246:		Line 252:
	\sum_{t} \binom{D}{A-t} \binom{A+B+E+F}{t} \binom{A+B+C+E+F-t}{B} \binom{C+D+E+F}{C,D,E,F}		\sum_{t} \binom{D}{A-t} \binom{A+B+E+F}{t} \binom{A+B+C+E+F-t}{B} \binom{C+D+E+F}{C,D,E,F}
	</math>		</math>






	=Flags=		=Flags=

	{{AOCPFlag}}		{{AOCPFlag}}

Admin: /* Multiset Permutations */

2017-07-20T07:04:41Z

Multiset Permutations

← Older revision		Revision as of 07:04, 20 July 2017
Line 27:		Line 27:
	</math>		</math>

	See [[AOCP/Binomial]] and [[AOCP/Multinomial]].		See [[AOCP/Binomial Coefficients]] and [[AOCP/Multinomial Coefficients]].

	Knuth notes that these were known in ancient times: "The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says 'Go on and obtain numbers which the mount cannot express and the ear cannot hear.'"		Knuth notes that these were known in ancient times: "The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says 'Go on and obtain numbers which the mount cannot express and the ear cannot hear.'"

Admin: /* Multiset Permutations */

2017-07-20T07:04:14Z

Multiset Permutations

← Older revision		Revision as of 07:04, 20 July 2017
Line 26:		Line 26:
	\binom{n}{n_1, n_2, \dots} = \dfrac{n!}{n_1! n_2! \dots}		\binom{n}{n_1, n_2, \dots} = \dfrac{n!}{n_1! n_2! \dots}
	</math>		</math>

			See [[AOCP/Binomial]] and [[AOCP/Multinomial]].

	Knuth notes that these were known in ancient times: "The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says 'Go on and obtain numbers which the mount cannot express and the ear cannot hear.'"		Knuth notes that these were known in ancient times: "The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says 'Go on and obtain numbers which the mount cannot express and the ear cannot hear.'"

Admin: Created page with "=Volume 3= ==Chapter 5: Combinatorics== ===Multiset Permutations=== Suppose we have a multiset $M = \{ a, a, a, b, b, c, d, d, d, d\} = \{ 3 \cdot a, 2 \cdot b, c, 4..."$

2017-07-20T04:20:19Z

Created page with "=Volume 3= ==Chapter 5: Combinatorics== ===Multiset Permutations=== Suppose we have a multiset <math> M = \{ a, a, a, b, b, c, d, d, d, d\} = \{ 3 \cdot a, 2 \cdot b, c, 4..."

New page

=Volume 3=

==Chapter 5: Combinatorics==

===Multiset Permutations===

Suppose we have a multiset

<math>
M = \{ a, a, a, b, b, c, d, d, d, d\} = \{ 3 \cdot a, 2 \cdot b, c, 4 \cdot d \}
</math>

and we wish to determine the number of permutations of this multiset into words of the form "aaabbcdddd".

If each character were distinct, we have 10 characters, so there would be 10! configurations. But many of these are duplicated. To be more precise, for the case of a, where there are 3 a's, there will be exactly 3! configurations that are duplicates. So, we can eliminate these by dividing 10! by 3!. Next, for b, there will be exactly 2! configurations that are duplicates. And so on.

Then we can determine the number of permutations of M via:

<math>
N_{perm} = \dfrac{10!}{3! 2! 1! 4!}
</math>

In general, the number of permutations of a multiset is the ''multinomial coefficient'' defined as

<math>
\binom{n}{n_1, n_2, \dots} = \dfrac{n!}{n_1! n_2! \dots}
</math>

Knuth notes that these were known in ancient times: "The Hebrew Book of Creation (300 AD), which was the earliest literary product of Jewish philosophical mysticism, gives the correct values of the first seven factorials, after which it says 'Go on and obtain numbers which the mount cannot express and the ear cannot hear.'"

First appearance of permutations of multisets appeared in 1150, ''Lilavati'' of Bhascara Acharya.

Interesting note: he gives the formula for the sum of the permutations of this multiset as:

<math>
\dfrac{(4+8+5+5+5) \cdot 120 \cdot 11111}{5 \cdot 6} = 48555 + 45885 + \dots
</math>

Foata (1969) provided an extension called the "intercalation product" that makes it possible to extend ideas and results from sets to multisets fairly easily.

First, assume the elements of the multiset are ordered in some way. Now consider the two-line notation:
* The top line will contain the elements of M in non-decreasing order
* The bottom line will contain the permutation itself

The intercalation product a T b of the top and bottom lines is done by expressing a and b in the two-line notation, then sorting columns into STABLE, non-decreasing order of the top line. Stable means, if there is a tie on the top line, break the tie using the original left-to-right order of the bottom row.

Example: the intercalation of these two multisets <code>c a d a b</code> and <code>b d d a d</code> would be:

<pre>
a a b c d
c a d a b

a b d d d
b d d a d

Intercalation:
a a a b b c d d d d
c a b d d a b d a d
</pre>

===Multiset Example===

Suppose we have a string of characters a, b, c that has exactly:
* A occurrences of a
* B occurrences of b
* C occurrences of c
* k occurrences of adjacent pair ca
* l occurrences of adjacent pair cb
* m occurrences of adjacent pair ba

This can be thought of as two-line arrays of the form:

<pre>
A B C
a ... a b ... b c ... c
\______/ \______/ \_______/
(A - k - m) a's (m a's) (k a's)
\_____________________________/ \______/
(B - l) b's (l b's)
\_________________________________________________/
C c's
</pre>

When we use this representation, we can turn each row (corresponding to each symbol a, b, c) into an umber of possible ways to permute that letter.

'''enumeration of a'''

In the second line, the a's are enumerated as the product of three terms;

The first term represents the number of ways that we can distribute A a's among (A - k - m) positions (the positions in which we are free to select what comes after a):

<math>
\binom{A}{A-k-m}
</math>

The second term represents our choice of B b's to place in m slots (next to m a's, for the m 'ab' combinations):

<math>
\binom{B}{m}
</math>

The third term comes from our choice of C c's to place in k slots (next to k a's, for the k 'ac' combinations):

<math>
\binom{C}{k}
</math>

This gives the total number of possibilities for A:

<math>
\binom{A}{A-k-m} \binom{B}{m} \binom{C}{k}
</math>

'''enumeration of b'''

In the third row, the b's can be placed in the remaining positions as our choice of placing B b's plus k combinations "ac" into B-l slots:

<math>
\binom{B+k}{B-l}
</math>

(This is a little magical - I would have used B in the top, not B+k. Not sure how we know to do that, since Knuth does not explain.)

Next, we have a term representing our choice of C-k remaining c characters to couple with b characters to form l pairs of 'bc' combinations:

<math>
\binom{C-k}{l}
</math>

This brings the enumeration of ways to arrange the bs to:

<math>
\binom{B+k}{B-l} \binom{C-k}{l}
</math>

'''enumeration of c'''

Tthe remaining positions that are still vacant must be filled by c's,

<math>
\binom{C}{k}
</math>

(Again, some magic happening here - why does Knuth use C, instead of (C - k - l)?

'''total enumerations'''

This gives the total number of arrangements:

<math>
\binom{A}{A-k-m} \binom{B}{m} \binom{C}{k} \binom{B+k}{B-l} \binom{C-k}{l}
</math>

===Another Multiset Example===

Let's look at another multiset example.

Suppose we have a multiset <math>M = \{ A \cdot a, B \cdot b, C \cdot c \}</math>.

Now let <math>N(A, B, C, m)</math> denote the number of permutations of M whose two-line representations contain NO columns of the form

<pre>
a b c
a b c
</pre>

and contains exactly m columns of the form

<math>
a
b
</math>

Then it follows that there are exactly A columns of the form

<pre>
a
c
</pre>

exactly B-m columns of the form

<pre>
c
b
</pre>

exactly C - B + m of the form

<pre>
c
a
</pre>

exactly C-A+m of the form

<pre>
b
c
</pre>

and exactly A + B - C - m of the form

<pre>
b
a
</pre>

Combining these facts, we get:

<math>
N(A,B,C,m) = \binom{A}{m} \binom{B}{C-A+m} \binom{C}{B-m}
</math>

Now, we can count these permutations in another way: since we have excluded columns where the two rows are identical, the only possible prime factors of the permutation are (a b), (a c), (b c), (a b c), (a c b). These each have one letter in common, so the factorization is unique.

Therefore, if the cycle (a b c) occurs k times in the factorization, this implies that (a b) occurs m-k times, (b c) occurs C - A + m - k times, (a c) occurs C - B + m - k times, and (a c b) occurs A + B - C - 2m + k times.

This allows us to put <math>N(A,B,C,m)</math> in terms of a multinomial coefficient:

<math>
N(A,B,C,m) = \sum_{k}{ \dfrac{(C+m-k)!}{ (m-k)!(C-A+m-k)!(C-B+m-k)!k!!(A+B-C-2m+k)!} }
</math>

and this simplifies to

<math>
N(A,B,C,m) = \sum_{k}{ \binom{m}{k} \binom{A}{m} \binom{A-m}{C-B+m-k} \binom{C+m-k}{A} }
</math>

From this, Knuth begins to do a bunch of manipulation of binomial coefficients. Specifically, he mentions the following identity:

<math>
\sum_{j} \binom{M-R+S}{j} \binom{N+R-S}{N-j} \binom{R+j}{M+N} = \binom{R}{M} \binom{S}{N}
</math>

with <math>M = A+B-C-m, N = C-B+m, R = B, S = C, j = C - B + m - k</math>.

===Third Example===

Exercise 13 (rated M21), Section 5.1.2 (Permutations of a Multiset), states: Prove that the number of permutations of <math>M = \{ A \cdot a, B \cdot b, C \cdot c, D \cdot d, E \cdot e, F \cdot f \}</math> containing no occurrences of the adjacent pairs of letters 'ca' and 'db' is:

<math>
\sum_{t} \binom{D}{A-t} \binom{A+B+E+F}{t} \binom{A+B+C+E+F-t}{B} \binom{C+D+E+F}{C,D,E,F}
</math>

=Flags=

{{AOCPFlag}}

AOCP/Multisets - Revision history

Admin: Fix typos ("an umber" → "a number", "Tthe" → "The"), fix LaTeX double-factorial typo (k!! → k!), correct formula error ("exactly A columns" → "exactly A-m columns" for a/c form), and clarify Lilavati formula context (via update-page on MediaWiki MCP Server)

Admin: /* Complicated Multiset Counting Example */

Admin: /* Complicated Multiset Example */

Admin: /* Multiset Example */

Admin: /* Flags */

Admin at 08:12, 24 July 2017

Admin: /* Chapter 5: Combinatorics */

Admin: /* Multiset Permutations */

Admin: /* Multiset Permutations */

Admin: Created page with "=Volume 3= ==Chapter 5: Combinatorics== ===Multiset Permutations=== Suppose we have a multiset M = \{ a, a, a, b, b, c, d, d, d, d\} = \{ 3 \cdot a, 2 \cdot b, c, 4..."

Admin: Created page with "=Volume 3= ==Chapter 5: Combinatorics== ===Multiset Permutations=== Suppose we have a multiset $M = \{ a, a, a, b, b, c, d, d, d, d\} = \{ 3 \cdot a, 2 \cdot b, c, 4..."$