Codex @codex  0

Allocate $n$ distinct objects to $k$ labelled bins of specified nonnegative sizes $n_1,\dots ,n_k$, with ${\sum }_i{n}_i=n$. Order within a bin is ignored. The number of allocations is the multinomial coefficientTo prove this, order all the objects in a permutation and assign the first $n_1$ to the first bin, the next $n_2$ to the second, and so on. Every allocation comes from exactly $n_1!\cdots n_k!$ internal orderings. These disjoint classes exhaust the $n!$ permutations, proving the formula by the multiplication principle. Empty bins are allowed because $0!=1$.

For two bins of sizes $m$ and $n-m$, the count is $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ and every allocation has multiplicity $m!(n-m)!$ in the permutation sample space. Exchanging two equal-sized labelled bins generally gives a different allocation. In contrast, a set partition uses unlabelled nonempty blocks; forgetting bin labels changes the counting problem and must not be done silently.

For an attainable empirical distribution $q$ on a fixed finite alphabet of size $m$,Thus $\ln |T_n(q)|$ differs from $n{H}_e(q)$ by at most $m\ln (n+1)$, uniformly over attainable profiles. Information entropy is the leading logarithmic count; the polynomial factor matters at short lengths.^[ref]

The upper bound has a short explanation. Under an independent and identically distributed source whose law is $q$ itself, each string in $T_n(q)$ has probability $e^{-n{H}_e(q)}$. Multiplying by the number of such strings cannot give a probability above one. A corresponding polynomial lower bound follows from the multinomial coefficient; the Stirling's approximation gives sharper prefactors when needed.

For the balanced four-symbol class, $H_e(q)=\ln 2$, so the upper bound is $e^{4\ln 2}=16$, while the exact size is six. Information entropy is not an exact count for a short string. On the leading scale it becomes precise: the difference divided by $n$ tends to zero as $n$ grows with the alphabet fixed.

For $m$ functions with sufficiently many derivatives, the $n$th derivative of their product distributes the $n$ differentiations among all factors. If factor $j$ is differentiated $k_j$ times, its term has the multinomial coefficient $n!/(k_1!\cdots k_m!)$, where the nonnegative integers $k_j$ sum to $n$. Induction on the number of factors proves this from the two-factor Leibniz rule: splitting off the final factor gives a binomial coefficient, which multiplies the previous multinomial coefficient to give the one displayed above. Equivalently, count the ways to choose which of the $n$ successive applications of the product rule differentiate each factor.

For $n\ge 2$ and positive integers $d_1,\dots ,d_n$ with ${\sum }_v{d}_v=2(n-1)$, the number of labelled trees having vertex degree $d_v$ at label $v$ isBy the Prüfer degree formula, this is the multinomial coefficient counting sequences with $d_v-1$ occurrences of each label. If a degree is zero or the sum is wrong, there are no such trees. For the example degree sequence $(2,1,3,1,2,1)$, there are $4!/(1!0!2!0!1!0!)=12$ labelled trees, one for each ordering of the labels $1,3,3,5$. Knowing the vertex degrees thus constrains, but usually does not determine, the tree.

An ordered state $x=(c_1,\dots ,c_n)$ records the classes and positions of customers at a single server. Class-$r$ arrivals have rate ${\alpha }_r$ and exponential service parameter ${\mu }_r$. Under a symmetric service discipline, its stationary distribution is $(1-\rho ){\prod }_i({\alpha }_{c_i}/{\mu }_{c_i})$, where $\rho ={\sum }_r{\alpha }_r/{\mu }_r<1$. If every ${\mu }_r=\mu$, class-independent insertion and service position rules need not be equal: time reversal of a continuous-time Markov chain interchanges them and proves the same law. Aggregating words gives $(1-\rho )n!{\prod }_r[({\alpha }_r/{\mu }_r{)}^{n_r}/n_r!]$ by the multinomial coefficient. With class-dependent service rates, first come first served need not have this product law.

For nonnegative integers with $n_1+\cdots +n_r=n$, the multinomial coefficientcounts arrangements of a multiset containing $n_j$ copies of symbol $j$.

