TheoremBase

Multinomial Coefficients: Binomial Products and Counting

A multinomial coefficient with one more entry is the previous one times a binomial coefficient, with two entries it is a binomial coefficient, and it counts the maps from [n] to [m] with prescribed fibre sizes.

Statement

In the setting of Finite Combinatorics: Notation, let m∈Nm\in\mathbb{N} and k1,…,km∈N0k_{1},\dots,k_{m}\in\mathbb{N}_{0}.

Adding an entry. For every km+1∈N0k_{m+1}\in\mathbb{N}_{0},

(k1+⋯+km+1k1,…,km+1)=(k1+⋯+kmk1,…,km)(k1+⋯+km+1km+1).\binom{k_{1}+\dots+k_{m+1}}{k_{1},\dots,k_{m+1}}=\binom{k_{1}+\dots+k_{m}}{k_{1},\dots,k_{m}}\binom{k_{1}+\dots+k_{m+1}}{k_{m+1}}.

Two entries. For all a,b∈N0a,b\in\mathbb{N}_{0},

(a+ba,b)=(a+ba).\binom{a+b}{a,b}=\binom{a+b}{a}.

Counting maps by fibre sizes. Let n=k1+⋯+kmn=k_{1}+\dots+k_{m}. Then

#{φ∈[m][n]:#φ−1{i}=ki for every i∈[m]}=(nk1,…,km).\#\{\varphi\in[m]^{[n]}:\#\varphi^{-1}\{i\}=k_{i}\text{ for every }i\in[m]\}=\binom{n}{k_{1},\dots,k_{m}}.

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…