ExampleConstruction: AI-adaptedVerification: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Arrangements of a word with repeated letters, counted by the multinomial coefficient

Example

Take the eleven-letter word $M I S S I S S I P P I$ , over the four-letter alphabet ${M, I, S, P}$ , in which $M$ occurs once, $I$ four times, $S$ four times and $P$ twice. The number of distinct arrangements of its letters is

$(\binom{11}{1, 4, 4, 2}) = \frac{11!}{1! 4! 4! 2!} = \frac{39916800}{1152} = 34650.$

The modelling step is the mathematics. An arrangement is a function from the set of eleven positions to the four-letter alphabet whose fibre over each letter has the prescribed size; that is literally an element of $B (A, k)$ in The multinomial coefficient $(\binom{n}{k_{0}, \dots, k_{m - 1}})$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes, with $A$ the set of positions, $m = 4$ and $k = (1, 4, 4, 2)$ .

Facts & Assumptions

Given: The position set $A$ with $∣ A ∣ = 11$ , the alphabet identified with $4 = {0, 1, 2, 3}$ by $0 \mapsto M$ , $1 \mapsto I$ , $2 \mapsto S$ , $3 \mapsto P$ , and the tuple $k = (1, 4, 4, 2)$ ; the factorials $1! = 1$ , $2! = 2$ , $4! = 24$ and $11! = 39916800$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[L1]

$B (A, k)$ is the set of $c : A \to m$ with $∣ c^{- 1} [{i}] ∣ = k_{i}$ for every $i < m$ ; it is nonempty only if $\sum_{i < m} k_{i} = ∣ A ∣$ , and its cardinality is $(\binom{∣ A ∣}{k})$ (The multinomial coefficient $(\binom{n}{k_{0}, \dots, k_{m - 1}})$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes, The cardinality $∣ A ∣$ of a finite set).

[L2]

$(\binom{n}{k}) \prod_{i < m} k_{i}! = n!$ (The multinomial coefficient equals $n! / \prod_{i < m} k_{i}!$ , and $(x_{0} + \dots + x_{m - 1})^{n} = \sum ι ⁣ (\binom{n}{k}) \prod_{i < m} x_{i}^{k_{i}}$ in $R$ , clause 1).

[L3]

Finite sums and products in $N$ and cancellation by a nonzero natural (Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ , Cancellation for multiplication by a nonzero factor).

Verification

technique · direct

1.1

The modelling. An arrangement of the letters of $M I S S I S S I P P I$ is a function $c$ assigning to each of the eleven positions one of the four letters, subject to the letter multiplicities; that is, $∣ c^{- 1} [{0}] ∣ = 1$ , $∣ c^{- 1} [{1}] ∣ = 4$ , $∣ c^{- 1} [{2}] ∣ = 4$ and $∣ c^{- 1} [{3}] ∣ = 2$ . So the set of arrangements is exactly $B (A, k)$ with $k = (1, 4, 4, 2)$ .

givenL1

2.1

The hypothesis is satisfied, and it must be checked before the coefficient is written down: $\sum_{i < 4} k_{i} = 1 + 4 + 4 + 2 = 11 = ∣ A ∣$ , so $k \in W (11, 4)$ and $(\binom{11}{1, 4, 4, 2})$ is defined.

step 1.1L1L3

3.1

The value. By [L2], $(\binom{11}{1, 4, 4, 2}) \cdot (1! \cdot 4! \cdot 4! \cdot 2!) = 11!$ , that is $(\binom{11}{1, 4, 4, 2}) \cdot (1 \cdot 24 \cdot 24 \cdot 2) = 39916800$ ; the product of factorials is $1152$ , and $1152 \cdot 34650 = 39916800$ , so cancellation by the nonzero factor $1152$ gives $(\binom{11}{1, 4, 4, 2}) = 34650$ .

step 2.1L2L3

4.1

Hence the word has exactly $34650$ distinct arrangements, this being $∣ B (A, k) ∣$ by [L1].

step 1.1step 3.1L1∎

Remarks

Why the letters are identified with ${0, 1, 2, 3}$ . The multinomial coefficient $(\binom{n}{k_{0}, \dots, k_{m - 1}})$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes takes the colour set to be a natural number, so the alphabet has to be presented as one; any bijection will do, and the count does not depend on which. A different identification permutes the tuple $k$ , and by clause 1 of The multinomial coefficient equals $n! / \prod_{i < m} k_{i}!$ , and $(x_{0} + \dots + x_{m - 1})^{n} = \sum ι ⁣ (\binom{n}{k}) \prod_{i < m} x_{i}^{k_{i}}$ in $R$ the coefficient is determined by $n$ together with the product $\prod_{i < m} k_{i}!$ , which a permutation of the parts leaves unchanged. The invariance clause of The multinomial coefficient $(\binom{n}{k_{0}, \dots, k_{m - 1}})$ as the number of ordered partitions of an $n$ -set into blocks of prescribed sizes is a different statement: it says the count depends only on $∣ A ∣$ , that is, only on the domain up to bijection.
The check in step 2.1 is not a formality. If the multiplicities did not sum to the length, $B (A, k)$ would be empty and the symbol $(\binom{11}{k})$ would not be defined at all.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

41 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Anagram (Wikipedia) (standard reference, not scraped)
Multinomial theorem (Wikipedia) (standard reference, not scraped)
Permutation (Wikipedia) (standard reference, not scraped)