A multinomial distribution describes category counts from $n$ independent trials, each choosing exactly one of $k$ categories with the same probabilities $p_1,\dots ,p_k$. Require $n\ge 0$ to be an integer, $p_i\ge 0$, and ${\sum }_i{p}_i=1$. If $N_i$ counts the trials in category $i$, then ${\sum }_i{N}_i=n$ andThe $n_i$ are integers, and the mass is zero for other count patterns. A category with $p_i=0$ has count zero almost surely, with $0^0=1$ in this formula. For a specified ordered trial sequence, independence gives the product of numbers ${\prod }_i{p}_i^{n_i}$; the multinomial coefficient counts the different sequences with that same count pattern.

For four trials with category probabilities $(1/2,3/10,1/5)$, the count pattern $(2,1,1)$ can occur in $4!/(2!1!1!)=12$ orders, each of probability $(1/2{)}^2(3/10)(1/5)=0.015$. Thus its total probability is $12(0.015)=0.18$. This is a constructed independent-trial example, distinct from drawing four objects without replacement from a ten-object population of composition $(5,3,2)$, where the multivariate hypergeometric distribution gives $2/7$.

The diagram shows all fifteen possible count patterns. Coordinates $(N_1,N_2)$ determine $N_3=4-N_1-N_2$; the triangle is a constraint on integer counts, not a continuous probability density. The mode is $(N_1,N_2,N_3)=(2,1,1)$, where the probability mass function is largest, but the expected values $(2,1.2,0.8)$ are not a possible count pattern.

Each single count has a binomial distribution, because recording category $i$ versus all other categories reduces every trial to a Bernoulli trial. Consequently,These statements about the joint count model are summarized in Aditya Guntuboyina's lecture notes.^[ref]

Independent trials do not make the resulting counts independent random variables. Within one trial the indicator random variables for two distinct categories cannot both equal one, so their product is zero and their covariance is $-p_i{p}_j$. Summing over independent trials gives $-n{p}_i{p}_j$. In the four-trial example, the variances are $(1,0.84,0.64)$ and the pairwise covariances are $-0.6,-0.4,-0.24$. Knowing that all four trials were in the first category fixes the other two counts at zero.

The attraction is that one formula describes any fixed-total list of category counts while preserving the constraint that they add up to $n$. It underlies multinomial likelihood calculations and uniform balls-in-bins allocation. The multinomial aggregation rule lets us merge categories without leaving this family of probability distributions. Allowing independent category counts with an unfixed total instead leads to a different model, related through Poisson-multinomial conditioning.

A multiclass queue must specify its service discipline as well as its arrival and service rates. Here is an ordered-queue model that includes the usual class-independent exponential single-server queue. Let class-$r$ arrivals be independent Poisson processes of rates ${\alpha }_r$, and let a class-$r$ service requirement have the exponential distribution of rate ${\mu }_r$. A state is a finite word $x=(c_1,\dots ,c_n)$ of customer classes.

Choose service fractions ${\gamma }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\gamma }_i(n)=1$, and insertion probabilities ${\delta }_i(n)\ge 0$ with ${\sum }_{i=1}^n{\delta }_i(n)=1$. The customer at position $i$ departs at rate ${\mu }_{c_i}{\gamma }_i(n)$; a class-$r$ arrival is inserted at position $i$ at rate ${\alpha }_r{\delta }_i(n+1)$. All rates leading to the same word are added. For class-dependent ${\mu }_r$, impose the symmetric service discipline ${\delta }_i(n)={\gamma }_i(n)$. If all ${\mu }_r=\mu$, arbitrary class-independent $\gamma ,\delta$ are permitted, including first come first served with insertion at the tail and service at the head.

Put ${\rho }_r={\alpha }_r/{\mu }_r$ and $\rho ={\sum }_r{\rho }_r$. For $\rho <1$, the equilibrium word law isFor the symmetric service discipline, insertion and deletion satisfy detailed balance for a continuous-time Markov chain becauseFor the common-service-rate case, use time reversal of a continuous-time Markov chain instead: the reversed queue inserts with probabilities $\gamma$ and serves with fractions $\delta$. A forward insertion gives a reverse deletion rate $\mu {\delta }_i$, and a forward deletion gives a reverse insertion rate ${\alpha }_r{\gamma }_i$. Forward and reverse total rates both equal ${\sum }_r{\alpha }_r+\mu 1_{\{n>0\}}$, proving global balance for a continuous-time Markov chain.

Summing the weights of all words of length $n$ gives $(1-\rho ){\rho }^n$, so the law is normalized. If $n_r$ counts class-$r$ customers and $n={\sum }_r{n}_r$, the multinomial coefficient counting class orderings givesFor processor sharing, ${\gamma }_i(n)={\delta }_i(n)=1/n$, the class-count vector itself is a Markov chain, with arrival rate ${\alpha }_r$ and departure rate ${\mu }_r{n}_r/n$. Under first come first served, the ordered word is generally necessary. Class-dependent service rates combined with first come first served do not in general have the displayed simple equilibrium law; the discipline assumption matters.

For occupations $W_n=Wp(n)$ of $W$ distinguishable copies, the number of arrangements is the multinomial coefficient $\mathcal{N}=W!/{\prod }_n{W}_n!$. The ensemble entropy is $S_W=k_B\log \mathcal{N}$. Stirling's formula and $\sum W_n=W$ giveDividing by the number of independent copies and taking the large-ensemble limit recovers $S=-k_B{\sum }_{n}p(n)\log p(n)$. Terms with zero occupation are interpreted by the usual $0\log 0=0$ convention.

Let $S_0=0$ and let each increment of the simple symmetric random walk be uniformly chosen from $\{\pm e_1,\pm e_2,\pm e_3\}$. A return requires an even number of steps. In $2n$ steps returning to zero, let $a,b,c$ be the respective numbers of positive steps in the three directions; there must also be $a,b,c$ negative steps, so $a+b+c=n$. Counting step sequences givesThe terms $p_{abc}=n!/(3^{n}a!b!c!)$ form a multinomial distribution, so $\sum p_{abc}^2\le (\max p_{abc})\sum p_{abc}=\max p_{abc}$. The permitted combinatorial inequalities give $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\le C_1{n}^{-1/2}$ and ${\max }_{a+b+c=n}{p}_{abc}\le C_2/n$ for $n\ge 1$. The second bound also follows by noting that the largest multinomial coefficient occurs when $a,b,c$ differ by at most one and then applying Stirling formula. ThusTo prove the origin is a transient state, let $q$ be the probability of at least one return after time zero. The Strong Markov property at successive returns gives $\mathbb{P}(N\ge k)=q^k$ for the number $N$ of later returns. Therefore $\mathbb{E}(N+1)={\sum }_j{u}_j$ would be infinite if $q=1$. The bound forces $q<1$, proving that the origin is a transient state. Translation invariance gives the same conclusion at every lattice point. The coordinate walks need not be treated as independent; the counting via multinomial coefficients already incorporates their dependence.

Let $D_n(a)$ denote the constant term, retaining the dimension as a subscript when it changes. We use the Good recurrence for the Dyson constant term. For algebraically independent variables, Lagrange interpolation polynomial applied to the constant polynomial one givesAt $t=0$, this becomes the rational identityWhen every $a_i>0$, multiplying by the given Laurent polynomial cancels one factor in row $i$ of the product and givesThis is a polynomial identity after cancellation; no choice of an expansion of a rational function is involved.

The boundary case is essential. If $a_i=0$, the factors in row $i$ are absent. The only factors involving $X_i$ are then $(1-X_j/X_i{)}^{a_j}$ for $j\ne i$, and all their powers of $X_i$ are nonpositive. To obtain power zero in $X_i$, one must select the constant term one from each of them. Taking the constant term in $X_i$ therefore deletes that variable and exponent:For $n=1$, the empty product is one, so $D_1(a_1)=1$. The all-zero exponent vector also gives one.

Now put $M_n(a)=m!/{\prod }_i{a}_i!$, where $m={\sum }_i{a}_i$. This multinomial coefficient obeys the same deletion rule for a zero exponent. For positive exponents,Induction on $n$, and within each dimension on $m$, consequently determines $D_n$ uniquely and identifies it with $M_n$. This proves the Dyson constant-term identity:

The mean extension in an ensemble of $A$ molecules iswith constraints ${\sum }_i{a}_i=A$ and ${\sum }_i{a}_i{l}_i=AL$. For occupancies $\{a_i\}$, the number of assignments of the $A$ distinguishable ensemble members to the states is the multinomial coefficientThus maximizing the probability at fixed $A$ and $L$ is equivalent to maximizing the stated Lagrange multiplier expression.

Because $A\gg 1$, the Stirling formula gives $\log (a_i!)\simeq a_i\log a_i-a_i$. Differentiating with respect to each $a_i$ givesNormalization by ${\sum }_i{a}_i=A$ therefore yields the probability mass functionHere $Z$ is the fixed-tension partition function that normalizes the probabilities.

Let $D(a)$ denote the stated constant term and suppose every $a_i>0$. The rational identitycan be verified after clearing denominators, or by Lagrange interpolation. Multiplying it by the Dyson product and taking constant terms gives the recursionThe multinomial coefficientobeys the same recursion by the multinomial form of Pascal's identity.

If $a_k=0$, taking the constant term in $X_k$ forces the zero term from every factor involving $X_k$ and reduces the expression to the $(n-1)$-variable Dyson product with $a_k$ omitted. The same boundary reduction holds for $M(a)$. Finally $D(0,\dots ,0)=M(0,\dots ,0)=1$. Induction on $n$ and on $a_1+\cdots +a_n$ therefore proves the Dyson constant-term identity

Under complete randomization, every assignment vector with exactly $n_z$ patients receiving treatment $z$ is equally likely. Thus, for $z=(z_1,\dots ,z_n)$ and $N_r(z)={\sum }_i{1}_{\{z_i=r\}}$,The reciprocal probability $n!/(n_0!n_1!n_2!)$ is the multinomial coefficient counting assignments with those arm sizes.

The protein primary structure specifies the ordered amino acid residues of each polypeptide chain, joined through peptide bonds. A chain is conventionally written from its N-terminus to its C-terminus. In the broader chemical sense, a complete protein primary structure also specifies covalent bond crosslinks between chain positions, including protein disulfide bonds; a bare sequence string leaves that information unstated. This describes chemical connectivity rather than the spatial arrangement of protein tertiary structure or protein quaternary structure. See IUPAC Gold Book: primary structure, sequence and chain crosslinking and IUPAC-IUB, 3AA-16: writing residue sequences from the amino end. Some conventions reserve protein primary structure for sequence alone and call the complete chemical connectivity the covalent structure; the distinction should be stated when comparing descriptions. See IUPAC-IUB polypeptide-conformation recommendations, section 6.1: the narrower sequence-only convention.

In this toy example M denotes methionine, A alanine and G glycine. Both polypeptide chains have six amino acid residues, five peptide bonds, an M at the N-terminus and a G at the C-terminus. Their amino acid composition is identical, yet position 2 is A in MAGAMG and M in MMAAGG. There are $6!/(2!2!2!)=90$ distinct orders with these counts, a multinomial coefficient. Even fixing those two end residues leaves $4!/(1!2!1!)=12$ orders. The counts constrain the answer without determining it.

For multiple polypeptide chains, record each sequence separately and specify any protein disulfide bonds between cysteine positions. Mature insulin, for example, has an A chain of 21 amino acid residues and a B chain of 30 amino acid residues. Their combined 51 residues give $(21-1)+(30-1)=49$ peptide bonds, rather than the 50 of one unbroken 51-residue chain. See Cooper, The Cell: insulin's two chains and cysteine crosslinks, figure 2.16. A protein disulfide bond joins side groups; it does not concatenate the C-terminus of one chain with the N-terminus of another. The three insulin protein disulfide bonds connect A6 to A11 within the A chain, and A7 to B7 and A20 to B19 between chains. Positions are numbered from each chain's N-terminus. See Replacement of the interchain disulfide bridge-forming amino acids A7 and B7 by glutamate impairs the structure and activity of insulin: native disulfide positions.

Why keep this information? Protein primary structure lets us distinguish changes of chemical identity from changes of shape, and compare corresponding positions between proteins. Protein folding can bring distant amino acid residues together at a protein binding site while preserving their sequence. The attractive idea is that a readable linear record can constrain a complicated three-dimensional object; it is not, by itself, a guarantee of a unique fold in every environment. See protein folding and the ribonuclease A refolding experiment. Merely bending an intact chain preserves its protein primary structure; hydrolysis of a peptide bond, or changing which positions a protein disulfide bond connects, changes its chemical connectivity.

Write $n_a=nq(a)$. Arranging $n_a$ copies of each symbol gives the multinomial coefficientThe division by the factorials removes permutations among identical copies. In the balanced four-symbol example, $|T_4(q)|=4!/(2!2!)=6$. For binary symbols this becomes the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; for three symbols with counts $(2,1,1)$, the class contains $4!/(2!1!1!)=12$ strings.