Introduction
Let s = ( s 1 , … , s n ) \mathbf{s}=(s_1,\ldots,s_n) s = ( s 1 , … , s n ) be a vector of non-negative integers and put N = s 1 + ⋯ + s n N=s_1+\cdots+s_n N = s 1 + ⋯ + s n . For 0 ≤ k ≤ N 0\le k\le N 0 ≤ k ≤ N , let R s ( k ) R_{\mathbf{s}}(k) R s ( k ) be the number of integer solutions of
k 1 + ⋯ + k n = k , 0 ≤ k i ≤ s i , i = 1 , … , n , (1) k_1+\cdots+k_n=k,\qquad0\le k_i\le s_i,\qquad i=1,\ldots,n, \tag*{(1)} k 1 + ⋯ + k n = k , 0 ≤ k i ≤ s i , i = 1 , … , n , (1)
or, equivalently,
R s ( k ) = [ x k ] ∏ i = 1 n ( 1 + x + ⋯ + x s i ) . (2) R_{\mathbf{s}}(k)=[x^k]\prod_{i=1}^{n}(1+x+\cdots+x^{s_i}). \tag*{(2)} R s ( k ) = [ x k ] i = 1 ∏ n ( 1 + x + ⋯ + x s i ) . (2)
Set R s ( k ) = 0 R_{\mathbf{s}}(k)=0 R s ( k ) = 0 for k < 0 k<0 k < 0 or k > N k>N k > N . In the multiset model, type i i i has s i s_i s i indistinguishable objects, of which we choose k i k_i k i . Thus R s ( k ) R_{\mathbf{s}}(k) R s ( k ) gives the number of size-k k k submultisets of a multiset of total size N N N .
The solution to Problem (1) is a standard exercise in inclusion–exclusion; see, for example, Charalambides [13, Theorem 4.3], Riordan [37, Problem 1.7], or West [43, Example 4.1.6]. The generating polynomial in (2) is the rank polynomial of a product of chains and, after normalization, the probability generating function of a sum of independent discrete uniform random variables. When s i = 2 σ i s_i = 2\sigma_i s i = 2 σ i , with each σ i ∈ 1 2 Z ≥ 0 \sigma_i \in\frac{1}{2}\mathbb{Z}_{\ge0} σ i ∈ 2 1 Z ≥ 0 , the coefficients are the weight-space dimensions of a tensor product of SU(2) representations. The first differences on the lower half of the array give the multiplicities of the irreducible constituents of this tensor product.
In the homogeneous case s i = s s_i=s s i = s with even n = 2 ν n=2\nu n = 2 ν , the central first difference is the s s s -Catalan number, which Linz identifies with a value of a Littlewood–Richardson stretching polynomial. For s = 1 s=1 s = 1 and s = 2 s=2 s = 2 , the resulting numbers are, respectively, the Catalan and even-indexed Riordan numbers. Near the boundary, by contrast, the coefficients and their first differences collapse to simplex numbers. The central rank layers of the product of chains are its largest antichains and therefore yield maximum-size constant-sum codebooks in the Winternitz framework, with applications to SPHINCS+ and XMSS [44 ] . Table 1 summarizes the principal interpretations and their specializations.
Table 1. Several interpretations of the coefficient array R s ( k ) R_s(k) R s ( k ) .
Our objective in this work is to survey these classical identities and interpretations and to record their provenance and terminology across the relevant literatures. In our derivations we carefully distinguish the globally valid and support-sharp forms of de Moivre’s sum and combine the sharp cutoff with complement symmetry. We also connect first differences with symmetric-chain starts and equal- and mixed-spin multiplicities, and trace the boundary formulas from their exact range to a Poisson crossover. In an algebraic coda, we examine the effect of using the polynomial convention for binomial coefficients with negative upper arguments. Examples throughout the article illustrate the main identities and show how the different interpretations apply in concrete cases.
Notation, terminology, and history
Notation
Throughout, n n n denotes the number of types, cells, or particles, depending on the interpretation. The integer k k k is the prescribed total, and k i k_i k i is the contribution of the component indexed by i i i . The individual upper bounds are s i s_i s i ; in the homogeneous case they all equal s s s , and N = s 1 + ⋯ + s n N=s_1+\cdots+s_n N = s 1 + ⋯ + s n is the maximum possible total. We use R s ( k ) R_s(k) R s ( k ) for the inhomogeneous enumeration in (2) and write ( n k ) s \binom{n}{k}_s ( k n ) s when all bounds equal s s s . In the representation-theoretic sections, σ \sigma σ denotes a single-particle spin, m m m the total magnetization, and J J J the total spin; when the number of particles is even, we write n = 2 ν n=2\nu n = 2 ν . The symbol q q q is reserved for deformation parameters.
The homogeneous notation ( n k ) s \binom{n}{k}_s ( k n ) s follows Belbachir and Benmezai [4 ] and Linz [26 ] ; the notation R s ( k ) R_s(k) R s ( k ) keeps the full vector of unequal bounds explicit.
Terminology
In the homogeneous case the numbers defined by (1) are the binomial coefficients ( n k ) s \binom{n}{k}_s ( k n ) s , defined by the expansion
( 1 + x + x 2 + ⋯ + x s ) n = ∑ k ≥ 0 ( n k ) s x k , ( n k ) s = 0 for k < 0 or k > n s . (3) (1+x+x^2+\cdots+x^s)^n=\sum_{k\ge0}\binom{n}{k}_s x^k,\qquad\binom{n}{k}_s=0\ \text{for }k<0\text{ or }k>ns. \tag*{(3)} ( 1 + x + x 2 + ⋯ + x s ) n = k ≥ 0 ∑ ( k n ) s x k , ( k n ) s = 0 for k < 0 or k > n s . (3)
Other names for these coefficients include ordinary multinomial coefficients , polynomial coefficients , and extended or generalized binomial coefficients of order s + 1 s+1 s + 1 . Here polynomial coefficients names the array, not the convention for ordinary binomial coefficients that we discuss in § 9 . For s = 1 s=1 s = 1 , the coefficients reduce to the ordinary binomial coefficients, ( k 1 ) = ( k k ) \binom{k}{1}=\binom{k}{k} ( 1 k ) = ( k k ) . The full coefficient array is the bis nomial triangle, also called the s s s -Pascal triangle.
The abundance of names reflects the array’s appearance in several literatures. Belbachir and Igueroufa [7 Table 1] provide a historical census, extending from Euler (1778) to Belbachir and Benmezai [4 ] , and date the term bis nomial to the latter authors [4 ] . Table 2 of the same paper catalogs the names used for the coefficient array.
History
The homogeneous form of Problem (1) goes back to de Moivre. In its original guise, it asks for the number of ways to obtain a prescribed total with n n n dice having s + 1 s+1 s + 1 numbered faces. De Moivre stated the problem for general n n n and s s s without proof in De Mensura Sortis (1711). His first published proof, based essentially on generating functions, appeared in the Miscellanea Analytica (1730, p. 196). Montmort had independently obtained an inclusion–exclusion solution by 1713; see Hald [25 ] and Doumas [19 ] . The gap between de Moivre’s statement and his first published proof explains some of the conflicting dates in the later coefficient literature.
Freund [21 ] later interpreted ( n k ) s \binom{n}{k}_{s} ( k n ) s as the number of distributions of k k k objects among n n n cells with at most s s s objects in each cell. He treated the problem under the heading of restricted occupancy theory ; see also Bondarenko [11 ] .
Enumeration by inclusion–exclusion
Two basic formulas
The enumeration in Problem (1) uses two basic combinatorial formulas. For subsets A 1 , … , A M A_1,\ldots,A_M A 1 , … , A M of a finite set S S S , the first is the principle of inclusion–exclusion in the form
∣ S ∖ ⋃ i = 1 M A i ∣ = ∑ I ⊆ { 1 , … , M } ( − 1 ) ∣ I ∣ ∣ ⋂ i ∈ I A i ∣ (4) \left|S\setminus\bigcup_{i=1}^{M}A_i\right|=\sum_{I\subseteq\{1,\ldots,M\}}(-1)^{|I|}\left|\bigcap_{i\in I}A_i\right| \tag*{(4)} S ∖ i = 1 ⋃ M A i = I ⊆ { 1 , … , M } ∑ ( − 1 ) ∣ I ∣ i ∈ I ⋂ A i (4)
where the intersection indexed by the empty set is S S S . The second is the stars-and-bars formula for the number of non-negative solutions of k 1 + ⋯ + k n = k k_1+\cdots+k_n=k k 1 + ⋯ + k n = k , namely
( k + n − 1 n − 1 ) = ( k + n − 1 k ) (5) \binom{k+n-1}{n-1}=\binom{k+n-1}{k} \tag*{(5)} ( n − 1 k + n − 1 ) = ( k k + n − 1 ) (5)
where the equality follows from the symmetry of the ordinary binomial coefficient.
By default, we use the elementary convention for binomial coefficients
( u v ) = 0 unless 0 ≤ v ≤ u . (6) \binom{u}{v}=0\quad\text{unless}\quad0\leq v\leq u. \tag*{(6)} ( v u ) = 0 unless 0 ≤ v ≤ u . (6)
This convention is standard in the bis nomial literature [4 , 5 , 7 ] . It makes inclusion–exclusion terms with negative or too-small upper arguments vanish, as required for empty intersections. In § 9 , we show that the generating function produces exactly the terms the convention retains and evaluate the sum of the additional terms that the alternative polynomial convention (see, for instance, [22 §5.1] ) contributes. Under this latter convention, ( u v ) \binom{u}{v} ( v u ) is the polynomial u ( u − 1 ) ⋯ ( u − v + 1 ) / v ! u(u-1)\cdots(u-v+1)/v! u ( u − 1 ) ⋯ ( u − v + 1 ) / v ! in u u u for each fixed integer v ≥ 0 v\geq0 v ≥ 0 .
Enumeration in the inhomogeneous case
For 0 ≤ k ≤ N 0\leq k\leq N 0 ≤ k ≤ N , let S S S be the set of non-negative integer solutions of k 1 + ⋯ + k n = k k_1+\cdots+k_n=k k 1 + ⋯ + k n = k , without the upper bounds in (1) . The stars-and-bars formula gives
Σ 0 = ∣ S ∣ = ( k + n − 1 n − 1 ) . (7) \Sigma_0=|S|=\binom{k+n-1}{n-1}. \tag*{(7)} Σ 0 = ∣ S ∣ = ( n − 1 k + n − 1 ) . (7)
For each i i i , let A i ⊆ S A_i \subseteq S A i ⊆ S be the set of solutions that violate the upper bound on k i k_i k i , so that k i ≥ s i + 1 k_i \ge s_i+1 k i ≥ s i + 1 . Writing k i = s i + 1 + b i k_i=s_i+1+b_i k i = s i + 1 + b i gives a bijection between A i A_i A i and the non-negative solutions of
k 1 + ⋯ + b i + ⋯ + k n = k − ( s i + 1 ) , (8) k_1+\cdots+b_i+\cdots+k_n=k-(s_i+1), \tag*{(8)} k 1 + ⋯ + b i + ⋯ + k n = k − ( s i + 1 ) , (8)
whose number is, by (5) , ( k − ( s i + 1 ) + n − 1 n − 1 ) \binom{k-(s_i+1)+n-1}{n-1} ( n − 1 k − ( s i + 1 ) + n − 1 ) . Hence
Σ 1 = ∑ i = 1 n ∣ A i ∣ = ∑ i = 1 n ( k − ( s i + 1 ) + n − 1 n − 1 ) . (9) \Sigma_1=\sum_{i=1}^{n}|A_i|=\sum_{i=1}^{n}\binom{k-(s_i+1)+n-1}{n-1}. \tag*{(9)} Σ 1 = i = 1 ∑ n ∣ A i ∣ = i = 1 ∑ n ( n − 1 k − ( s i + 1 ) + n − 1 ) . (9)
For distinct indices i 1 , … , i j i_1,\ldots,i_j i 1 , … , i j , shifting the corresponding j j j coordinates reduces the prescribed total by ∑ l = 1 j ( s i l + 1 ) \sum_{l=1}^{j}(s_{i_l}+1) ∑ l = 1 j ( s i l + 1 ) . Summing over all j j j -element sets of indices gives
Σ j = ∑ 1 ≤ i 1 < ⋯ < i j ≤ n ∣ A i 1 ∩ ⋯ ∩ A i j ∣ = ∑ 1 ≤ i 1 < ⋯ < i j ≤ n ( k − ∑ l = 1 j ( s i l + 1 ) + n − 1 n − 1 ) . (10) \Sigma_j=\sum_{1\le i_1<\cdots<i_j\le n}|A_{i_1}\cap\cdots\cap A_{i_j}|=\sum_{1\le i_1<\cdots<i_j\le n}\binom{k-\sum_{l=1}^{j}(s_{i_l}+1)+n-1}{n-1}. \tag*{(10)} Σ j = 1 ≤ i 1 < ⋯ < i j ≤ n ∑ ∣ A i 1 ∩ ⋯ ∩ A i j ∣ = 1 ≤ i 1 < ⋯ < i j ≤ n ∑ ( n − 1 k − ∑ l = 1 j ( s i l + 1 ) + n − 1 ) . (10)
Because k ≤ N k\le N k ≤ N , the intersection A 1 ∩ ⋯ ∩ A n A_1\cap\cdots\cap A_n A 1 ∩ ⋯ ∩ A n is empty: if every upper bound were violated, then ∑ i = 1 n k i ≥ N + n > k \sum_{i=1}^{n}k_i\ge N+n>k ∑ i = 1 n k i ≥ N + n > k . Hence Σ n = 0 \Sigma_n=0 Σ n = 0 , and inclusion–exclusion gives
R s ( k ) = ∑ j = 0 n − 1 ( − 1 ) j ∑ 1 ≤ i 1 < ⋯ < i j ≤ n ( k − ∑ l = 1 j ( s i l + 1 ) + n − 1 n − 1 ) . (11) R_{\mathbf{s}}(k)=\sum_{j=0}^{n-1}(-1)^j\sum_{1\le i_1<\cdots<i_j\le n}\binom{k-\sum_{l=1}^{j}(s_{i_l}+1)+n-1}{n-1}. \tag*{(11)} R s ( k ) = j = 0 ∑ n − 1 ( − 1 ) j 1 ≤ i 1 < ⋯ < i j ≤ n ∑ ( n − 1 k − ∑ l = 1 j ( s i l + 1 ) + n − 1 ) . (11)
For j = 0 j=0 j = 0 , the inner sum contains only the empty index set and equals ( k + n − 1 n − 1 ) \binom{k+n-1}{n-1} ( n − 1 k + n − 1 ) . Formula (11) is a special case of the lower-and-upper-bound result of Charalambides [13 Theorem 4.3] . MacMahon [27 §§38–39] treats bounded multiplicities by symmetric-function methods.
If L i L_i L i denotes the number of types whose bound equals i i i , collecting equal bounds rewrites the generating polynomial as ∏ i ≥ 1 ( 1 + x + ⋯ + x i ) L i \prod_{i\ge1}(1+x+\cdots+x^i)^{L_i} ∏ i ≥ 1 ( 1 + x + ⋯ + x i ) L i . The coefficients in this expansion are the classical supernomial coefficients of Schilling and Warnaar [38 ] ; see also Belbachir, Bouroubi, and Khelladi [5 Section 1] . Equations (30)–(31) describe the corresponding supernomial boundary regimes.
Example 3.1 (Unequal bounds). Take s = ( 1 , 2 , 4 ) \mathbf{s}=(1,2,4) s = ( 1 , 2 , 4 ) and k = 5 k=5 k = 5 . There are ( 7 2 ) = 21 \binom{7}{2}=21 ( 2 7 ) = 21 unrestricted non-negative solutions. The sets defined by k 1 ≥ 2 k_1\ge2 k 1 ≥ 2 , k 2 ≥ 3 k_2\ge3 k 2 ≥ 3 , and k 3 ≥ 5 k_3\ge5 k 3 ≥ 5 have sizes ( 5 2 ) = 10 \binom{5}{2}=10 ( 2 5 ) = 10 , ( 4 2 ) = 6 \binom{4}{2}=6 ( 2 4 ) = 6 , and ( 2 2 ) = 1 \binom{2}{2}=1 ( 2 2 ) = 1 , respectively. The only nonempty pairwise intersection is A 1 ∩ A 2 = { ( 2 , 3 , 0 ) } A_1\cap A_2=\{(2,3,0)\} A 1 ∩ A 2 = {( 2 , 3 , 0 )} , so equation (11) gives
R ( 1 , 2 , 4 ) ( 5 ) = 21 − 10 − 6 − 1 + 1 = 5. R_{(1,2,4)}(5)=21-10-6-1+1=5. R ( 1 , 2 , 4 ) ( 5 ) = 21 − 10 − 6 − 1 + 1 = 5.
The five admissible tuples are ( 0 , 1 , 4 ) (0,1,4) ( 0 , 1 , 4 ) , ( 0 , 2 , 3 ) (0,2,3) ( 0 , 2 , 3 ) , ( 1 , 0 , 4 ) (1,0,4) ( 1 , 0 , 4 ) , ( 1 , 1 , 3 ) (1,1,3) ( 1 , 1 , 3 ) , and ( 1 , 2 , 2 ) (1,2,2) ( 1 , 2 , 2 ) . The final + 1 +1 + 1 corrects the double subtraction of ( 2 , 3 , 0 ) (2,3,0) ( 2 , 3 , 0 ) .
The homogeneous enumeration: de Moivre's alternating summation
Suppose n > 1 n>1 n > 1 and all bounds equal s s s , so that N = n s N=ns N = n s . Riordan [37 Problem 1.7] calls the resulting homogeneous coefficients regular. In (10) , the binomial coefficient then depends only on j j j , while the j j j restricted coordinates can be chosen in ( n j ) \binom{n}{j} ( j n ) ways. Hence
Σ j = ( n j ) ( k − j ( s + 1 ) + n − 1 n − 1 ) . (12) \Sigma_j=\binom{n}{j}\binom{k-j(s+1)+n-1}{n-1}. \tag*{(12)} Σ j = ( j n ) ( n − 1 k − j ( s + 1 ) + n − 1 ) . (12)
On the admissible range 0 ≤ k ≤ n s 0\le k\le ns 0 ≤ k ≤ n s , we have Σ n = 0 \Sigma_n=0 Σ n = 0 , and inclusion–exclusion reduces to
( n k ) s = ∑ j = 0 n − 1 ( − 1 ) j Σ j = ∑ j = 0 n − 1 ( − 1 ) j ( n j ) ( k − j ( s + 1 ) + n − 1 n − 1 ) . (13) \binom{n}{k}_s=\sum_{j=0}^{n-1}(-1)^j\Sigma_j=\sum_{j=0}^{n-1}(-1)^j\binom{n}{j}\binom{k-j(s+1)+n-1}{n-1}. \tag*{(13)} ( k n ) s = j = 0 ∑ n − 1 ( − 1 ) j Σ j = j = 0 ∑ n − 1 ( − 1 ) j ( j n ) ( n − 1 k − j ( s + 1 ) + n − 1 ) . (13)
For ( n , s , k ) = ( 3 , 2 , 4 ) (n,s,k)=(3,2,4) ( n , s , k ) = ( 3 , 2 , 4 ) , equation (13) gives ( 6 2 ) − 3 ( 3 2 ) = 6 \binom{6}{2}-3\binom{3}{2}=6 ( 2 6 ) − 3 ( 2 3 ) = 6 , corresponding to the three permutations of ( 2 , 2 , 0 ) (2,2,0) ( 2 , 2 , 0 ) and the three permutations of ( 2 , 1 , 1 ) (2,1,1) ( 2 , 1 , 1 ) .
Identity (13) is de Moivre’s alternating summation. Belbachir, Bouroubi, and Khelladi [5 Theorem 2.1] state and prove the support-sharp form
( n k ) s = ∑ j = 0 ⌊ k / ( s + 1 ) ⌋ ( − 1 ) j ( n j ) ( k − j ( s + 1 ) + n − 1 n − 1 ) . (14) \binom{n}{k}_{s}=\sum_{j=0}^{\lfloor k/(s+1)\rfloor}(-1)^j\binom{n}{j}\binom{k-j(s+1)+n-1}{n-1}. \tag*{(14)} ( k n ) s = j = 0 ∑ ⌊ k / ( s + 1 )⌋ ( − 1 ) j ( j n ) ( n − 1 k − j ( s + 1 ) + n − 1 ) . (14)
Their proof uses the generating-function factorization
( 1 + x + ⋯ + x s ) n = ( 1 − x s + 1 ) n ( 1 − x ) n = [ ∑ j = 0 n ( − 1 ) j ( n j ) x j ( s + 1 ) ] [ ∑ i ≥ 0 ( i + n − 1 n − 1 ) x i ] . (15) (1+x+\cdots+x^s)^n=\frac{(1-x^{s+1})^n}{(1-x)^n}=\left[\sum_{j=0}^{n}(-1)^j\binom{n}{j}x^{j(s+1)}\right]\left[\sum_{i\geq0}\binom{i+n-1}{n-1}x^i\right]. \tag*{(15)} ( 1 + x + ⋯ + x s ) n = ( 1 − x ) n ( 1 − x s + 1 ) n = [ j = 0 ∑ n ( − 1 ) j ( j n ) x j ( s + 1 ) ] [ i ≥ 0 ∑ ( n − 1 i + n − 1 ) x i ] . (15)
Extracting the coefficient of x k x^k x k from (15) gives (14) . Belbachir and Benmezai [4 Eq. (5)] and Belbachir and Igueroufa [7 Eq. (3)] also give (14) under the name de Moivre alternate summation . Thus (14) is the support-sharp form of (13) .
Proposition 3.3 (Exact summation bounds). For every k ≥ 0 k\geq0 k ≥ 0 , the nonzero terms in the full generating-function expansion are exactly those with
0 ≤ j ≤ min { n , ⌊ k s + 1 ⌋ } . (16) 0\leq j\leq\min\left\{n,\left\lfloor\frac{k}{s+1}\right\rfloor\right\}. \tag*{(16)} 0 ≤ j ≤ min { n , ⌊ s + 1 k ⌋ } . (16) Consequently, the globally valid coefficient formula is
( n k ) s = ∑ j = 0 min { n , ⌊ k / ( s + 1 ) ⌋ } ( − 1 ) j ( n j ) ( k − j ( s + 1 ) + n − 1 n − 1 ) , (17) \binom{n}{k}_{s}=\sum_{j=0}^{\min\{n,\lfloor k/(s+1)\rfloor\}}(-1)^j\binom{n}{j}\binom{k-j(s+1)+n-1}{n-1}, \tag*{(17)} ( k n ) s = j = 0 ∑ m i n { n , ⌊ k / ( s + 1 )⌋} ( − 1 ) j ( j n ) ( n − 1 k − j ( s + 1 ) + n − 1 ) , (17) where the left-hand side is zero for k > n s k>ns k > n s . On the admissible range 0 ≤ k ≤ n s 0\leq k\leq ns 0 ≤ k ≤ n s , the minimum is unnecessary; Belbachir, Bouroubi, and Khelladi [5 Theorem 2.1] and Charalambides [12 eq. (2.8)] give the sharp upper limit for nonzero summands ⌊ k / ( s + 1 ) ⌋ \lfloor k/(s+1)\rfloor ⌊ k / ( s + 1 )⌋ .
Proof. The factor ( n j ) \binom{n}{j} ( j n ) is nonzero exactly for 0 ≤ j ≤ n 0 \le j \le n 0 ≤ j ≤ n , whereas the second binomial coefficient is nonzero exactly when j ≤ k / ( s + 1 ) j \le k/(s+1) j ≤ k / ( s + 1 ) . A summand is nonzero precisely when both conditions hold, which gives the range stated in the proposition. Identity (17) then follows by coefficient extraction from (15). If 0 ≤ k ≤ n s 0 \le k \le ns 0 ≤ k ≤ n s , then k / ( s + 1 ) ≤ n s / ( s + 1 ) < n k/(s+1) \le ns/(s+1) < n k / ( s + 1 ) ≤ n s / ( s + 1 ) < n , so the minimum reduces to ⌊ k / ( s + 1 ) ⌋ \lfloor k/(s+1)\rfloor ⌊ k / ( s + 1 )⌋ and every displayed term is nonzero.
Example 3.4 (Beyond the support). The distinction matters off the admissible range. For s = 1 s=1 s = 1 , n = 2 n=2 n = 2 , and k = 4 k=4 k = 4 , the globally sharp cutoff is 2 and
( 2 0 ) ( 5 1 ) − ( 2 1 ) ( 3 1 ) + ( 2 2 ) ( 1 1 ) = 5 − 6 + 1 = 0 , (18) \binom{2}{0}\binom{5}{1}-\binom{2}{1}\binom{3}{1}+\binom{2}{2}\binom{1}{1}=5-6+1=0, \tag*{(18)} ( 0 2 ) ( 1 5 ) − ( 1 2 ) ( 1 3 ) + ( 2 2 ) ( 1 1 ) = 5 − 6 + 1 = 0 , (18)
whereas truncating at j = n − 1 = 1 j=n-1=1 j = n − 1 = 1 gives − 1 -1 − 1 .
Table Table 2 displays the first rows of the coefficient triangles for s = 2 , 3 s=2,3 s = 2 , 3 ; the coefficient triangle for s = 1 s=1 s = 1 is just the usual binomial (Pascal) triangle. Read by rows, with n ≥ 0 n \ge0 n ≥ 0 and 0 ≤ k ≤ n s 0 \le k \le ns 0 ≤ k ≤ n s , these arrays are catalogued in the On-Line Encyclopedia of Integer Sequences (OEIS) as sequences A027907 and A008287, respectively; the corresponding array for s = 4 s=4 s = 4 is A035343.
Table 2. The bisnomial coefficient triangles for s = 2 , 3 s=2,3 s = 2 , 3 and 0 ≤ n ≤ 6 0 \le n \le6 0 ≤ n ≤ 6 . Each row indexed by n n n lists ( n k ) s \binom{n}{k}_s ( k n ) s ; blank entries are zero. The central coefficient(s) at k = ⌊ n s / 2 ⌋ k=\lfloor ns/2\rfloor k = ⌊ n s /2 ⌋ and k = ⌈ n s / 2 ⌉ k=\lceil ns/2\rceil k = ⌈ n s /2 ⌉ are in bold, and the last column gives the row sum ( s + 1 ) n (s+1)^n ( s + 1 ) n .
Symmetry, boundary collapse, and figurate numbers
The bijection and the symmetry relation
Given a solution of Problem (1), set b i = s i − k i b_i=s_i-k_i b i = s i − k i . Then 0 ≤ b i ≤ s i 0 \le b_i \le s_i 0 ≤ b i ≤ s i for every i i i , and
b 1 + ⋯ + b n = ∑ i = 1 n s i − k = N − k . (19) b_1+\cdots+b_n=\sum_{i=1}^{n}s_i-k=N-k. \tag*{(19)} b 1 + ⋯ + b n = i = 1 ∑ n s i − k = N − k . (19)
Conversely, k i = s i − b i k_i=s_i-b_i k i = s i − b i recovers the original solution. Thus coordinatewise complementation replaces selected copies by omitted copies and gives a bijection between solutions of total k k k and solutions of total N − k N-k N − k . In the homogeneous case, it proves the symmetry relation
( n k ) s = ( n n s − k ) s . (20) \binom{n}{k}_{s}=\binom{n}{ns-k}_{s}. \tag*{(20)} ( k n ) s = ( n s − k n ) s . (20)
Belbachir, Bouroubi, and Khelladi [5 eq. (1.3)] and Belbachir and Igueroufa [7 eq. (4)] record this identity.
The stars-and-bars formula gives ( N − k + n − 1 n − 1 ) \binom{N-k+n-1}{n-1} ( n − 1 N − k + n − 1 ) unrestricted non-negative solutions in the variables b i b_i b i . The upper bounds are automatic precisely in the following range.
Proposition 4.1. For 0 ≤ k ≤ N 0 \le k \le N 0 ≤ k ≤ N , the identity R s ( k ) = ( N − k + n − 1 n − 1 ) R_s(k)=\binom{N-k+n-1}{n-1} R s ( k ) = ( n − 1 N − k + n − 1 ) holds if and only if N − k ≤ min ( s 1 , … , s n ) N-k \le\min(s_1,\ldots,s_n) N − k ≤ min ( s 1 , … , s n ) .
Proof. By the complement bijection, it remains to determine when every non-negative solution of b 1 + ⋯ + b n = N − k b_1+\cdots+b_n=N-k b 1 + ⋯ + b n = N − k automatically satisfies b i ≤ s i b_i\le s_i b i ≤ s i . If N − k ≤ min ( s 1 , … , s n ) N-k\le\min(s_1,\ldots,s_n) N − k ≤ min ( s 1 , … , s n ) , then b i ≤ N − k ≤ s i b_i\le N-k\le s_i b i ≤ N − k ≤ s i for every i i i . Conversely, choose i ∗ i^* i ∗ such that s i ∗ = min ( s 1 , … , s n ) s_{i^*}=\min(s_1,\ldots,s_n) s i ∗ = min ( s 1 , … , s n ) . If N − k > s i ∗ N-k>s_{i^*} N − k > s i ∗ , the unrestricted solution b i ∗ = N − k b_{i^*}=N-k b i ∗ = N − k , b l = 0 b_l=0 b l = 0 for l ≠ i ∗ l\ne i^* l = i ∗ is inadmissible, so the stars-and-bars formula strictly overcounts.
Figurate numbers
When s 1 = ⋯ = s n = s s_1=\cdots=s_n=s s 1 = ⋯ = s n = s , so that N = n s N=ns N = n s , put c = n s − k c=ns-k c = n s − k . For 0 ≤ c ≤ s 0\le c\le s 0 ≤ c ≤ s , Proposition 4.1 gives
( n n s − c ) s = ( c + n − 1 n − 1 ) = ( c + n − 1 c ) , (21) \binom{n}{ns-c}_{s}=\binom{c+n-1}{n-1}=\binom{c+n-1}{c}, \tag*{(21)} ( n s − c n ) s = ( n − 1 c + n − 1 ) = ( c c + n − 1 ) , (21)
where the second equality follows from the symmetry of the ordinary binomial coefficient. For fixed c c c , the numbers ( c + n − 1 c ) \binom{c+n-1}{c} ( c c + n − 1 ) form the c c c -dimensional simplex-number sequence — triangular for c = 2 c=2 c = 2 , tetrahedral for c = 3 c=3 c = 3 , and so on. In the binomial (Pascal) coefficient triangle these figurate sequences lie on diagonals. Left-aligning the rows turns these diagonal figurate sequences into columns, as Table 3 illustrates. Thus equation (21) identifies the coefficient at distance c c c from the upper edge of the support with the corresponding figurate number.
Table 3. A segment of the left-aligned binomial coefficient triangle. The entries below the diagonal label c c c form the sequence ( c + n − 1 c ) \binom{c+n-1}{c} ( c c + n − 1 ) , n ≥ 1 n\ge1 n ≥ 1 ; in particular, the columns c = 2 c=2 c = 2 and c = 3 c=3 c = 3 contain the triangular and tetrahedral numbers.
The boundary collapse, three times over
Formula (13) collapses to a single binomial coefficient at either end of the admissible range of k k k . In the lower regime this is immediate from the elementary convention. For 0 ≤ k ≤ s 0\le k\le s 0 ≤ k ≤ s and any j ≥ 1 j\ge1 j ≥ 1 we have j ( s + 1 ) ≥ s + 1 > k j(s+1)\ge s+1>k j ( s + 1 ) ≥ s + 1 > k , so k − j ( s + 1 ) + n − 1 < n − 1 k-j(s+1)+n-1<n-1 k − j ( s + 1 ) + n − 1 < n − 1 and the corresponding binomial vanishes by (6) . Only the j = 0 j=0 j = 0 term survives, giving
∑ j = 0 n − 1 ( − 1 ) j ( n j ) ( k − j ( s + 1 ) + n − 1 n − 1 ) = ( k + n − 1 n − 1 ) , 0 ≤ k ≤ s . (22) \sum_{j=0}^{n-1}(-1)^j\binom{n}{j}\binom{k-j(s+1)+n-1}{n-1}=\binom{k+n-1}{n-1},\qquad0\le k\le s. \tag*{(22)} j = 0 ∑ n − 1 ( − 1 ) j ( j n ) ( n − 1 k − j ( s + 1 ) + n − 1 ) = ( n − 1 k + n − 1 ) , 0 ≤ k ≤ s . (22)
In bi’snomial notation, equation (22) says that ( n k ) s = ( n + k − 1 k ) \binom{n}{k}_{s}=\binom{n+k-1}{k} ( k n ) s = ( k n + k − 1 ) for 0 ≤ k ≤ s 0\le k\le s 0 ≤ k ≤ s .
Belbachir, Bouroubi, and Khelladi [5 Corollary 4.2] give (22) ; Charalambides [13 Example 4.7] records the same boundary case. The Bell-polynomial and complement-bijection arguments below emphasize different aspects of the identity.
Bell-polynomial proof. Let B ν , n ( t 1 , t 2 , … ) B_{\nu,n}(t_1,t_2,\ldots) B ν , n ( t 1 , t 2 , … ) be the exponential partial Bell polynomials, defined by
1 n ! ( ∑ ℓ ≥ 1 t ℓ ℓ ! x ℓ ) n = ∑ ν ≥ n B ν , n x ν ν ! , n = 0 , 1 , 2 , … (23) \frac{1}{n!}\left(\sum_{\ell\geq1}\frac{t_\ell}{\ell!}x^\ell\right)^n=\sum_{\nu\geq n}B_{\nu,n}\frac{x^\nu}{\nu!},\qquad n=0,1,2,\ldots \tag*{(23)} n ! 1 ( ℓ ≥ 1 ∑ ℓ ! t ℓ x ℓ ) n = ν ≥ n ∑ B ν , n ν ! x ν , n = 0 , 1 , 2 , … (23)
Taking t ℓ = ℓ ! t_\ell=\ell! t ℓ = ℓ ! for 1 ≤ ℓ ≤ s + 1 1\leq\ell\leq s+1 1 ≤ ℓ ≤ s + 1 and t ℓ = 0 t_\ell=0 t ℓ = 0 otherwise turns the inner sum in (23) into x + x 2 + ⋯ + x s + 1 = x ( 1 + x + ⋯ + x s ) x+x^2+\cdots+x^{s+1}=x(1+x+\cdots+x^s) x + x 2 + ⋯ + x s + 1 = x ( 1 + x + ⋯ + x s ) , and comparing coefficients of x ν x^\nu x ν yields the connection formula [5 Theorem 4.1]
B ν , n ( 1 ! , 2 ! , … , ( s + 1 ) ! , 0 , … ) = ν ! n ! ( n ν − n ) s . (24) B_{\nu,n}(1!,2!,\ldots,(s+1)!,0,\ldots)=\frac{\nu!}{n!}\binom{n}{\nu-n}_{s}. \tag*{(24)} B ν , n ( 1 ! , 2 ! , … , ( s + 1 )! , 0 , … ) = n ! ν ! ( ν − n n ) s . (24)
With no truncation, the inner sum is x / ( 1 − x ) x/(1-x) x / ( 1 − x ) , and the same comparison gives, for ν ≥ n ≥ 1 \nu\geq n\geq1 ν ≥ n ≥ 1 , the classical evaluation by Lah numbers,
B ν , n ( 1 ! , 2 ! , 3 ! , … ) = ν ! n ! ( ν − 1 ν − n ) . (25) B_{\nu,n}(1!,2!,3!,\ldots)=\frac{\nu!}{n!}\binom{\nu-1}{\nu-n}. \tag*{(25)} B ν , n ( 1 ! , 2 ! , 3 ! , … ) = n ! ν ! ( ν − n ν − 1 ) . (25)
The coefficient of x ν x^\nu x ν in (23) involves only the products t ℓ 1 ⋯ t ℓ n t_{\ell_1}\cdots t_{\ell_n} t ℓ 1 ⋯ t ℓ n with ℓ 1 + ⋯ + ℓ n = ν \ell_1+\cdots+\ell_n=\nu ℓ 1 + ⋯ + ℓ n = ν and every ℓ i ≥ 1 \ell_i\geq1 ℓ i ≥ 1 , so that ℓ i ≤ ν − n + 1 \ell_i\leq\nu-n+1 ℓ i ≤ ν − n + 1 . Consequently, truncating the Bell-polynomial arguments after ( s + 1 ) ! (s+1)! ( s + 1 )! has no effect when s + 1 ≥ ν − n + 1 s+1\geq\nu-n+1 s + 1 ≥ ν − n + 1 . For s ≥ ν − n s\geq\nu-n s ≥ ν − n , the two evaluations therefore agree and ( n ν − n ) s = ( ν − 1 ν − n ) \binom{n}{\nu-n}_{s}=\binom{\nu-1}{\nu-n} ( ν − n n ) s = ( ν − n ν − 1 ) , which is (22) on setting k = ν − n k=\nu-n k = ν − n .
Bijection proof. Apply Proposition 4.1 to the complementary total n s − k ns-k n s − k . Since n s − ( n s − k ) = k ≤ s ns-(ns-k)=k\leq s n s − ( n s − k ) = k ≤ s , the proposition gives ( n n s − k ) s = ( k + n − 1 n − 1 ) \binom{n}{ns-k}_{s}=\binom{k+n-1}{n-1} ( n s − k n ) s = ( n − 1 k + n − 1 ) ; the symmetry relation (20) then yields (22) .
The symmetry relation reflects the lower boundary onto the upper boundary. Indeed, n s − k ∈ [ 0 , s ] ns-k\in[0,s] n s − k ∈ [ 0 , s ] precisely when k ∈ [ ( n − 1 ) s , n s ] k\in[(n-1)s,ns] k ∈ [( n − 1 ) s , n s ] . Applying (22) at n s − k ns-k n s − k therefore gives ( n k ) s = ( n s − k + n − 1 n − 1 ) \binom{n}{k}_{s}=\binom{ns-k+n-1}{n-1} ( k n ) s = ( n − 1 n s − k + n − 1 ) , that is,
∑ j = 0 n − 1 ( − 1 ) j ( n j ) ( k − j ( s + 1 ) + n − 1 n − 1 ) = ( n s − k + n − 1 n − 1 ) , ( n − 1 ) s ≤ k ≤ n s . (26) \sum_{j=0}^{n-1}(-1)^j\binom{n}{j}\binom{k-j(s+1)+n-1}{n-1}=\binom{ns-k+n-1}{n-1},\qquad(n-1)s\leq k\leq ns. \tag*{(26)} j = 0 ∑ n − 1 ( − 1 ) j ( j n ) ( n − 1 k − j ( s + 1 ) + n − 1 ) = ( n − 1 n s − k + n − 1 ) , ( n − 1 ) s ≤ k ≤ n s . (26)
In (22) , every term but one vanishes individually; in (26) , several terms cancel to leave the single figurate number on the right.
Example 4.2 (Three dice near the upper boundary). For three ordinary dice totaling 16, subtracting one from each face value gives ( n , s , k ) = ( 3 , 5 , 13 ) (n,s,k)=(3,5,13) ( n , s , k ) = ( 3 , 5 , 13 ) . The support-sharp inclusion–exclusion formula yields
( 3 13 ) 5 = ( 15 2 ) − 3 ( 9 2 ) + 3 ( 3 2 ) = 105 − 108 + 9 = 6. \binom{3}{13}_{5}=\binom{15}{2}-3\binom{9}{2}+3\binom{3}{2}=105-108+9=6. ( 13 3 ) 5 = ( 2 15 ) − 3 ( 2 9 ) + 3 ( 2 3 ) = 105 − 108 + 9 = 6.
Complement symmetry replaces k = 13 k=13 k = 13 by 15 − 13 = 2 15-13=2 15 − 13 = 2 , where the lower-boundary formula gives ( 3 2 ) 5 = ( 4 2 ) = 6 \binom{3}{2}_{5}=\binom{4}{2}=6 ( 2 3 ) 5 = ( 2 4 ) = 6 directly. The six dice outcomes are the three permutations of ( 6 , 6 , 4 ) (6,6,4) ( 6 , 6 , 4 ) and the three permutations of ( 6 , 5 , 5 ) (6,5,5) ( 6 , 5 , 5 ) . On the original dice, complementation sends each face value d i d_i d i to 7 − d i 7-d_i 7 − d i , pairing totals 16 and 5; each total has probability 6 / 6 3 = 1 / 36 6/6^3=1/36 6/ 6 3 = 1/36 .
Two consequences of the symmetry relation
At k = n s + 1 k=ns+1 k = n s + 1 , no bounded solution exists. The globally valid generating-function expansion obtained from (15) therefore sums to zero. For n ≥ 2 n\geq2 n ≥ 2 , its j = n j=n j = n term is ( − 1 ) n ( n n ) ( 0 n − 1 ) = 0 (-1)^n\binom{n}{n}\binom{0}{n-1}=0 ( − 1 ) n ( n n ) ( n − 1 0 ) = 0 , so the sum may be written through j = n − 1 j=n-1 j = n − 1 :
∑ j = 0 n − 1 ( − 1 ) j ( n j ) ( ( n − j ) ( s + 1 ) n − 1 ) = 0 , (27) \sum_{j=0}^{n-1}(-1)^j\binom{n}{j}\binom{(n-j)(s+1)}{n-1}=0, \tag*{(27)} j = 0 ∑ n − 1 ( − 1 ) j ( j n ) ( n − 1 ( n − j ) ( s + 1 ) ) = 0 , (27)
independently of s s s . At the nearby admissible value k = n s − 1 k=ns-1 k = n s − 1 , for s ≥ 1 s\geq1 s ≥ 1 , exactly n n n solutions remain — one for each choice of which k i k_i k i drops to $s-1 while the rest stay at s s s — and hence
∑ j = 0 n − 1 ( − 1 ) j ( n j ) ( ( n − j ) ( s + 1 ) − 2 n − 1 ) = n , (28) \sum_{j=0}^{n-1}(-1)^j\binom{n}{j}\binom{(n-j)(s+1)-2}{n-1}=n, \tag*{(28)} j = 0 ∑ n − 1 ( − 1 ) j ( j n ) ( n − 1 ( n − j ) ( s + 1 ) − 2 ) = n , (28)
again independently of s s s . West [43 Example 4.1.6] derives both identities by the same inclusion–exclusion argument.
Complement symmetry also shortens the support-sharp inclusion–exclusion sum.
Corollary 4.4. For 0 ≤ k ≤ n s 0 \le k \le ns 0 ≤ k ≤ n s , let k ∗ = min ( k , n s − k ) k^*=\min(k,ns-k) k ∗ = min ( k , n s − k ) denote the distance from k k k to the nearer endpoint of the support. Then
( n k ) s = ∑ j = 0 ⌊ k ∗ / ( s + 1 ) ⌋ ( − 1 ) j ( n j ) ( k ∗ − j ( s + 1 ) + n − 1 n − 1 ) , (29) \binom{n}{k}_s=\sum_{j=0}^{\lfloor k^*/(s+1)\rfloor}(-1)^j\binom{n}{j}\binom{k^*-j(s+1)+n-1}{n-1}, \tag*{(29)} ( k n ) s = j = 0 ∑ ⌊ k ∗ / ( s + 1 )⌋ ( − 1 ) j ( j n ) ( n − 1 k ∗ − j ( s + 1 ) + n − 1 ) , (29) a sum of ⌊ k ∗ / ( s + 1 ) ⌋ + 1 \lfloor k^*/(s+1)\rfloor+1 ⌊ k ∗ / ( s + 1 )⌋ + 1 terms.
Proof. Apply (14) at k ∗ k^* k ∗ and use (20) .
Since k ∗ ≤ n s / 2 k^* \le ns/2 k ∗ ≤ n s /2 , the number of terms in (29) never exceeds ⌊ n s / 2 ( s + 1 ) ⌋ + 1 \lfloor ns/2(s+1)\rfloor+1 ⌊ n s /2 ( s + 1 )⌋ + 1 , roughly half the maximum number of terms in (14) . At k = n s k=ns k = n s , equation (29) has one term, whereas the direct support-sharp form has ⌊ n s / ( s + 1 ) ⌋ + 1 \lfloor ns/(s+1)\rfloor+1 ⌊ n s / ( s + 1 )⌋ + 1 terms. Finally, ⌊ k ∗ / ( s + 1 ) ⌋ = 0 \lfloor k^*/(s+1)\rfloor=0 ⌊ k ∗ / ( s + 1 )⌋ = 0 exactly when k ∗ ≤ s k^* \le s k ∗ ≤ s . This condition describes the lower range 0 ≤ k ≤ s 0 \le k \le s 0 ≤ k ≤ s and its reflection ( n − 1 ) s ≤ k ≤ n s (n-1)s \le k \le ns ( n − 1 ) s ≤ k ≤ n s , yielding (22) and (26) .
Example 4.5 (Shorter sums through complementation). For ( n , s ) = ( 12 , 3 ) (n,s)=(12,3) ( n , s ) = ( 12 , 3 ) , the support is 0 ≤ k ≤ 36 0 \le k \le36 0 ≤ k ≤ 36 . Evaluating each of the 37 coefficients separately by the direct support-sharp formula (14) requires 190 summands, whereas using the complementary total in (29) requires 105:
∑ k = 0 36 ( ⌊ k 4 ⌋ + 1 ) = 190 , ∑ k = 0 36 ( ⌊ min ( k , 36 − k ) 4 ⌋ + 1 ) = 105. \sum_{k=0}^{36}\left(\left\lfloor\frac{k}{4}\right\rfloor+1\right)=190,\qquad
\sum_{k=0}^{36}\left(\left\lfloor\frac{\min(k,36-k)}{4}\right\rfloor+1\right)=105. k = 0 ∑ 36 ( ⌊ 4 k ⌋ + 1 ) = 190 , k = 0 ∑ 36 ( ⌊ 4 min ( k , 36 − k ) ⌋ + 1 ) = 105.
The inhomogeneous boundary regimes
Let s min = min ( s 1 , … , s n ) s_{\min}=\min(s_1,\ldots,s_n) s m i n = min ( s 1 , … , s n ) . For arbitrary bounds, every solution in the lower range 0 ≤ k ≤ s min 0 \le k \le s_{\min} 0 ≤ k ≤ s m i n satisfies k i ≤ k ≤ s i k_i \le k \le s_i k i ≤ k ≤ s i , so that
R s ( k ) = ( k + n − 1 n − 1 ) . (30) R_s(k)=\binom{k+n-1}{n-1}. \tag*{(30)} R s ( k ) = ( n − 1 k + n − 1 ) . (30)
In the upper range N − s min ≤ k ≤ N N-s_{\min} \le k \le N N − s m i n ≤ k ≤ N , the complement bijection gives
R s ( k ) = ( N − k + n − 1 n − 1 ) . (31) R_s(k)=\binom{N-k+n-1}{n-1}. \tag*{(31)} R s ( k ) = ( n − 1 N − k + n − 1 ) . (31)
The complement map preserves the middle range s min < k < N − s min s_{\min}<k<N-s_{\min} s m i n < k < N − s m i n , but neither the bounds k i ≤ s i k_i \le s_i k i ≤ s i nor the complementary bounds b i ≤ s i b_i \le s_i b i ≤ s i are automatic there. By Proposition 4.1, and by the same argument applied to the k i k_i k i themselves, each one-term formula holds exactly on its own boundary range, so neither holds in the middle range. Equating (30) –(31) with (11) produces inhomogeneous analogues of (22) and (26) . The alternating sums no longer share the factor ( n j ) \binom{n}{j} ( j n ) , but the boundary values remain simplex, or figurate, numbers.
A probabilistic interpretation
Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be independent and uniform on { 0 , 1 , … , s } \{0,1,\ldots,s\} { 0 , 1 , … , s } , and write U s = 1 s + 1 ( δ 0 + ⋯ + δ s ) U_s=\frac{1}{s+1}(\delta_0+\cdots+\delta_s) U s = s + 1 1 ( δ 0 + ⋯ + δ s ) for their common distribution. Set S n = X 1 + ⋯ + X n S_n=X_1+\cdots+X_n S n = X 1 + ⋯ + X n . Normalizing the coefficients in (3) gives the probability mass function of S n S_n S n :
P ( S n = k ) = ( n k ) s ( s + 1 ) n . (32) \mathbb{P}(S_n=k)=\frac{\binom{n}{k}_s}{(s+1)^n}. \tag*{(32)} P ( S n = k ) = ( s + 1 ) n ( k n ) s . (32)
Belbachir, Bouroubi, and Khelladi [5 Corollary 5.1] give (32) , which recovers de Moivre’s dice model in probabilistic form. The involution X i ↦ s − X i X_i\mapsto s-X_i X i ↦ s − X i sends S n S_n S n to n s − S n ns-S_n n s − S n , so the distribution is symmetric about n s / 2 ns/2 n s /2 , in agreement with (20) .
Moments
Belbachir, Bouroubi, and Khelladi [5 Corollary 5.2] evaluate the moments of S n S_n S n ; the mean and variance follow directly from independence. A single draw from U s U_s U s has mean s / 2 s/2 s /2 and variance ( ( s + 1 ) 2 − 1 ) / 12 ((s+1)^2-1)/12 (( s + 1 ) 2 − 1 ) /12 , so
E ( S n ) = n s 2 , Var ( S n ) = n s ( s + 2 ) 12 = : τ n , s 2 . (33) \mathbb{E}(S_n)=\frac{ns}{2},\qquad\operatorname{Var}(S_n)=\frac{ns(s+2)}{12}=:\tau_{n,s}^2. \tag*{(33)} E ( S n ) = 2 n s , Var ( S n ) = 12 n s ( s + 2 ) =: τ n , s 2 . (33)
Symmetry about n s / 2 ns/2 n s /2 makes every odd central moment vanish. For s = 1 s=1 s = 1 , the variance becomes the binomial value n / 4 n/4 n /4 . Under the spin substitution s = 2 σ s=2\sigma s = 2 σ of § 7.1 , it becomes τ n , 2 σ 2 = n σ ( σ + 1 ) / 3 \tau_{n,2\sigma}^2=n\sigma(\sigma+1)/3 τ n , 2 σ 2 = nσ ( σ + 1 ) /3 , the familiar variance of the total magnetization of n n n free spins.
Mode and log-concavity
For every n ≥ 1 n\ge1 n ≥ 1 and s ≥ 0 s\ge0 s ≥ 0 , the coefficient sequence k ↦ ( n k ) s k\mapsto\binom{n}{k}_s k ↦ ( k n ) s is the n n n -fold convolution of ( 1 , 1 , … , 1 ) (1,1,\ldots,1) ( 1 , 1 , … , 1 ) . This base sequence is log-concave with no internal zeros, and convolution preserves these properties [8 ] . Hence the coefficient sequence is log-concave and unimodal. Together with symmetry, unimodality places a mode at the center. Belbachir [3 ] gives the exact statement
max 0 ≤ k ≤ n s ( n k ) s = ( n ⌊ ( n s + 1 ) / 2 ⌋ ) s . (34) \max_{0\le k\le ns}\binom{n}{k}_s=\binom{n}{\lfloor(ns+1)/2\rfloor}_s. \tag*{(34)} 0 ≤ k ≤ n s max ( k n ) s = ( ⌊( n s + 1 ) /2 ⌋ n ) s . (34)
Deshouillers [18 ] attributes the location of this maximum at ⌊ n s / 2 ⌋ \lfloor ns/2\rfloor ⌊ n s /2 ⌋ to G. Lévy’s 1971 thesis. For n ≥ 2 n\ge2 n ≥ 2 and s ≥ 1 s\ge1 s ≥ 1 , the central mode is unique when n s ns n s is even and there are exactly two central modes when n s ns n s is odd. For n = 1 n=1 n = 1 , all s + 1 s+1 s + 1 coefficients equal 1; for s = 0 s=0 s = 0 , the only coefficient is at k = 0 k=0 k = 0 .
Normal approximation and the central coefficients
For fixed s ≥ 1 s\ge1 s ≥ 1 , the distribution U s U_s U s has lattice span 1, since its support contains consecutive integers, and moments of every order, since that support is bounded. Maximal span is precisely the condition for the uniform lattice local limit theorem [34 Ch. VII, Theorem 1] , and the third moment yields a version with an explicit rate [34 Ch. VII, Theorem 6] . With φ \varphi φ denoting the standard normal density and τ n , s \tau_{n,s} τ n , s defined in (33) ,
( n k ) s ( s + 1 ) n = 1 τ n , s φ ( k − n s / 2 τ n , s ) + O ( τ n , s − 2 ) , (35) \frac{\binom{n}{k}_s}{(s+1)^n}=\frac{1}{\tau_{n,s}}\varphi\left(\frac{k-ns/2}{\tau_{n,s}}\right)+O(\tau_{n,s}^{-2}), \tag*{(35)} ( s + 1 ) n ( k n ) s = τ n , s 1 φ ( τ n , s k − n s /2 ) + O ( τ n , s − 2 ) , (35)
uniformly in k k k as n → ∞ n\to\infty n → ∞ .
For k = ⌊ n s / 2 ⌋ k=\lfloor ns/2\rfloor k = ⌊ n s /2 ⌋ , the distance ∣ k − n s / 2 ∣ \lvert k-ns/2\rvert ∣ k − n s /2 ∣ is at most 1 / 2 1/2 1/2 , so the argument of φ \varphi φ in (35) is at most 1 / 2 τ n , s 1/2\tau_{n,s} 1/2 τ n , s , and φ \varphi φ may be replaced there by φ ( 0 ) = 1 / 2 π \varphi(0)=1/\sqrt{2\pi} φ ( 0 ) = 1/ 2 π at the cost of a relative error O ( τ n , s − 2 ) O(\tau_{n,s}^{-2}) O ( τ n , s − 2 ) . The normalized central coefficient is therefore φ ( 0 ) / τ n , s + O ( τ n , s − 2 ) \varphi(0)/\tau_{n,s}+O(\tau_{n,s}^{-2}) φ ( 0 ) / τ n , s + O ( τ n , s − 2 ) , with relative error O ( n − 1 / 2 ) O(n^{-1/2}) O ( n − 1/2 ) , and substituting τ n , s \tau_{n,s} τ n , s from (33) gives
( n ⌊ n s / 2 ⌋ ) s ∼ ( s + 1 ) n 6 π n s ( s + 2 ) . (36) \binom{n}{\lfloor ns/2\rfloor}_s\sim(s+1)^n\sqrt{\frac{6}{\pi ns(s+2)}}. \tag*{(36)} ( ⌊ n s /2 ⌋ n ) s ∼ ( s + 1 ) n π n s ( s + 2 ) 6 . (36)
The central coefficient therefore accounts for a Θ ( n − 1 / 2 ) \Theta(n^{-1/2}) Θ ( n − 1/2 ) fraction of the total mass ( s + 1 ) n (s+1)^n ( s + 1 ) n . Since τ n , s = Θ ( n ) \tau_{n,s}=\Theta(\sqrt{n}) τ n , s = Θ ( n ) while the support has width n s = Θ ( n ) ns=\Theta(n) n s = Θ ( n ) , the mass concentrates on a vanishing fraction of the support. Equation (36) also estimates the cardinality of the central rank layer used in § 7.4 .
With p = s + 1 p=s+1 p = s + 1 , so that ( n k ) p − 1 \binom{n}{k}_{p-1} ( k n ) p − 1 is the p p p -nomial coefficient of order n n n , equation (36) becomes
max k ( n k ) p − 1 ∼ p n 6 π n ( p 2 − 1 ) . (37) \max_k\binom{n}{k}_{p-1}\sim p^n\sqrt{\frac{6}{\pi n(p^2-1)}}. \tag*{(37)} k max ( k n ) p − 1 ∼ p n π n ( p 2 − 1 ) 6 . (37)
The asymptotic formula (37) was conjectured by G. Lévy and proved by Deshouillers [18 ] . Eger [20 ] later recovered the same leading term by a lattice local-limit argument under the name central extended binomial coefficients .
After division by ( s + 1 ) n (s+1)^n ( s + 1 ) n , the adjacent central difference is of order τ n , s − 3 \tau_{n,s}^{-3} τ n , s − 3 , whereas the uniform error in (35) is only O ( τ n , s − 2 ) O(\tau_{n,s}^{-2}) O ( τ n , s − 2 ) . Subtracting the approximation at two adjacent lattice points therefore does not control the difference. Petrov [34, Ch. VII, Theorem 13] refines the lattice local limit theorem to an asymptotic expansion with a uniform remainder of arbitrary order in n − 1 / 2 n^{-1/2} n − 1/2 , since the bounded support of U s U_s U s guarantees the required moments. Neuschel [32 ] gives a complete local expansion with uniform error terms; alternatively, one may use the midpoint-anchored saddle-point expansion of [29 ] . Petrov’s expansion through order n − 1 n^{-1} n − 1 already suffices. With x = ( k − n s / 2 ) / τ n , s x=(k-ns/2)/\tau_{n,s} x = ( k − n s /2 ) / τ n , s , and with κ 4 = − ( ( s + 1 ) 4 − 1 ) / 120 \kappa_4=-((s+1)^4-1)/120 κ 4 = − (( s + 1 ) 4 − 1 ) /120 the fourth cumulant of U s U_s U s , it reads
τ n , s ( n k ) s ( s + 1 ) n = φ ( x ) [ 1 + n κ 4 24 τ n , s 4 ( x 4 − 6 x 2 + 3 ) ] + o ( n − 1 ) , (38) \frac{\tau_{n,s}\binom{n}{k}_s}{(s+1)^n}=\varphi(x)\left[1+\frac{n\kappa_4}{24\tau_{n,s}^4}(x^4-6x^2+3)\right]+o(n^{-1}), \tag*{(38)} ( s + 1 ) n τ n , s ( k n ) s = φ ( x ) [ 1 + 24 τ n , s 4 n κ 4 ( x 4 − 6 x 2 + 3 ) ] + o ( n − 1 ) , (38)
uniformly in k k k . The term of order n − 1 / 2 n^{-1/2} n − 1/2 is proportional to the third cumulant of U s U_s U s and vanishes by symmetry. Had it survived, it would contribute to the adjacent difference at the same order as the Gaussian term. The correction that remains, φ ( x ) \varphi(x) φ ( x ) times the O ( n − 1 ) O(n^{-1}) O ( n − 1 ) polynomial in the bracket, is even in x x x , so between x = 0 x=0 x = 0 and x = 1 / τ n , s x=1/\tau_{n,s} x = 1/ τ n , s , that is, between k = n s / 2 k=ns/2 k = n s /2 and k = n s / 2 + 1 k=ns/2+1 k = n s /2 + 1 , it changes by only O ( n − 1 τ n , s − 2 ) O(n^{-1}\tau_{n,s}^{-2}) O ( n − 1 τ n , s − 2 ) . The Gaussian term changes by
φ ( 0 ) − φ ( 1 / τ n , s ) = φ ( 0 ) ( 1 − e − 1 / ( 2 τ n , s 2 ) ) = φ ( 0 ) 2 τ n , s 2 + O ( τ n , s − 4 ) . (39) \varphi(0)-\varphi(1/\tau_{n,s})=\varphi(0)(1-e^{-1/(2\tau_{n,s}^2)})=\frac{\varphi(0)}{2\tau_{n,s}^2}+O(\tau_{n,s}^{-4}). \tag*{(39)} φ ( 0 ) − φ ( 1/ τ n , s ) = φ ( 0 ) ( 1 − e − 1/ ( 2 τ n , s 2 ) ) = 2 τ n , s 2 φ ( 0 ) + O ( τ n , s − 4 ) . (39)
Since τ n , s 2 \tau_{n,s}^2 τ n , s 2 is of order n n n , every other contribution is o ( τ n , s − 2 ) o(\tau_{n,s}^{-2}) o ( τ n , s − 2 ) , and dividing by τ n , s \tau_{n,s} τ n , s gives, for fixed s s s and even n s ns n s ,
( n n s / 2 ) s − ( n n s / 2 + 1 ) s ∼ ( s + 1 ) n 2 2 π τ n , s 3 , n → ∞ . (40) \binom{n}{ns/2}_s-\binom{n}{ns/2+1}_s\sim\frac{(s+1)^n}{2\sqrt{2\pi}\tau_{n,s}^3},\qquad n\to\infty. \tag*{(40)} ( n s /2 n ) s − ( n s /2 + 1 n ) s ∼ 2 2 π τ n , s 3 ( s + 1 ) n , n → ∞. (40)
Thus the normalized central difference is Θ ( n − 3 / 2 ) \Theta(n^{-3/2}) Θ ( n − 3/2 ) , one factor of n − 1 n^{-1} n − 1 below the central probability mass, which is Θ ( n − 1 / 2 ) \Theta(n^{-1/2}) Θ ( n − 1/2 ) . This extra factor is characteristic of the Catalan-type first differences considered below.
Under the spin dictionary of § 7.1 , let d n , σ ( J ) d_{n,\sigma}^{(J)} d n , σ ( J ) denote the multiplicity of the spin-J J J irreducible representation in the n n n -fold tensor product of spin-σ \sigma σ representations, as defined in (59) . In the central regime J = O ( n ) J=O(\sqrt{n}) J = O ( n ) , these multiplicities have a Maxwell-type profile, a Gaussian in J / n J/\sqrt{n} J / n multiplied by 2 J + 1 2J+1 2 J + 1 . Polychronakos and Sfetsos [35 ] obtained this profile through random walks, while Curtright, Van Kortryk, and Zachos [15 ] derived it from SU(2) characters.
The midpoint-anchored saddle-point expansion of [29 ] recovers the central profile and extends it to a large-deviation asymptotic with relative error O ( n − 1 ) O(n^{-1}) O ( n − 1 ) , uniformly for fixed σ \sigma σ and any ϵ > 0 \epsilon>0 ϵ > 0 throughout 0 ≤ ( J + 1 2 ) / n ≤ σ − ϵ 0\le(J+\frac{1}{2})/n\le\sigma-\epsilon 0 ≤ ( J + 2 1 ) / n ≤ σ − ϵ . Its central specialization recovers the leading fixed-J J J form of Curtright, Van Kortryk, and Zachos [15 ] and the large-J J J central form of Polychronakos and Sfetsos [35 ] . When n σ ∈ Z n\sigma\in\mathbb{Z} nσ ∈ Z , equation (40) with s = 2 σ s=2\sigma s = 2 σ is its J = 0 J=0 J = 0 specialization and yields the singlet asymptotic in the following example.
Example 5.1. Take n = 2 ν n=2\nu n = 2 ν spin-2 particles. Then s = 4 s=4 s = 4 , τ 2 ν , 4 2 = 2 ν ⋅ 4 ⋅ 6 / 12 = 4 ν \tau_{2\nu,4}^2=2\nu\cdot4\cdot6/12=4\nu τ 2 ν , 4 2 = 2 ν ⋅ 4 ⋅ 6/12 = 4 ν , and 2 2 π τ 2 ν , 4 3 = 16 2 π ν 3 / 2 2\sqrt{2\pi}\tau_{2\nu,4}^3=16\sqrt{2\pi}\nu^{3/2} 2 2 π τ 2 ν , 4 3 = 16 2 π ν 3/2 , so equation (40) gives
d 2 ν , 2 ( 0 ) ∼ 5 2 ν 16 2 π ν 3 / 2 . (41) d_{2\nu,2}^{(0)}\sim\frac{5^{2\nu}}{16\sqrt{2\pi}\nu^{3/2}}. \tag*{(41)} d 2 ν , 2 ( 0 ) ∼ 16 2 π ν 3/2 5 2 ν . (41)
This recovers the leading behavior of sequence A007043 in Table 4 . Taking σ = 1 2 \sigma=\frac{1}{2} σ = 2 1 instead, τ 2 ν , 2 2 = ν / 2 \tau_{2\nu,2}^2=\nu/2 τ 2 ν , 2 2 = ν /2 , and the same computation gives the classical Catalan asymptotic 4 ν / π ν 3 4^\nu/\sqrt{\pi\nu^3} 4 ν / π ν 3 .
Table 4. The singlet sequences (63) and their OEIS entries. For σ = 1 \sigma= 1 σ = 1 and σ = 2 \sigma= 2 σ = 2 , the table lists the even-index subsequence of the cited entry.
Corollary 5.2 (Central asymptotic corrections). For fixed s ≥ 1 s\ge1 s ≥ 1 and even n s ns n s , as n → ∞ n\to\infty n → ∞ ,
( n n s / 2 ) s = ( s + 1 ) n 2 π τ n , s [ 1 − 3 ( ( s + 1 ) 2 + 1 ) 20 ( ( s + 1 ) 2 − 1 ) n + O ( n − 2 ) ] , (42) \binom{n}{ns/2}_s=\frac{(s+1)^n}{\sqrt{2\pi}\tau_{n,s}}\left[1-\frac{3((s+1)^2+1)}{20((s+1)^2-1)n}+O(n^{-2})\right], \tag*{(42)} ( n s /2 n ) s = 2 π τ n , s ( s + 1 ) n [ 1 − 20 (( s + 1 ) 2 − 1 ) n 3 (( s + 1 ) 2 + 1 ) + O ( n − 2 ) ] , (42) ( n n s / 2 ) s − ( n n s / 2 + 1 ) s = ( s + 1 ) n 2 2 π τ n , s 3 [ 1 − 3 ( ( s + 1 ) 2 + 5 ) 4 ( ( s + 1 ) 2 − 1 ) n + O ( n − 2 ) ] . (43) \binom{n}{ns/2}_s-\binom{n}{ns/2+1}_s=\frac{(s+1)^n}{2\sqrt{2\pi}\tau_{n,s}^3}\left[1-\frac{3((s+1)^2+5)}{4((s+1)^2-1)n}+O(n^{-2})\right]. \tag*{(43)} ( n s /2 n ) s − ( n s /2 + 1 n ) s = 2 2 π τ n , s 3 ( s + 1 ) n [ 1 − 4 (( s + 1 ) 2 − 1 ) n 3 (( s + 1 ) 2 + 5 ) + O ( n − 2 ) ] . (43)
Proof. Apply Neuschel’s uniform local expansion [32 ] through order n − 3 n^{-3} n − 3 . Its correction terms are smooth and even, so their differences between x = 0 x=0 x = 0 and x = 1 / τ n , s x=1/\tau_{n,s} x = 1/ τ n , s gain a factor O ( n − 1 ) O(n^{-1}) O ( n − 1 ) ; the uniform remainder is o ( n − 3 ) o(n^{-3}) o ( n − 3 ) . The leading difference of the rescaled probabilities in (38) is of order n − 1 n^{-1} n − 1 , so passing to a relative remainder amplifies the uniform remainder by a factor of order n n n . With κ 2 = s ( s + 2 ) / 12 \kappa_2=s(s+2)/12 κ 2 = s ( s + 2 ) /12 and λ 4 = κ 4 / κ 2 2 = − 6 ( ( s + 1 ) 2 + 1 ) / 5 ( ( s + 1 ) 2 − 1 ) \lambda_4=\kappa_4/\kappa_2^2=-6((s+1)^2+1)/5((s+1)^2-1) λ 4 = κ 4 / κ 2 2 = − 6 (( s + 1 ) 2 + 1 ) /5 (( s + 1 ) 2 − 1 ) , the relative corrections are λ 4 / 8 n \lambda_4/8n λ 4 /8 n and 5 λ 4 / 8 n − 1 / 4 τ n , s 2 5\lambda_4/8n-1/4\tau_{n,s}^2 5 λ 4 /8 n − 1/4 τ n , s 2 , respectively.
Under s = 2 σ s=2\sigma s = 2 σ , equation (43) recovers the general singlet correction of Curtright, Van Kortryk, and Zachos [15 eq. (33)] ; for s = 2 s=2 s = 2 , its 1 / n 1/n 1/ n coefficient is − 21 / 16 -21/16 − 21/16 .
Remark 5.3 (Higher-order corrections). Carrying the same expansion through order n − 4 n^{-4} n − 4 gives the next terms in the brackets of (42) and (43) , respectively,
− 13 ( s + 1 ) 4 + 134 ( s + 1 ) 2 − 13 1120 ( ( s + 1 ) 2 − 1 ) 2 n 2 , 29 ( s + 1 ) 4 + 1058 ( s + 1 ) 2 + 1829 160 ( ( s + 1 ) 2 − 1 ) 2 n 2 . (44) \frac{-13(s+1)^4+134(s+1)^2-13}{1120((s+1)^2-1)^2n^2}, \qquad\frac{29(s+1)^4+1058(s+1)^2+1829}{160((s+1)^2-1)^2n^2}. \tag*{(44)} 1120 (( s + 1 ) 2 − 1 ) 2 n 2 − 13 ( s + 1 ) 4 + 134 ( s + 1 ) 2 − 13 , 160 (( s + 1 ) 2 − 1 ) 2 n 2 29 ( s + 1 ) 4 + 1058 ( s + 1 ) 2 + 1829 . (44)
With these terms retained, both remainders improve to O ( n − 3 ) O(n^{-3}) O ( n − 3 ) .
Remark 5.4 (Central coefficients and nonnegative walks). For fixed s ≥ 1 s\ge1 s ≥ 1 , the centered sums T j = S j − j s / 2 T_j=S_j-js/2 T j = S j − j s /2 form a symmetric random walk. Put u 0 , s = 1 u_{0,s}=1 u 0 , s = 1 and u n , s = P ( T 1 ≥ 0 , … , T n ≥ 0 ) u_{n,s}=\mathbb{P}(T_1\ge0,\ldots,T_n\ge0) u n , s = P ( T 1 ≥ 0 , … , T n ≥ 0 ) . Its return probabilities are
p m , s = P ( T m = 0 ) = { ( m m s / 2 ) ( s + 1 ) m , m s even , 0 , m s odd . p_{m,s}=\mathbb{P}(T_m=0)=
\begin{cases}
\dfrac{\binom{m}{ms/2}}{(s+1)^m}, & ms\text{ even},\\
0, & ms\text{ odd}.
\end{cases} p m , s = P ( T m = 0 ) = ⎩ ⎨ ⎧ ( s + 1 ) m ( m s /2 m ) , 0 , m s even , m s odd .
The generalized Sparre Andersen identity, valid also for discrete jumps [31 §III.2] , gives
∑ n ≥ 0 u n , s z n = exp ( ∑ m ≥ 1 z m m P ( T m ≥ 0 ) ) = 1 1 − z exp ( 1 2 ∑ m ≥ 1 p m , s z m m ) , ∣ z ∣ < 1. (45) \sum_{n\ge0}u_{n,s}z^n=\exp\left(\sum_{m\ge1}\frac{z^m}{m}\mathbb{P}(T_m\ge0)\right)=\frac{1}{\sqrt{1-z}}\exp\left(\frac{1}{2}\sum_{m\ge1}\frac{p_{m,s}z^m}{m}\right),\qquad|z|<1. \tag*{(45)} n ≥ 0 ∑ u n , s z n = exp ( m ≥ 1 ∑ m z m P ( T m ≥ 0 ) ) = 1 − z 1 exp ( 2 1 m ≥ 1 ∑ m p m , s z m ) , ∣ z ∣ < 1. (45)
where symmetry gives P ( T m ≥ 0 ) = ( 1 + p m , s ) / 2 \mathbb{P}(T_m\ge0)=(1+p_{m,s})/2 P ( T m ≥ 0 ) = ( 1 + p m , s ) /2 . Thus the central coefficients determine the enumeration ( s + 1 ) n u n , s (s+1)^n u_{n,s} ( s + 1 ) n u n , s of words ( x 1 , … , x n ) ∈ { 0 , … , s } n (x_1,\ldots,x_n)\in\{0,\ldots,s\}^n ( x 1 , … , x n ) ∈ { 0 , … , s } n for which every prefix satisfies x 1 + ⋯ + x j ≥ j s / 2 x_1+\cdots+x_j\ge js/2 x 1 + ⋯ + x j ≥ j s /2 . For s = 1 s=1 s = 1 , the reflection principle gives 2 n u n , 1 = ( n ⌊ n / 2 ⌋ ) 2^n u_{n,1}=\binom{n}{\lfloor n/2\rfloor} 2 n u n , 1 = ( ⌊ n /2 ⌋ n ) . The return term in (45) retains the distinction between weak and strict positivity on the lattice.
Products of chains and first differences
Rank layers and symmetric chains
Consider the product
P s = ∏ i = 1 n { 0 , 1 , … , s i } (46) P_s=\prod_{i=1}^{n}\{0,1,\ldots,s_i\} \tag*{(46)} P s = i = 1 ∏ n { 0 , 1 , … , s i } (46)
with the componentwise order and the rank function ρ ( k 1 , … , k n ) = k 1 + ⋯ + k n \rho(k_1,\ldots,k_n)=k_1+\cdots+k_n ρ ( k 1 , … , k n ) = k 1 + ⋯ + k n . Its rank-k k k elements are precisely the bounded compositions in (1), so the rank-k k k layer has cardinality R s ( k ) R_s(k) R s ( k ) . In the homogeneous case, the rank generating polynomial is ( 1 + x + ⋯ + x s ) n (1+x+\cdots+x^s)^n ( 1 + x + ⋯ + x s ) n .
A saturated chain in P s P_s P s is symmetric if the ranks of its first and last elements sum to N N N . De Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk [17 ] proved that every finite product of chains admits a partition into symmetric chains, or a symmetric chain decomposition. Stanley [41 ] established the connection between the hard Lefschetz theorem and Sperner properties. Proctor [36 ] gave a linear realization through an s l ( 2 , C ) \mathfrak{sl}(2,\mathbb{C}) sl ( 2 , C ) action whose raising operator has maximal rank between consecutive layers; this yields unimodality and the Sperner property. See Srinivasan [40 ] for a modern account.
The de Bruijn–Tengbergen–Kruyswijk construction is inductive. Given a symmetric chain decomposition of P ( s 1 , … , s n − 1 ) P_{(s_1,\ldots,s_{n-1})} P ( s 1 , … , s n − 1 ) , let C = { c 0 < c 1 < ⋯ < c a − 1 } C=\{c_0<c_1<\cdots<c_{a-1}\} C = { c 0 < c 1 < ⋯ < c a − 1 } be one of its chains and put b = s n + 1 b=s_n+1 b = s n + 1 . Symmetry of C C C means that ρ ( c 0 ) + ρ ( c a − 1 ) = N − s n \rho(c_0)+\rho(c_{a-1})=N-s_n ρ ( c 0 ) + ρ ( c a − 1 ) = N − s n . The product C × { 0 , … , s n } C\times\{0,\ldots,s_n\} C × { 0 , … , s n } is an a × b a\times b a × b grid, and its outer hook
( c 0 , 0 ) < ( c 1 , 0 ) < ⋯ < ( c a − 1 , 0 ) < ( c a − 1 , 1 ) < ⋯ < ( c a − 1 , s n ) (47) (c_0,0)<(c_1,0)<\cdots<(c_{a-1},0)<(c_{a-1},1)<\cdots<(c_{a-1},s_n) \tag*{(47)} ( c 0 , 0 ) < ( c 1 , 0 ) < ⋯ < ( c a − 1 , 0 ) < ( c a − 1 , 1 ) < ⋯ < ( c a − 1 , s n ) (47)
is a saturated chain with a + b − 1 a+b-1 a + b − 1 elements. Its end ranks ρ ( c 0 ) \rho(c_0) ρ ( c 0 ) and ρ ( c a − 1 ) + s n \rho(c_{a-1})+s_n ρ ( c a − 1 ) + s n sum to N N N , so it is symmetric. Removing it leaves the ( a − 1 ) × ( b − 1 ) (a-1) \times(b-1) ( a − 1 ) × ( b − 1 ) grid { c 0 , … , c a − 2 } × { 1 , … , s n } \{c_0,\ldots,c_{a-2}\} \times\{1,\ldots,s_n\} { c 0 , … , c a − 2 } × { 1 , … , s n } , whose end ranks ρ ( c 0 ) + 1 \rho(c_0)+1 ρ ( c 0 ) + 1 and ρ ( c a − 1 ) + s n − 1 \rho(c_{a-1})+s_n-1 ρ ( c a − 1 ) + s n − 1 again sum to N N N . Iteration produces min { a , b } \min\{a,b\} min { a , b } symmetric chains of lengths
a + b − 1 , a + b − 3 , … , ∣ a − b ∣ + 1. (48) a+b-1,\qquad a+b-3,\qquad\ldots,\qquad|a-b|+1. \tag*{(48)} a + b − 1 , a + b − 3 , … , ∣ a − b ∣ + 1. (48)
Figure 1 displays the 5 × 4 5 \times4 5 × 4 case beside the Clebsch–Gordan decomposition with the same dimension profile.
Figure 1. Nested-hook decomposition of a 5 × 4 5 \times4 5 × 4 product grid. The four symmetric saturated chains have lengths 8, 6, 4, 2. Since 5 = 2 ( 2 ) + 1 5 = 2(2) + 1 5 = 2 ( 2 ) + 1 and 4 = 2 ( 3 / 2 ) + 1 4 = 2(3/2) + 1 4 = 2 ( 3/2 ) + 1 , these four chain lengths are the dimensions of the Clebsch–Gordan constituents displayed on the right. The four chain lengths and the four constituent dimensions coincide as multisets.
Starting from the decomposition of the empty product into a single one-element chain and applying this nested-hook split to every chain at each step i = 1 , … , n i=1,\ldots,n i = 1 , … , n yields a symmetric chain decomposition of P s P_s P s .
If k < N / 2 k<N/2 k < N /2 , every symmetric chain that meets rank k k k continues through rank k + 1 k+1 k + 1 , because it runs from some rank c ≤ k c\leq k c ≤ k to the rank N − c ≥ N − k > k N-c\geq N-k>k N − c ≥ N − k > k . Sending each rank-k k k element to its successor on the chain therefore injects the rank-k k k layer into the rank-( k + 1 ) (k+1) ( k + 1 ) layer and proves unimodality. Reversing every chain gives a bijection between ranks k k k and N − k N-k N − k , recovering symmetry. Moreover, every symmetric chain meets rank ⌊ N / 2 ⌋ \lfloor N/2\rfloor ⌊ N /2 ⌋ exactly once, so the number of chains equals R s ( ⌊ N / 2 ⌋ ) R_s(\lfloor N/2\rfloor) R s (⌊ N /2 ⌋) . Since an antichain meets each chain in at most one element, a central rank layer is a largest antichain. This is the Sperner property used in the coding application of § 7.4 .
The same decomposition proves the strong Sperner property. Let 1 ≤ r ≤ N + 1 1\leq r\leq N+1 1 ≤ r ≤ N + 1 , and let A ⊆ P s A\subseteq P_s A ⊆ P s contain no chain of r + 1 r+1 r + 1 elements. For every symmetric chain C C C , we have ∣ A ∩ C ∣ ≤ min { r , ∣ C ∣ } |A\cap C|\leq\min\{r,|C|\} ∣ A ∩ C ∣ ≤ min { r , ∣ C ∣ } . Because the ranks occupied by C C C form an interval centered at N / 2 N/2 N /2 , the r r r rank layers nearest the center contain exactly min { r , ∣ C ∣ } \min\{r,|C|\} min { r , ∣ C ∣ } elements of C C C . When r r r and N N N have the same parity, these r r r layers can be chosen in two ways, and either choice works, because every symmetric chain has ∣ C ∣ ≡ N + 1 ( m o d 2 ) |C|\equiv N+1\pmod{2} ∣ C ∣ ≡ N + 1 ( mod 2 ) and hence ∣ C ∣ ≠ r |C|\neq r ∣ C ∣ = r . Summing over the decomposition shows that ∣ A ∣ |A| ∣ A ∣ is at most the sum of the r r r largest rank sizes, and the union of those r r r central layers attains the bound.
Any symmetric chain decomposition of P s P_s P s has exactly R s ( ⌊ N / 2 ⌋ ) R_s(\lfloor N/2\rfloor) R s (⌊ N /2 ⌋) chains, which in the homogeneous case is asymptotically ( s + 1 ) n 6 / π n s ( s + 2 ) (s+1)^n\sqrt{6/\pi ns(s+2)} ( s + 1 ) n 6/ π n s ( s + 2 ) by [36 ] . The homogeneous poset has ( s + 1 ) n (s+1)^n ( s + 1 ) n elements. Hence, for fixed s ≥ 1 s\geq1 s ≥ 1 , the average chain length in any symmetric chain decomposition is
( s + 1 ) n ( n ⌊ n s / 2 ⌋ ) s ∼ π n s ( s + 2 ) 6 . (49) \frac{(s+1)^n}{\binom{n}{\lfloor ns/2\rfloor}_s}\sim\sqrt{\frac{\pi ns(s+2)}{6}}. \tag*{(49)} ( ⌊ n s /2 ⌋ n ) s ( s + 1 ) n ∼ 6 π n s ( s + 2 ) . (49)
The average length is therefore Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) , whereas the longest chain has n s + 1 = Θ ( n ) ns+1=\Theta(n) n s + 1 = Θ ( n ) elements.
First differences and chain starts
Fix a symmetric chain decomposition of P s P_s P s and set R s ( − 1 ) = 0 R_s(-1)=0 R s ( − 1 ) = 0 . Each chain contains at most one element of any given rank, so R s ( k ) R_s(k) R s ( k ) is the number of chains meeting rank k k k . For 0 ≤ k ≤ ⌊ N / 2 ⌋ 0\leq k\leq\lfloor N/2\rfloor 0 ≤ k ≤ ⌊ N /2 ⌋ , every chain meeting rank k − 1 k-1 k − 1 also meets rank k k k . Hence the number of chains beginning at rank k k k is
R s ( k ) − R s ( k − 1 ) . (50) R_s(k)-R_s(k-1). \tag*{(50)} R s ( k ) − R s ( k − 1 ) . (50)
In the homogeneous case, define the first differences by
D n , s ( k ) = ( n k ) s − ( n k − 1 ) s . (51) D_{n,s}(k)=\binom{n}{k}_s-\binom{n}{k-1}_s. \tag*{(51)} D n , s ( k ) = ( k n ) s − ( k − 1 n ) s . (51)
Multiplying the generating polynomial by 1 − x 1-x 1 − x gives
∑ k ≥ 0 D n , s ( k ) x k = ( 1 − x ) ( 1 + x + ⋯ + x s ) n = ( 1 − x s + 1 ) n ( 1 − x ) n − 1 . (52) \sum_{k\geq0}D_{n,s}(k)x^k=(1-x)(1+x+\cdots+x^s)^n=\frac{(1-x^{s+1})^n}{(1-x)^{n-1}}. \tag*{(52)} k ≥ 0 ∑ D n , s ( k ) x k = ( 1 − x ) ( 1 + x + ⋯ + x s ) n = ( 1 − x ) n − 1 ( 1 − x s + 1 ) n . (52)
For n ≥ 2 n\geq2 n ≥ 2 , expand ( 1 − x s + 1 ) n (1-x^{s+1})^n ( 1 − x s + 1 ) n and use [ x m ] ( 1 − x ) − ( n − 1 ) = ( m + n − 2 n − 2 ) [x^m](1-x)^{-(n-1)}=\binom{m+n-2}{n-2} [ x m ] ( 1 − x ) − ( n − 1 ) = ( n − 2 m + n − 2 ) for m ≥ 0 m\geq0 m ≥ 0 . Coefficient extraction gives the exact first-difference formula
D n , s ( k ) = ∑ j = 0 min { n , ⌊ k / ( s + 1 ) ⌋ } ( − 1 ) j ( n j ) ( k − j ( s + 1 ) + n − 2 n − 2 ) , k ≥ 0. (53) D_{n,s}(k)=\sum_{j=0}^{\min\{n,\lfloor k/(s+1)\rfloor\}}(-1)^j\binom{n}{j}\binom{k-j(s+1)+n-2}{n-2},\qquad k\geq0. \tag*{(53)} D n , s ( k ) = j = 0 ∑ m i n { n , ⌊ k / ( s + 1 )⌋} ( − 1 ) j ( j n ) ( n − 2 k − j ( s + 1 ) + n − 2 ) , k ≥ 0. (53)
In particular, throughout the lower boundary range 0 ≤ k ≤ s 0\leq k\leq s 0 ≤ k ≤ s , only the j = 0 j=0 j = 0 term contributes and
D n , s ( k ) = ( k + n − 2 n − 2 ) . (54) D_{n,s}(k)=\binom{k+n-2}{n-2}. \tag*{(54)} D n , s ( k ) = ( n − 2 k + n − 2 ) . (54)
For 0 ≤ k ≤ ⌊ n s / 2 ⌋ 0\leq k\leq\lfloor ns/2\rfloor 0 ≤ k ≤ ⌊ n s /2 ⌋ , D n , s ( k ) D_{n,s}(k) D n , s ( k ) counts the chains beginning at rank k k k . Such a chain ends at rank n s − k ns-k n s − k and therefore contains n s − 2 k + 1 ns-2k+1 n s − 2 k + 1 elements. With s = 2 σ s=2\sigma s = 2 σ , this is 2 ( n σ − k ) + 1 2(n\sigma-k)+1 2 ( nσ − k ) + 1 , the dimension of a spin-( n σ − k ) (n\sigma-k) ( nσ − k ) irreducible representation.
Symmetric chains and Clebsch–Gordan profiles
Fix s i = 2 σ i s_i=2\sigma_i s i = 2 σ i , with σ i ∈ 1 2 Z ≥ 0 \sigma_i\in\frac{1}{2}\mathbb{Z}_{\geq0} σ i ∈ 2 1 Z ≥ 0 , and let V σ V_\sigma V σ denote the irreducible SU(2)-module of spin σ \sigma σ , of dimension 2 σ + 1 2\sigma+1 2 σ + 1 . Assigning the coordinate value k i k_i k i the weight k i − σ i k_i-\sigma_i k i − σ i identifies the rank-k k k elements of P s P_s P s with a basis of the weight space of weight k − N / 2 k-N/2 k − N /2 in ⨂ i = 1 n V σ i \bigotimes_{i=1}^n V_{\sigma_i} ⨂ i = 1 n V σ i . Proctor’s s l ( 2 , C ) \mathfrak{sl}(2,\mathbb{C}) sl ( 2 , C ) action on the vector space with basis P s P_s P s [36 ] realizes the module ⨂ i V σ i \bigotimes_i V_{\sigma_i} ⨂ i V σ i ; its raising operator is the sum of the n n n single-coordinate raising operators. An irreducible decomposition of this module and a symmetric chain decomposition of the underlying poset are different objects: the former expresses a vector space as a direct sum of invariant subspaces, whereas the latter partitions the elements of a poset. Srinivasan [40 ] constructs a symmetric Jordan basis that supplies a linear bridge between them.
Proposition 6.1 (Chain and constituent profiles). Let C C C be any symmetric chain decomposition of P s P_s P s with s i = 2 σ i s_i=2\sigma_i s i = 2 σ i . For 0 ≤ k ≤ ⌊ N / 2 ⌋ 0\leq k\leq\lfloor N/2\rfloor 0 ≤ k ≤ ⌊ N /2 ⌋ , the number of chains in C C C beginning at rank k k k is
R s ( k ) − R s ( k − 1 ) = d σ ( N / 2 − k ) , (55) R_s(k)-R_s(k-1)=d_{\sigma}^{(N/2-k)}, \tag*{(55)} R s ( k ) − R s ( k − 1 ) = d σ ( N /2 − k ) , (55) the multiplicity of V N / 2 − k V_{N/2-k} V N /2 − k in ⨂ i V σ i \bigotimes_i V_{\sigma_i} ⨂ i V σ i . Consequently, the multiset of chain lengths in C C C equals the multiset of dimensions of the irreducible constituents. After choosing an irreducible direct-sum decomposition, we can match chains and constituent copies noncanonically, pairing each chain beginning at rank k k k with a copy of V N / 2 − k V_{N/2-k} V N /2 − k .
Proof. By (50) , the number of chains beginning at rank k k k is R s ( k ) − R s ( k − 1 ) R_s(k)-R_s(k-1) R s ( k ) − R s ( k − 1 ) . Let w m w_m w m denote the dimension of the weight-m m m space and put J = N / 2 − k J=N/2-k J = N /2 − k . A spin-L L L summand contributes one vector at every weight from − L -L − L to L L L . Hence w − J w_{-J} w − J and w − ( J + 1 ) w_{-(J+1)} w − ( J + 1 ) are the total multiplicities of constituents with spin at least J J J and J + 1 J+1 J + 1 , respectively. Their difference isolates the spin-J J J multiplicity:
d σ ( J ) = w − J − w − ( J + 1 ) . (56) d_{\sigma}^{(J)}=w_{-J}-w_{-(J+1)}. \tag*{(56)} d σ ( J ) = w − J − w − ( J + 1 ) . (56)
The weight-space dictionary gives w − J = R s ( k ) w_{-J}=R_s(k) w − J = R s ( k ) and w − ( J + 1 ) = R s ( k − 1 ) w_{-(J+1)}=R_s(k-1) w − ( J + 1 ) = R s ( k − 1 ) , proving (55) . A chain beginning at rank k k k ends at rank N − k N-k N − k and therefore has N − 2 k + 1 N-2k+1 N − 2 k + 1 elements, the dimension of V N / 2 − k V_{N/2-k} V N /2 − k . Pair chains and constituent copies separately for each starting rank.
The Clebsch–Gordan decomposition of the tensor product V α ⊗ V β V_\alpha\otimes V_\beta V α ⊗ V β is
V α ⊗ V β ≅ ⨁ J = ∣ α − β ∣ α + β V J , (57) V_\alpha\otimes V_\beta\cong\bigoplus_{J=|\alpha-\beta|}^{\alpha+\beta}V_J, \tag*{(57)} V α ⊗ V β ≅ J = ∣ α − β ∣ ⨁ α + β V J , (57)
where J J J increases in unit steps. This tensor-product decomposition is the representation-theoretic counterpart of the grid rule (48). With a = 2 α + 1 a=2\alpha+1 a = 2 α + 1 and b = 2 β + 1 b=2\beta+1 b = 2 β + 1 , its constituents have dimensions a + b − 1 , a + b − 3 , … , ∣ a − b ∣ + 1 a+b-1,a+b-3,\ldots,|a-b|+1 a + b − 1 , a + b − 3 , … , ∣ a − b ∣ + 1 , and there are min { a , b } \min\{a,b\} min { a , b } of them.
Remark 6.2. The de Bruijn–Tengbergen–Kruyswijk nested-hook induction therefore mirrors the Clebsch–Gordan rule at the level of profiles. The conclusion is an equality of length–dimension profiles, not a canonical identification of individual chains with irreducible summands.
For 0 ≤ k ≤ ⌊ n s / 2 ⌋ 0 \le k \le\lfloor ns/2 \rfloor 0 ≤ k ≤ ⌊ n s /2 ⌋ , equation (53) is a character-free closed form for the multiplicity d n , s / 2 ( n s / 2 − k ) d_{n,s/2}^{(ns/2-k)} d n , s /2 ( n s /2 − k ) .
Example 6.3 (A binary row and its interpretations). For ( n , s ) = ( 4 , 1 ) (n,s)=(4,1) ( n , s ) = ( 4 , 1 ) , Table 2 gives the coefficient row ( 1 , 4 , 6 , 4 , 1 ) (1,4,6,4,1) ( 1 , 4 , 6 , 4 , 1 ) , whose lower-half first differences are ( 1 , 3 , 2 ) (1,3,2) ( 1 , 3 , 2 ) . The middle layer contains the six binary words with exactly two ones, so four independent fair binary draws total two with probability 6 / 16 = 3 / 8 6/16=3/8 6/16 = 3/8 . Every symmetric chain decomposition of { 0 , 1 } 4 \{0,1\}^{4} { 0 , 1 } 4 has one chain of length five, three of length three, and two of length one. Proposition 6.1 gives the matching constituent profile
V 1 / 2 ⊗ 4 ≅ V 2 ⊕ 3 V 1 ⊕ 2 V 0 , 5 + 3 ⋅ 3 + 2 ⋅ 1 = 16. V_{1/2}^{\otimes4} \cong V_2 \oplus3V_1 \oplus2V_0,\qquad5+3\cdot3+2\cdot1=16. V 1/2 ⊗ 4 ≅ V 2 ⊕ 3 V 1 ⊕ 2 V 0 , 5 + 3 ⋅ 3 + 2 ⋅ 1 = 16. Thus the zero-magnetization subspace has dimension six, whereas the singlet subspace has dimension 6 − 4 = 2 6-4=2 6 − 4 = 2 : each spin-2 2 2 or spin-1 1 1 constituent also contributes one zero-weight vector.
Proposition 6.1 and the profile comparison hold for arbitrary bounds, hence for mixed spins. We work out the mixed-spin case in § 8 .
Representation theory and applications
Spin multiplicities
Specialize the dictionary of § 6.3 to n n n identical spin-σ \sigma σ particles, σ ∈ 1 2 Z ≥ 0 \sigma\in\frac{1}{2}\mathbb{Z}_{\ge0} σ ∈ 2 1 Z ≥ 0 . If m m m denotes the total magnetization, use the identifications
s = 2 σ , k = m + σ n . (58) s=2\sigma,\qquad k=m+\sigma n. \tag*{(58)} s = 2 σ , k = m + σ n . (58)
Here m + n σ ∈ Z m+n\sigma\in\mathbb{Z} m + nσ ∈ Z , and the spin labels satisfy 0 ≤ J ≤ n σ 0 \le J \le n\sigma 0 ≤ J ≤ nσ and J − n σ ∈ Z J-n\sigma\in\mathbb{Z} J − nσ ∈ Z . The coefficient ( n m + σ n ) 2 σ \binom{n}{m+\sigma n}_{2\sigma} ( m + σ n n ) 2 σ is the dimension of the total-magnetization-m m m subspace. The multiplicity d n , σ ( J ) d_{n,\sigma}^{(J)} d n , σ ( J ) of the spin-J J J irreducible representation in the n n n -fold tensor product of spin-σ \sigma σ representations is the difference between the dimensions of the magnetization-J J J and magnetization-( J + 1 ) (J+1) ( J + 1 ) subspaces:
d n , σ ( J ) = ( n J + σ n ) 2 σ − ( n J + σ n + 1 ) 2 σ . (59) d_{n,\sigma}^{(J)}=\binom{n}{J+\sigma n}_{2\sigma}-\binom{n}{J+\sigma n+1}_{2\sigma}. \tag*{(59)} d n , σ ( J ) = ( J + σ n n ) 2 σ − ( J + σ n + 1 n ) 2 σ . (59)
The midpoint shift also has a representation-theoretic interpretation. In spin units, the Weyl vector of s u ( 2 ) \mathfrak{su}(2) su ( 2 ) is ρ = 1 2 \rho=\frac{1}{2} ρ = 2 1 , and
dim V J = 2 ( J + ρ ) , J ( J + 1 ) = ( J + ρ ) 2 − ρ 2 . \dim V_J=2(J+\rho),\qquad J(J+1)=(J+\rho)^2-\rho^2. dim V J = 2 ( J + ρ ) , J ( J + 1 ) = ( J + ρ ) 2 − ρ 2 .
Thus the Gaussian factor in the central multiplicity profile of § 5.3 is expressed in terms of the shifted spin J + 1 2 J+\frac{1}{2} J + 2 1 , or equivalently through the shifted Casimir J ( J + 1 ) + 1 4 J(J+1)+\frac{1}{4} J ( J + 1 ) + 4 1 .
To measure the deficit from maximal spin, set ℓ = n σ − J \ell=n\sigma-J ℓ = nσ − J . Then J + σ n = 2 σ n − ℓ J+\sigma n=2\sigma n-\ell J + σ n = 2 σ n − ℓ , and the symmetry relation (20) , with n s = 2 σ n ns=2\sigma n n s = 2 σ n , replaces the lower entries J + σ n J+\sigma n J + σ n and J + σ n + 1 J+\sigma n+1 J + σ n + 1 in (59) by ℓ \ell ℓ and ℓ − 1 \ell-1 ℓ − 1 :
d n , σ ( n σ − ℓ ) = ( n ℓ ) 2 σ − ( n ℓ − 1 ) 2 σ = D n , 2 σ ( ℓ ) . (60) d_{n,\sigma}^{(n\sigma-\ell)}=\binom{n}{\ell}_{2\sigma}-\binom{n}{\ell-1}_{2\sigma}=D_{n,2\sigma}(\ell). \tag*{(60)} d n , σ ( nσ − ℓ ) = ( ℓ n ) 2 σ − ( ℓ − 1 n ) 2 σ = D n , 2 σ ( ℓ ) . (60)
Proposition 6.1 gives a second interpretation of (60) : D n , 2 σ ( ℓ ) D_{n,2\sigma}(\ell) D n , 2 σ ( ℓ ) is the number of symmetric chains beginning at rank ℓ \ell ℓ in { 0 , 1 , … , 2 σ } n \{0,1,\ldots,2\sigma\}^{n} { 0 , 1 , … , 2 σ } n , and each such chain has 2 J + 1 2J+1 2 J + 1 elements.
The boundary range 0 ≤ k ≤ s 0\le k\le s 0 ≤ k ≤ s corresponds to − σ n ≤ m ≤ − σ ( n − 2 ) -\sigma n\le m\le-\sigma(n-2) − σ n ≤ m ≤ − σ ( n − 2 ) . Its reflection under m ↦ − m m\mapsto-m m ↦ − m gives the opposite boundary range, so their union is the near-saturation sector
∣ m ∣ ≥ σ ( n − 2 ) . (61) |m|\ge\sigma(n-2). \tag*{(61)} ∣ m ∣ ≥ σ ( n − 2 ) . (61)
In this sector, the fixed-magnetization subspaces have figurate-number dimensions, and the irreducible multiplicities are their first differences. For n ≥ 2 n\ge2 n ≥ 2 and 0 ≤ ℓ ≤ 2 σ 0\le\ell\le2\sigma 0 ≤ ℓ ≤ 2 σ , equations (60) and (54) give
d n , σ ( n σ − ℓ ) = ( ℓ + n − 2 n − 2 ) . (62) d_{n,\sigma}^{(n\sigma-\ell)}=\binom{\ell+n-2}{n-2}. \tag*{(62)} d n , σ ( nσ − ℓ ) = ( n − 2 ℓ + n − 2 ) . (62)
For σ ≥ 1 \sigma\ge1 σ ≥ 1 , the values at ℓ = 0 , 1 , 2 \ell= 0,1,2 ℓ = 0 , 1 , 2 are 1 1 1 , n − 1 n-1 n − 1 , and ( n 2 ) \binom{n}{2} ( 2 n ) ; when σ = 1 2 \sigma= \frac{1}{2} σ = 2 1 , only ℓ = 0 , 1 \ell= 0,1 ℓ = 0 , 1 lie in the boundary range. The distinction between weight-space dimension and irreducible multiplicity is already visible at ℓ = 1 \ell= 1 ℓ = 1 : the magnetization-( n σ − 1 ) (n\sigma- 1) ( nσ − 1 ) subspace has dimension n n n , whereas spin J = n σ − 1 J = n\sigma- 1 J = nσ − 1 occurs with multiplicity n − 1 n-1 n − 1 .
When n = 2 ν n = 2\nu n = 2 ν is even, the central first difference
d 2 ν , σ ( 0 ) = ( 2 ν 2 σ ν ) 2 σ − ( 2 ν 2 σ ν + 1 ) 2 σ (63) d^{(0)}_{2\nu,\sigma} = \binom{2\nu}{2\sigma\nu}_{2\sigma} - \binom{2\nu}{2\sigma\nu+ 1}_{2\sigma} \tag*{(63)} d 2 ν , σ ( 0 ) = ( 2 σ ν 2 ν ) 2 σ − ( 2 σ ν + 1 2 ν ) 2 σ (63)
is the dimension of the SU(2)-invariant subspace of the 2 ν 2\nu 2 ν -fold tensor product of the ( 2 σ + 1 ) (2\sigma+ 1) ( 2 σ + 1 ) -dimensional irreducible representation.
Equation (63) recovers familiar low-spin sequences. For σ = 1 2 \sigma= \frac{1}{2} σ = 2 1 it gives the Catalan numbers ( 2 ν ν ) − ( 2 ν ν + 1 ) \binom{2\nu}{\nu} - \binom{2\nu}{\nu+1} ( ν 2 ν ) − ( ν + 1 2 ν ) , and for σ = 1 \sigma= 1 σ = 1 the even-index Riordan numbers. For σ = 2 \sigma= 2 σ = 2 it gives the dimensions of the spaces of even-degree noncommutative SL(2, C \mathbb{C} C )-invariants in five variables. Almkvist, Dicks, and Formanek [1 ] studied these invariant spaces before the spin-multiplicity interpretation. These sequences are catalogued in the OEIS; Table 4 gives the concordance.
The two Riordan entries record complementary interpretations. OEIS entry A099251 identifies the even-index Riordan numbers with the Haar moments ⟨ ( tr O ) 2 ν ⟩ \langle(\operatorname{tr} O)^{2\nu}\rangle ⟨( tr O ) 2 ν ⟩ over the 3 × 3 3 \times3 3 × 3 orthogonal group. The double cover SU(2) → \to → SO(3) mediates this correspondence. OEIS entry A005043 records the Motzkin- and Riordan-path descriptions.
K σ ( J , L ) = 2 L + 1 ( 2 J + 1 ) ( 2 σ + 1 ) , L = ∣ J − σ ∣ , ∣ J − σ ∣ + 1 , … , J + σ , (64) K_\sigma(J,L) = \frac{2L + 1}{(2J + 1)(2\sigma+ 1)}, \qquad L = \lvert J - \sigma\rvert, \lvert J - \sigma\rvert+ 1, \ldots, J + \sigma, \tag*{(64)} K σ ( J , L ) = ( 2 J + 1 ) ( 2 σ + 1 ) 2 L + 1 , L = ∣ J − σ ∣ , ∣ J − σ ∣ + 1 , … , J + σ , (64)
with zero entries otherwise, a Markov transition kernel on the spin labels. This is the SU(2) specialization of the tensor-product chain of Biane, Bougerol, and O’Connell [10 §5.5] . Along a path, the dimension factors telescope, so starting at J 0 = 0 J_0 = 0 J 0 = 0 gives
P ( J n = J ) = ( 2 J + 1 ) d n , σ ( J ) ( 2 σ + 1 ) n . (65) \mathbb{P}(J_n = J) = \frac{(2J + 1)d^{(J)}_{n,\sigma}}{(2\sigma+ 1)^n}. \tag*{(65)} P ( J n = J ) = ( 2 σ + 1 ) n ( 2 J + 1 ) d n , σ ( J ) . (65)
This is the fraction of the full tensor-product dimension belonging to the spin-J J J sector. For σ = 1 2 \sigma= \frac{1}{2} σ = 2 1 , the coupling paths ending at zero are Dyck paths after doubling their heights. For σ = 1 \sigma= 1 σ = 1 , they are Riordan paths: non-negative paths with steps − 1 , 0 , 1 -1,0,1 − 1 , 0 , 1 and no horizontal step at height zero, since V 0 ⊗ V 1 ≅ V 1 V_0 \otimes V_1 \cong V_1 V 0 ⊗ V 1 ≅ V 1 . This boundary rule distinguishes them from ordinary non-negative bridges of the centered walk in Remark 5.4.
The s-Catalan numbers as Littlewood–Richardson coefficients
Belbachir and Iguerouafa [6 Def. 3.2] name the central first differences (63)
Cat ν ( s ) : = ( 2 ν s ν ) s − ( 2 ν s ν + 1 ) s (66) \operatorname{Cat}^{(s)}_\nu:= \binom{2\nu}{s\nu}_{s} - \binom{2\nu}{s\nu+ 1}_{s} \tag*{(66)} Cat ν ( s ) := ( s ν 2 ν ) s − ( s ν + 1 2 ν ) s (66)
the s s s -Catalan numbers, under a standing hypothesis that s s s is odd, and already observe that these values occur as spin multiplicities [14 , 15 ] . Linz [26 ] keeps the name for every s ≥ 1 s \ge1 s ≥ 1 , uses the notation ( n k ) s \binom{n}{k}_s ( k n ) s adopted here alongside the term s s s -binomial, and tabulates the values in his Figure 1. For s = 2 σ s=2\sigma s = 2 σ , Cat ν ( s ) = d 2 ν , σ ( 0 ) \operatorname{Cat}^{(s)}_\nu=d^{(0)}_{2\nu,\sigma} Cat ν ( s ) = d 2 ν , σ ( 0 ) .
For a partition λ = ( λ 1 , … , λ r ) \lambda=(\lambda_1,\ldots,\lambda_r) λ = ( λ 1 , … , λ r ) , let s ∗ λ = ( s λ 1 , … , s λ r ) s*\lambda=(s\lambda_1,\ldots,s\lambda_r) s ∗ λ = ( s λ 1 , … , s λ r ) denote its horizontal stretch by a factor s s s . Figure 2 shows λ 4 \lambda_4 λ 4 and 2 ∗ λ 4 2*\lambda_4 2 ∗ λ 4 .
Figure 2. The staircase partition λ 4 = ( 4 , 3 , 2 , 1 ) \lambda_4=(4,3,2,1) λ 4 = ( 4 , 3 , 2 , 1 ) and its horizontal stretch 2 ∗ λ 4 = ( 8 , 6 , 4 , 2 ) 2*\lambda_4=(8,6,4,2) 2 ∗ λ 4 = ( 8 , 6 , 4 , 2 ) . The gray dividers separate the two boxes arising from each original box.
Let λ ν = ( ν , ν − 1 , … , 1 ) \lambda_\nu=(\nu,\nu-1,\ldots,1) λ ν = ( ν , ν − 1 , … , 1 ) . Linz [26 Theorem 2] gives the Littlewood–Richardson interpretation
d 2 ν , σ ( 0 ) = Cat ν ( s ) = c s ∗ λ 2 ν − 1 , s ∗ ( ν , ν ) s ∗ λ 2 ν , s = 2 σ . (67) d^{(0)}_{2\nu,\sigma}=\operatorname{Cat}^{(s)}_\nu=c^{s*\lambda_{2\nu}}_{s*\lambda_{2\nu-1},s*(\nu,\nu)},\qquad s=2\sigma. \tag*{(67)} d 2 ν , σ ( 0 ) = Cat ν ( s ) = c s ∗ λ 2 ν − 1 , s ∗ ( ν , ν ) s ∗ λ 2 ν , s = 2 σ . (67)
The proof uses a reflection-principle bijection on Littlewood–Richardson tableaux. For fixed ν \nu ν , the coefficient in (67) is polynomial in s s s , explaining, as Linz notes, the polynomial dependence that Curtright, Van Kortryk, and Zachos [15 ] observed empirically for the singlet multiplicities. The Littlewood–Richardson tableau model also supplies a combinatorial interpretation of the s s s -Catalan numbers, as Belbachir and Igueroufa [6 ] sought. Linz’s Theorem 4 further gives, for integers s ≥ 1 s\ge1 s ≥ 1 and μ ≥ 0 \mu\ge0 μ ≥ 0 ,
( ( 2 μ + 1 s ( μ + 1 ) ) s − ( 2 μ + 1 s ( μ + 1 ) + 1 ) s ) = ( ( 2 μ + 2 s ( μ + 1 ) ) s − ( 2 μ + 2 s ( μ + 1 ) + 1 ) s ) . (68) \left(\binom{2\mu+1}{s(\mu+1)}_s-\binom{2\mu+1}{s(\mu+1)+1}_s\right)=\left(\binom{2\mu+2}{s(\mu+1)}_s-\binom{2\mu+2}{s(\mu+1)+1}_s\right). \tag*{(68)} ( ( s ( μ + 1 ) 2 μ + 1 ) s − ( s ( μ + 1 ) + 1 2 μ + 1 ) s ) = ( ( s ( μ + 1 ) 2 μ + 2 ) s − ( s ( μ + 1 ) + 1 2 μ + 2 ) s ) . (68)
At s = 1 s=1 s = 1 , this identity reduces to the two familiar expressions for the Catalan numbers. In the notation of (59) , with σ = s / 2 \sigma=s/2 σ = s /2 , its two sides are d 2 μ + 1 , σ ( 0 ) d^{(0)}_{2\mu+1,\sigma} d 2 μ + 1 , σ ( 0 ) and d 2 μ + 2 , σ ( 0 ) d^{(0)}_{2\mu+2,\sigma} d 2 μ + 2 , σ ( 0 ) . It also follows in two lines from the longitudinal recurrence ( n + 1 k ) s = ∑ i = 0 s ( n − i k − i ) s \binom{n+1}{k}_s=\sum_{i=0}^{s}\binom{n-i}{k-i}_s ( k n + 1 ) s = ∑ i = 0 s ( k − i n − i ) s [5 eq. (1.4)] . With n = 2 μ + 1 n=2\mu+1 n = 2 μ + 1 and K = s ( μ + 1 ) K=s(\mu+1) K = s ( μ + 1 ) , the difference of two such sums telescopes to ( n K − s ) s − ( n K + 1 ) s \binom{n}{K-s}_s-\binom{n}{K+1}_s ( K − s n ) s − ( K + 1 n ) s , and ( n K − s ) s = ( n K ) s \binom{n}{K-s}_s=\binom{n}{K}_s ( K − s n ) s = ( K n ) s by (20) , since ( K − s ) + K = n s (K-s)+K=ns ( K − s ) + K = n s .
Linz’s “spin σ \sigma σ -Catalan number” [26 Def. 3] uses a shifted index, corresponding to the multiplicity of V σ V_\sigma V σ in V σ ⊗ n V_\sigma^{\otimes n} V σ ⊗ n . Self-duality, V σ ∗ ≅ V σ V_\sigma^*\cong V_\sigma V σ ∗ ≅ V σ , gives d n , σ ( 0 ) = d n + 1 , σ ( 0 ) d^{(0)}_{n,\sigma}=d^{(0)}_{n+1,\sigma} d n , σ ( 0 ) = d n + 1 , σ ( 0 ) , which explains the one-step offset between Linz’s table and (63) and contains (68) as the case n = 2 μ + 1 n=2\mu+1 n = 2 μ + 1 .
Example 7.2 (Four-particle singlets). For four identical spin-σ \sigma σ particles, put s = 2 σ ≥ 1 s=2\sigma\ge1 s = 2 σ ≥ 1 . The Clebsch–Gordan rule gives V σ ⊗ V σ ≅ ⨁ J = 0 s V J V_\sigma\otimes V_\sigma\cong\bigoplus_{J=0}^{s}V_J V σ ⊗ V σ ≅ ⨁ J = 0 s V J . A tensor product V J ⊗ V L V_J\otimes V_L V J ⊗ V L contains a singlet precisely when J = L J=L J = L , and then with multiplicity one. Pairing two copies of the two-particle decomposition therefore gives
d 4 , s / 2 ( 0 ) = Cat 2 ( s ) = ( 4 2 s ) s − ( 4 2 s + 1 ) s = s + 1. d^{(0)}_{4,s/2}=\operatorname{Cat}^{(s)}_2=\binom{4}{2s}_s-\binom{4}{2s+1}_s=s+1. d 4 , s /2 ( 0 ) = Cat 2 ( s ) = ( 2 s 4 ) s − ( 2 s + 1 4 ) s = s + 1.
For s = 1 , 2 , 3 s=1,2,3 s = 1 , 2 , 3 , the rows n = 4 n=4 n = 4 in Table 2 give 6 − 4 = 2 6-4=2 6 − 4 = 2 , 19 − 16 = 3 19-16=3 19 − 16 = 3 , and 44 − 40 = 4 44-40=4 44 − 40 = 4 . Equation (67) consequently evaluates the stretching polynomial
c ( 3 s , 2 s , s ) , ( 2 s , s ) ( 4 s , 3 s , 2 s , s ) = s + 1. c^{(4s,3s,2s,s)}_{(3s,2s,s),(2s,s)}=s+1. c ( 3 s , 2 s , s ) , ( 2 s , s ) ( 4 s , 3 s , 2 s , s ) = s + 1.
Entanglement witnesses and spectral degeneracies
In the entanglement witnesses studied by Cohen, Hansen, and Itzhaki [14 ] , the singlet multiplicities d 2 J , σ ( 0 ) d^{(0)}_{2J,\sigma} d 2 J , σ ( 0 ) give the dimension of the witness’s singlet eigenspace. For σ = 1 2 \sigma=\frac{1}{2} σ = 2 1 , the spin-J J J multiplicities give the spectral degeneracies within each admissible fixed-particle-number sector of the symmetric simple exclusion process on the complete graph; over the full state space, the degeneracies are ( 2 J + 1 ) d n , 1 / 2 ( J ) (2J+1)d^{(J)}_{n,1/2} ( 2 J + 1 ) d n , 1/2 ( J ) . Mendonça [28 ] treats complete bipartite and related graphs.
Constant-sum antichains and hash-based signatures
The Winternitz one-time signature framework encodes a message as a word ( k 1 , … , k n ) (k_1,\ldots,k_n) ( k 1 , … , k n ) over the alphabet { 0 , 1 , … , s } \{0,1,\ldots,s\} { 0 , 1 , … , s } . Signing a word reveals, for each i i i , the k i k_i k i th element of the i i i th hash chain, and anyone can advance along a hash chain but not reverse it. A signature for one codeword therefore yields a signature for every componentwise larger word, so the codewords must form an antichain. Every constant-sum layer satisfies this condition because the rank levels of the product of chains in § 6 are antichains.
Such a layer contains ( n k ) s \binom{n}{k}_s ( k n ) s words and is largest at a central rank by (34) . Zhang, Cui, and Yu [44 ] therefore take k = ⌊ n s / 2 ⌋ k=\lfloor ns/2\rfloor k = ⌊ n s /2 ⌋ . They evaluate its size using Belbachir, Bouroubi, and Khelladi’s longitudinal recurrence [5 eq. (1.4)] together with the support-sharp closed form (14) , and report signature-size reductions of up to 12.4% for SPHINCS+ and 1.78% for XMSS. Earlier work on constant-sum encodings in this signature framework is due to Perin, Zambonin, Custódio, Moura, and Panario [33 ] .
Example 7.3 (A seven-word constant-sum codebook). For ( n , s ) = ( 3 , 2 ) (n,s)=(3,2) ( n , s ) = ( 3 , 2 ) , the central layer k = 3 k=3 k = 3 consists of
{ 012 , 021 , 102 , 111 , 120 , 201 , 210 } \{012,021,102,111,120,201,210\} { 012 , 021 , 102 , 111 , 120 , 201 , 210 }
where a b c abc ab c denotes the word ( a , b , c ) (a,b,c) ( a , b , c ) . Its size is ( 3 3 ) 2 = 7 \binom{3}{3}_2=7 ( 3 3 ) 2 = 7 , as in Table 2 , and it is a largest antichain in { 0 , 1 , 2 } 3 \{0,1,2\}^3 { 0 , 1 , 2 } 3 . If one word were componentwise larger than another, with at least one strict inequality, its coordinate sum would be larger, so two distinct words in this layer are incomparable. For instance, a signature for 012 permits advancing the first hash chain to obtain a signature for 112. The latter word has sum four and lies outside the codebook; every componentwise advance that changes a word similarly leaves the constant-sum layer.
Unequal bounds, boundary crossover, and further directions
Mixed bounds and mixed spins
For a collection of particles with spins σ = ( σ 1 , … , σ n ) \boldsymbol{\sigma}=(\sigma_1,\ldots,\sigma_n) σ = ( σ 1 , … , σ n ) , put s i = 2 σ i s_i=2\sigma_i s i = 2 σ i and write S = ∑ i σ i S=\sum_i\sigma_i S = ∑ i σ i . The dimension of the magnetization-m m m space is
R 2 σ ( m + S ) , (69) R_{2\boldsymbol{\sigma}}(m+S), \tag*{(69)} R 2 σ ( m + S ) , (69)
and, with ℓ = S − J \ell=S-J ℓ = S − J , the spin-J J J multiplicity is
d σ ( S − ℓ ) = R 2 σ ( ℓ ) − R 2 σ ( ℓ − 1 ) . (70) d_{\boldsymbol{\sigma}}^{(S-\ell)}=R_{2\boldsymbol{\sigma}}(\ell)-R_{2\boldsymbol{\sigma}}(\ell-1). \tag*{(70)} d σ ( S − ℓ ) = R 2 σ ( ℓ ) − R 2 σ ( ℓ − 1 ) . (70)
The spin labels satisfy 0 ≤ J ≤ S 0\leq J\leq S 0 ≤ J ≤ S and J − S ∈ Z J-S\in\mathbb{Z} J − S ∈ Z , so ℓ = S − J \ell=S-J ℓ = S − J is an integer. The right-hand side of (70) also gives the number of symmetric chains beginning at rank ℓ \ell ℓ in the unequal product ∏ i { 0 , 1 , … , 2 σ i } \prod_i\{0,1,\ldots,2\sigma_i\} ∏ i { 0 , 1 , … , 2 σ i } . Each such chain has 2 ( S − ℓ ) + 1 2(S-\ell)+1 2 ( S − ℓ ) + 1 elements. Thus Proposition 6.1 shows that, at the level of profiles, the numbers and lengths of the chains agree with the multiplicities and dimensions of the mixed-spin constituents.
If n ≥ 2 n\geq2 n ≥ 2 and 0 ≤ ℓ ≤ min i ( 2 σ i ) 0\leq\ell\leq\min_i(2\sigma_i) 0 ≤ ℓ ≤ min i ( 2 σ i ) , the inhomogeneous boundary formula (30) and Pascal’s rule, ( ℓ + n − 1 n − 1 ) − ( ℓ + n − 2 n − 1 ) = ( ℓ + n − 2 n − 2 ) \binom{\ell+n-1}{n-1}-\binom{\ell+n-2}{n-1}=\binom{\ell+n-2}{n-2} ( n − 1 ℓ + n − 1 ) − ( n − 1 ℓ + n − 2 ) = ( n − 2 ℓ + n − 2 ) , give
d σ ( S − ℓ ) = ( ℓ + n − 2 n − 2 ) . (71) d_{\boldsymbol{\sigma}}^{(S-\ell)}=\binom{\ell+n-2}{n-2}. \tag*{(71)} d σ ( S − ℓ ) = ( n − 2 ℓ + n − 2 ) . (71)
Throughout this range, the multiplicity depends only on n n n and ℓ \ell ℓ , not on the individual spins. Beyond this boundary range, the mixed-spin multiplicities still admit a closed form. Multiplying the inhomogeneous generating polynomial by 1 − x 1-x 1 − x gives
∑ k ≥ 0 [ R s ( k ) − R s ( k − 1 ) ] x k = ∏ i = 1 n ( 1 − x s i + 1 ) ( 1 − x ) n − 1 , (72) \sum_{k\geq0}\left[R_s(k)-R_s(k-1)\right]x^k=\frac{\prod_{i=1}^{n}(1-x^{s_i+1})}{(1-x)^{n-1}}, \tag*{(72)} k ≥ 0 ∑ [ R s ( k ) − R s ( k − 1 ) ] x k = ( 1 − x ) n − 1 ∏ i = 1 n ( 1 − x s i + 1 ) , (72)
and extracting the coefficient of x k x^k x k yields, for $n\geq 2,
R s ( k ) − R s ( k − 1 ) = ∑ I ⊆ { 1 , … , n } ( − 1 ) ∣ I ∣ ( k − ∑ i ∈ I ( s i + 1 ) + n − 2 n − 2 ) , (73) R_s(k)-R_s(k-1)=\sum_{I\subseteq\{1,\ldots,n\}}(-1)^{|I|}\binom{k-\sum_{i\in I}(s_i+1)+n-2}{n-2}, \tag*{(73)} R s ( k ) − R s ( k − 1 ) = I ⊆ { 1 , … , n } ∑ ( − 1 ) ∣ I ∣ ( n − 2 k − ∑ i ∈ I ( s i + 1 ) + n − 2 ) , (73)
the inhomogeneous counterpart of (53) , valid for k ≥ 0 k \ge0 k ≥ 0 . On the lower half of the rank range, 0 ≤ k ≤ ⌊ N / 2 ⌋ 0 \le k \le\lfloor N/2 \rfloor 0 ≤ k ≤ ⌊ N /2 ⌋ , the left-hand side of (73) is exactly the mixed-spin multiplicity d σ ( S − k ) d_{\sigma}^{(S-k)} d σ ( S − k ) . When all bounds are equal, the 2 n 2^n 2 n subset-indexed terms are grouped, according to j = ∣ I ∣ j=|I| j = ∣ I ∣ , into the terms of (53) . Under convention (6) , every subset I I I satisfying ∑ i ∈ I ( s i + 1 ) > k \sum_{i\in I}(s_i+1)>k ∑ i ∈ I ( s i + 1 ) > k contributes zero; the Cauchy-product argument of § 9 , applied to (72) , shows that these subsets do not arise at all.
In the range where the first differences give multiplicities, equation (73) is the subset-indexed form of Gyamfi and Barone’s formula [24 Theorem 5] ; the boundary formulas (62) and (71) follow by retaining the term indexed by the empty subset.
Example 8.1. Take σ = ( 1 2 , 1 , 1 ) \sigma=\left(\frac{1}{2},1,1\right) σ = ( 2 1 , 1 , 1 ) , so s = ( 1 , 2 , 2 ) s=(1,2,2) s = ( 1 , 2 , 2 ) , N = 5 N=5 N = 5 , and S = 5 2 S=\frac{5}{2} S = 2 5 . The rank-size sequence is ( 1 , 3 , 5 , 5 , 3 , 1 ) (1,3,5,5,3,1) ( 1 , 3 , 5 , 5 , 3 , 1 ) , whose lower-half first differences are 1 , 2 , 2 1,2,2 1 , 2 , 2 . Hence the product of chains { 0 , 1 } × { 0 , 1 , 2 } 2 \{0,1\}\times\{0,1,2\}^2 { 0 , 1 } × { 0 , 1 , 2 } 2 decomposes into one six-element symmetric chain beginning at rank 0, two four-element symmetric chains beginning at rank 1, and two two-element symmetric chains beginning at rank 2. The corresponding Clebsch–Gordan decomposition is
V 1 / 2 ⊗ V 1 ⊗ V 1 ≅ V 5 / 2 ⊕ 2 V 3 / 2 ⊕ 2 V 1 / 2 . (74) V_{1/2}\otimes V_1\otimes V_1 \cong V_{5/2}\oplus2V_{3/2}\oplus2V_{1/2}. \tag*{(74)} V 1/2 ⊗ V 1 ⊗ V 1 ≅ V 5/2 ⊕ 2 V 3/2 ⊕ 2 V 1/2 . (74)
This decomposition has the same length–dimension and start–multiplicity profiles as the chain decomposition, and formula (73) returns 1 , 2 , 2 1,2,2 1 , 2 , 2 directly.
The convolution interpretation, moment formulas, log-concavity, and existence of a central mode in § 5 extend directly to unequal bounds. Let X i ∼ U s i X_i\sim U_{s_i} X i ∼ U s i be independent and set S n = X 1 + ⋯ + X n S_n=X_1+\cdots+X_n S n = X 1 + ⋯ + X n . Then
E ( S n ) = N 2 , V a r ( S n ) = ∑ i = 1 n s i ( s i + 2 ) 12 = : τ s 2 . (75) \mathop{\mathrm{E}}(S_n)=\frac{N}{2},\qquad\mathop{\mathrm{Var}}(S_n)=\sum_{i=1}^{n}\frac{s_i(s_i+2)}{12}=:\tau_s^2. \tag*{(75)} E ( S n ) = 2 N , Var ( S n ) = i = 1 ∑ n 12 s i ( s i + 2 ) =: τ s 2 . (75)
Each factor 1 + x + ⋯ + x s i 1+x+\cdots+x^{s_i} 1 + x + ⋯ + x s i has a log-concave coefficient sequence with no internal zeros. Convolution preserves these properties, so k ↦ R s ( k ) k\mapsto R_s(k) k ↦ R s ( k ) is log-concave and unimodal. Symmetry places a maximum at k = ⌊ N / 2 ⌋ k=\lfloor N/2\rfloor k = ⌊ N /2 ⌋ . Independently, the symmetric chain decomposition of § 6 shows that this central layer is a largest antichain. Consider a triangular array of bound vectors s ( n ) s^{(n)} s ( n ) , and write s s s for its n n n th row. A Lindeberg central limit theorem applies under the sufficient conditions
τ s 2 ⟶ ∞ , max 1 ≤ i ≤ n s i 2 τ s 2 ⟶ 0. (76) \tau_s^2\longrightarrow\infty,\qquad\frac{\max_{1\le i\le n}s_i^2}{\tau_s^2}\longrightarrow0. \tag*{(76)} τ s 2 ⟶ ∞ , τ s 2 max 1 ≤ i ≤ n s i 2 ⟶ 0. (76)
These conditions hold, in particular, for uniformly bounded arrays with a growing number of nonzero bounds. Since the corresponding probability mass functions are log-concave with no internal zeros, Bender’s local-limit lemma [9 Lemma 2] upgrades this central limit theorem to
sup k ∈ Z ∣ τ s R s ( k ) ∏ i = 1 n ( s i + 1 ) − ϕ ( k − N / 2 τ s ) ∣ ⟶ 0. (77) \sup_{k\in\mathbb{Z}}\left|\tau_s\frac{R_s(k)}{\prod_{i=1}^{n}(s_i+1)}-\phi\left(\frac{k-N/2}{\tau_s}\right)\right|\longrightarrow0. \tag*{(77)} k ∈ Z sup τ s ∏ i = 1 n ( s i + 1 ) R s ( k ) − ϕ ( τ s k − N /2 ) ⟶ 0. (77)
The boundary crossover
The boundary formula (54) remains asymptotically valid beyond its exact range. For k k k indistinguishable balls in n + 1 n+1 n + 1 urns, Menon and Indira’s Poisson limit theorem [30 Theorem 2] shows that the number of urns holding exactly s + 1 s+1 s + 1 balls is asymptotically Poisson when k → ∞ k\to\infty k → ∞ , k / n → 0 k/n\to0 k / n → 0 , and k s + 1 / n s k^{s+1}/n^s k s + 1 / n s converges. Urns holding more than s + 1 s+1 s + 1 balls are then asymptotically absent, their expected number being O ( k s + 2 / n s + 1 ) O(k^{s+2}/n^{s+1}) O ( k s + 2 / n s + 1 ) , so the theorem implies the following crossover.
Proposition 8.2 (Boundary crossover). Fix s ≥ 1 s\ge1 s ≥ 1 , and let k = k ( n ) k=k(n) k = k ( n ) be a sequence of integers tending to infinity. If
k n s / ( s + 1 ) ⟶ λ ∈ [ 0 , ∞ ) , (78) \frac{k}{n^{s/(s+1)}}\longrightarrow\lambda\in[0,\infty), \tag*{(78)} n s / ( s + 1 ) k ⟶ λ ∈ [ 0 , ∞ ) , (78) then
D n , s ( k ) ( k + n − 2 n − 2 ) ⟶ e − λ s + 1 . (79) \frac{D_{n,s}(k)}{\binom{k+n-2}{n-2}}\longrightarrow e^{-\lambda^{s+1}}. \tag*{(79)} ( n − 2 k + n − 2 ) D n , s ( k ) ⟶ e − λ s + 1 . (79)
Consequently, if k = o ( n s / ( s + 1 ) ) k = o(n^{s/(s+1)}) k = o ( n s / ( s + 1 ) ) , then D n , s ( k ) ∼ ( k + n − 2 n − 2 ) D_{n,s}(k) \sim\binom{k+n-2}{n-2} D n , s ( k ) ∼ ( n − 2 k + n − 2 ) .
Proof. Put r = s + 1 r = s + 1 r = s + 1 , θ = λ r \theta= \lambda^r θ = λ r and B n ( k ) = ( k + n − 2 n − 2 ) B_n(k) = \binom{k+n-2}{n-2} B n ( k ) = ( n − 2 k + n − 2 ) , and note that k / n → 0 k/n \to0 k / n → 0 . Since ( 1 − x ) ( 1 + x + ⋯ + x s ) = 1 − x r (1-x)(1+x+\cdots+x^s)=1-x^r ( 1 − x ) ( 1 + x + ⋯ + x s ) = 1 − x r , the generating function (52) equals ( 1 − x r ) ( 1 + x + ⋯ + x s ) n − 1 (1-x^r)(1+x+\cdots+x^s)^{n-1} ( 1 − x r ) ( 1 + x + ⋯ + x s ) n − 1 , and therefore
D n , s ( k ) = ( n − 1 k ) s − ( n − 1 k − r ) s . (80) D_{n,s}(k)=\binom{n-1}{k}_s-\binom{n-1}{k-r}_s. \tag*{(80)} D n , s ( k ) = ( k n − 1 ) s − ( k − r n − 1 ) s . (80)
Choose a weak composition of k k k into n − 1 n-1 n − 1 parts uniformly, and let Y n Y_n Y n be the number of parts at least r r r . Then P ( Y n = 0 ) = ( n − 1 k ) s / B n ( k ) \mathbb{P}(Y_n=0)=\binom{n-1}{k}_s/B_n(k) P ( Y n = 0 ) = ( k n − 1 ) s / B n ( k ) . Requiring any prescribed set of j j j parts to be at least r r r and subtracting r r r from each gives a bijection with the weak compositions of k − r j k-rj k − r j , so that E [ ( Y n j ) ] = ( n − 1 j ) B n ( k − r j ) / B n ( k ) \mathbb{E}\left[\binom{Y_n}{j}\right]=\binom{n-1}{j}B_n(k-rj)/B_n(k) E [ ( j Y n ) ] = ( j n − 1 ) B n ( k − r j ) / B n ( k ) . For each fixed integer t ≥ 0 t\geq0 t ≥ 0 ,
B n ( k − t ) B n ( k ) = ∏ ℓ = 0 t − 1 k − ℓ n + k − 2 − ℓ = ( k n ) t ( 1 + o ( 1 ) ) , (81) \frac{B_n(k-t)}{B_n(k)}
=\prod_{\ell=0}^{t-1}\frac{k-\ell}{n+k-2-\ell}
=\left(\frac{k}{n}\right)^t(1+o(1)), \tag*{(81)} B n ( k ) B n ( k − t ) = ℓ = 0 ∏ t − 1 n + k − 2 − ℓ k − ℓ = ( n k ) t ( 1 + o ( 1 )) , (81)
because each factor is ( k / n ) ( 1 + o ( 1 ) ) (k/n)(1+o(1)) ( k / n ) ( 1 + o ( 1 )) when k → ∞ k\to\infty k → ∞ and k / n → 0 k/n\to0 k / n → 0 . With ( n − 1 j ) ∼ n j / j ! \binom{n-1}{j}\sim n^j/j! ( j n − 1 ) ∼ n j / j ! , this gives, for each fixed j ≥ 1 j\geq1 j ≥ 1 ,
E [ ( Y n j ) ] ∼ n j j ! ( k n ) r j = 1 j ! ( k r n r − 1 ) j ⟶ θ j j ! , (82) \mathbb{E}\left[\binom{Y_n}{j}\right]
\sim\frac{n^j}{j!}\left(\frac{k}{n}\right)^{rj}
=\frac{1}{j!}\left(\frac{k^r}{n^{r-1}}\right)^j
\longrightarrow\frac{\theta^j}{j!}, \tag*{(82)} E [ ( j Y n ) ] ∼ j ! n j ( n k ) r j = j ! 1 ( n r − 1 k r ) j ⟶ j ! θ j , (82)
since k r / n r − 1 = ( k / n s / ( s + 1 ) ) s + 1 k^r/n^{r-1}=(k/n^{s/(s+1)})^{s+1} k r / n r − 1 = ( k / n s / ( s + 1 ) ) s + 1 . Formula (17) for n − 1 n-1 n − 1 types, divided by B n ( k ) B_n(k) B n ( k ) , reads
P ( Y n = 0 ) = ∑ j ≥ 0 ( − 1 ) j E [ ( Y n j ) ] . (83) \mathbb{P}(Y_n=0)=\sum_{j\geq0}(-1)^j\mathbb{E}\left[\binom{Y_n}{j}\right]. \tag*{(83)} P ( Y n = 0 ) = j ≥ 0 ∑ ( − 1 ) j E [ ( j Y n ) ] . (83)
By the Bonferroni inequalities, its partial sums ending at odd and at even j j j bound P ( Y n = 0 ) \mathbb{P}(Y_n=0) P ( Y n = 0 ) from below and from above, respectively. Letting n → ∞ n\to\infty n → ∞ with the cutoff fixed, and then letting the cutoff grow, gives P ( Y n = 0 ) → ∑ j ≥ 0 ( − 1 ) j θ j / j ! = e − θ \mathbb{P}(Y_n=0)\to\sum_{j\geq0}(-1)^j\theta^j/j!=e^{-\theta} P ( Y n = 0 ) → ∑ j ≥ 0 ( − 1 ) j θ j / j ! = e − θ . The factorial-moment limits also imply that Y n Y_n Y n converges in distribution to a Poisson random variable of mean θ \theta θ . Moreover, by (81) with t = r t=r t = r ,
0 ≤ ( n − 1 k − r ) s B n ( k ) ≤ B n ( k − r ) B n ( k ) = O ( ( k n ) r ) = o ( 1 ) . (84) 0\leq\frac{\binom{n-1}{k-r}_s}{B_n(k)}
\leq\frac{B_n(k-r)}{B_n(k)}
=O\left(\left(\frac{k}{n}\right)^r\right)=o(1). \tag*{(84)} 0 ≤ B n ( k ) ( k − r n − 1 ) s ≤ B n ( k ) B n ( k − r ) = O ( ( n k ) r ) = o ( 1 ) . (84)
Dividing the identity D n , s ( k ) = ( n − 1 k ) s − ( n − 1 k − r ) s D_{n,s}(k)=\binom{n-1}{k}_s-\binom{n-1}{k-r}_s D n , s ( k ) = ( k n − 1 ) s − ( k − r n − 1 ) s by B n ( k ) B_n(k) B n ( k ) and applying the two preceding limits proves (79) . □
Thus n s / ( s + 1 ) n^{s/(s+1)} n s / ( s + 1 ) is the first boundary-crossover scale, the smallest scale of k k k at which (54) acquires a nontrivial limiting correction, namely e − λ s + 1 e^{-\lambda^{s+1}} e − λ s + 1 . Figure 3 illustrates this convergence for s = 2 s=2 s = 2 .
Figure 3. Boundary crossover for s = 2 s=2 s = 2 . The finite-n n n curves plot the exact ratio D n , 2 ( k ) / ( k + n − 2 n − 2 ) D_{n,2}(k)/\binom{k+n-2}{n-2} D n , 2 ( k ) / ( n − 2 k + n − 2 ) at every integer 0 ≤ k ≤ ⌊ 1.5 n 2 / 3 ⌋ 0 \le k \le\lfloor1.5n^{2/3}\rfloor 0 ≤ k ≤ ⌊ 1.5 n 2/3 ⌋ , against λ = k / n 2 / 3 \lambda=k/n^{2/3} λ = k / n 2/3 . The finite-n n n coefficients were evaluated by exact-integer convolution, followed by first differencing and normalization. The curves approach the limiting profile e − λ 3 e^{-\lambda^3} e − λ 3 of Proposition 8.2 . For fixed λ > 0 \lambda>0 λ > 0 , the fixed-shift ratios in its proof have relative corrections of order k / n + 1 / k k/n+1/k k / n + 1/ k , whose larger scale here is n − 1 / 3 n^{-1/3} n − 1/3 , suggesting the relatively slow finite-size convergence visible in the figure.
The same argument applies when a positive proportion of the bounds attains a fixed minimum.
Corollary 8.3 (Unequal-bound boundary crossover). Fix s ≥ 1 s\geq1 s ≥ 1 , and let s = ( s 1 , … , s n ) \boldsymbol{s}=(s_1,\ldots,s_n) s = ( s 1 , … , s n ) depend on n n n , with s i ≥ s s_i\geq s s i ≥ s and m n = # { i : s i = s } m_n=\#\{i:s_i=s\} m n = # { i : s i = s } satisfying m n / n → α ∈ ( 0 , 1 ] m_n/n\to\alpha\in(0,1] m n / n → α ∈ ( 0 , 1 ] . If k = k ( n ) → ∞ k=k(n)\to\infty k = k ( n ) → ∞ and k / n s / ( s + 1 ) → λ ∈ [ 0 , ∞ ) k/n^{s/(s+1)}\to\lambda\in[0,\infty) k / n s / ( s + 1 ) → λ ∈ [ 0 , ∞ ) , then
R s ( k ) − R s ( k − 1 ) ( k + n − 2 n − 2 ) ⟶ e − α λ s + 1 . (85) \frac{R_{\boldsymbol{s}}(k)-R_{\boldsymbol{s}}(k-1)}{\binom{k+n-2}{n-2}}
\longrightarrow e^{-\alpha\lambda^{s+1}}. \tag*{(85)} ( n − 2 k + n − 2 ) R s ( k ) − R s ( k − 1 ) ⟶ e − α λ s + 1 . (85)
Proof. For large n n n , permute the coordinates so that s 1 = s s_1=s s 1 = s , put r = s + 1 r=s+1 r = s + 1 and B n ( k ) = ( k + n − 2 n − 2 ) B_n(k)=\binom{k+n-2}{n-2} B n ( k ) = ( n − 2 k + n − 2 ) , and let A n ( k ) A_n(k) A n ( k ) be the number of bounded compositions in the remaining n − 1 n-1 n − 1 coordinates. The generating function (72) gives
R s ( k ) − R s ( k − 1 ) = A n ( k ) − A n ( k − r ) . (86) R_{\boldsymbol{s}}(k)-R_{\boldsymbol{s}}(k-1)=A_n(k)-A_n(k-r). \tag*{(86)} R s ( k ) − R s ( k − 1 ) = A n ( k ) − A n ( k − r ) . (86)
Choose an unrestricted weak composition of k k k into n − 1 n-1 n − 1 parts uniformly, and let Y n Y_n Y n be the number of violations among the m n − 1 m_n-1 m n − 1 coordinates with bound s s s . By (81) , for each fixed j ≥ 1 j \ge1 j ≥ 1 ,
E [ ( Y n j ) ] = ( m n − 1 j ) B n ( k − r j ) B n ( k ) ⟶ ( α λ r ) j j ! . (87) \mathbb{E}\left[\binom{Y_n}{j}\right] = \binom{m_n-1}{j}\frac{B_n(k-rj)}{B_n(k)} \longrightarrow\frac{(\alpha\lambda^r)^j}{j!}. \tag*{(87)} E [ ( j Y n ) ] = ( j m n − 1 ) B n ( k ) B n ( k − r j ) ⟶ j ! ( α λ r ) j . (87)
The Bonferroni argument of Proposition 8.2 yields P ( Y n = 0 ) → e − α λ r \mathbb{P}(Y_n=0) \to e^{-\alpha\lambda^r} P ( Y n = 0 ) → e − α λ r . Writing X i X_i X i for the part in coordinate i i i , the tail probability P ( X i ≥ t ) = B n ( k − t ) / B n ( k ) \mathbb{P}(X_i \ge t)=B_n(k-t)/B_n(k) P ( X i ≥ t ) = B n ( k − t ) / B n ( k ) is non-increasing in t t t . A violation in a coordinate with bound larger than s s s requires at least r + 1 r+1 r + 1 objects, so no upper bound on the larger s i s_i s i is needed: the union bound shows that the probability of any such violation is at most
n B n ( k − r − 1 ) B n ( k ) = O ( k r n r − 1 k n ) = o ( 1 ) , (88) n\frac{B_n(k-r-1)}{B_n(k)} = O\left(\frac{k^r}{n^{r-1}}\frac{k}{n}\right)=o(1), \tag*{(88)} n B n ( k ) B n ( k − r − 1 ) = O ( n r − 1 k r n k ) = o ( 1 ) , (88)
since k r / n r − 1 → λ r k^r/n^{r-1}\to\lambda^r k r / n r − 1 → λ r and k / n → 0 k/n\to0 k / n → 0 . Consequently,
P ( Y n = 0 ) − o ( 1 ) ≤ A n ( k ) B n ( k ) ≤ P ( Y n = 0 ) . (89) \mathbb{P}(Y_n=0)-o(1) \le\frac{A_n(k)}{B_n(k)} \le\mathbb{P}(Y_n=0). \tag*{(89)} P ( Y n = 0 ) − o ( 1 ) ≤ B n ( k ) A n ( k ) ≤ P ( Y n = 0 ) . (89)
Thus A n ( k ) / B n ( k ) → e − α λ r A_n(k)/B_n(k)\to e^{-\alpha\lambda^r} A n ( k ) / B n ( k ) → e − α λ r , whereas 0 ≤ A n ( k − r ) / B n ( k ) ≤ B n ( k − r ) / B n ( k ) = o ( 1 ) 0\le A_n(k-r)/B_n(k)\le B_n(k-r)/B_n(k)=o(1) 0 ≤ A n ( k − r ) / B n ( k ) ≤ B n ( k − r ) / B n ( k ) = o ( 1 ) . Substitution in (86) proves the result.
Deformations and arithmetic
Grouping equal bounds in the inhomogeneous generating polynomial produces ∏ i ≥ 1 ( 1 + x + ⋯ + x i ) L i \prod_{i\ge1}(1+x+\cdots+x^i)^{L_i} ∏ i ≥ 1 ( 1 + x + ⋯ + x i ) L i , whose coefficients are the classical supernomial coefficients of Schilling and Warnaar [38 ] . Their q q q -supernomials retain recurrences and symmetries while connecting the rank polynomial with partition theory and solvable lattice models. In the homogeneous case, Belbachir and Benmezai [4 ] and Bazeniar, Ahmia, and Belbachir [2 ] develop related q q q -deformations and symmetric-function identities. Belbachir and Igueroufa [7 ] develop arithmetic properties of generalized binomial coefficients, including Lucas-type congruences and extensions of theorems of Kummer and Ram. Belbachir, Bouroubi, and Khelladi [5 ] relate the homogeneous coefficients to Bell polynomials and Fibonacci numbers.
Open problems
Deformations with a chain interpretation. Schilling and Warnaar [39 ] give crystal-path and generalized Kostka interpretations of q q q -deformed coefficient arrays. For the deformations discussed above, the more specific question is whether a chain model can respect the nested-hook rule of Remark 6.2. One target is a non-negative integer grading g ( C ) g(C) g ( C ) , constant along each symmetric chain, for which the coefficient at rank k k k is the sum of q g ( C ) q^{g(C)} q g ( C ) over chains meeting that rank. The question is whether a specified deformation admits such a grading on the coordinate grid, compatible with the nested-hook induction. For this model, the lower-half first differences must be coefficientwise non-negative. Which of these deformations admit this additional structure?
Weighted antichains. For positive weights w i w_i w i , every level ∑ i w i k i = c \sum_i w_i k_i=c ∑ i w i k i = c is an antichain. For homogeneous products with n ≥ 2 n \ge2 n ≥ 2 and s ≥ 1 s \ge1 s ≥ 1 , Griggs’s theorem [23 ] implies that a weighted level attains the width of the poset if and only if all weights are equal. The application-specific question is to optimize the level size under additional constraints that a signature scheme imposes on weights or encoding parameters, as in § 7.4 .
Counting the decompositions. Proposition 6.1 shows that every symmetric chain decomposition of P s P_s P s has the multiset of chain lengths dictated by the Clebsch–Gordan rule. For homogeneous products, Tomon [42 ] proved
# SCD ( { 0 , 1 } n ) = ( n 2 e + o ( n ) ) 2 n . (90) \#\operatorname{SCD}(\{0,1\}^{n})=\left(\frac{n}{2e}+o(n)\right)^{2^n}. \tag*{(90)} # SCD ({ 0 , 1 } n ) = ( 2 e n + o ( n ) ) 2 n . (90)
and, more generally, uniformly for s ≥ 1 s \ge1 s ≥ 1 ,
# SCD ( { 0 , 1 , … , s } n ) = n ( 1 − o n ( 1 ) ) ( s + 1 ) n . (91) \#\operatorname{SCD}(\{0,1,\ldots,s\}^{n})=n^{(1-o_n(1))(s+1)^n}. \tag*{(91)} # SCD ({ 0 , 1 , … , s } n ) = n ( 1 − o n ( 1 )) ( s + 1 ) n . (91)
The second estimate determines the logarithmic growth. Further questions concern identifying an analogue of the factor 1 / 2 e 1/2e 1/2 e for fixed s ≥ 2 s \ge2 s ≥ 2 and obtaining sharper asymptotic estimates for the number of symmetric chain decompositions of unequal products P s P_s P s .
An algebraic coda on conventions for binomial coefficients
The support-sharp formula (14) contains only binomial coefficients with non-negative upper arguments and hence does not depend on how we extend ordinary binomial coefficients to negative arguments. The proper-subset sums (11) and (13) do depend on that extension, and the elementary convention (6) is the extension the generating function itself supplies.
To see this, write the rank polynomial as
∏ i = 1 n ( 1 − x a i ) 1 ( 1 − x ) n , a i = s i + 1 , (92) \prod_{i=1}^{n}(1-x^{a_i})\frac{1}{(1-x)^n},\qquad a_i=s_i+1, \tag*{(92)} i = 1 ∏ n ( 1 − x a i ) ( 1 − x ) n 1 , a i = s i + 1 , (92)
and expand the n + 1 n+1 n + 1 factors as a Cauchy product. Each of the first n n n series has coefficient 1 1 1 at exponent 0 0 0 , coefficient − 1 -1 − 1 at exponent a i a_i a i , and no other terms, while the last has coefficient ( u + n − 1 n − 1 ) \binom{u+n-1}{n-1} ( n − 1 u + n − 1 ) at exponent u u u . A nonzero contribution to [ x k ] [x^k] [ x k ] therefore selects the subset I ⊆ [ n ] = { 1 , … , n } I\subseteq[n]=\{1,\ldots,n\} I ⊆ [ n ] = { 1 , … , n } of indices for which the exponent a i a_i a i is selected, carries the sign ( − 1 ) ∣ I ∣ (-1)^{|I|} ( − 1 ) ∣ I ∣ , and leaves the exponent k − a I k-a_I k − a I , with a I = ∑ i ∈ I a i a_I=\sum_{i\in I}a_i a I = ∑ i ∈ I a i , for the last factor. That exponent is a power-series index, so it is non-negative by construction: the subsets with a I > k a_I>k a I > k contribute no term at all. They are not annihilated by a convention; they do not arise.
Inclusion–exclusion proceeds differently. Every subset is present from the start, and the terms indexed by a I > k a_I>k a I > k record empty intersections, which the elementary convention sets to zero. Under the polynomial convention, the additional terms change the value of the full transform; the results below identify their total and the proper-subset sum.
Under the polynomial convention mentioned in § 3 , ( u v ) \binom{u}{v} ( v u ) is the polynomial u ( u − 1 ) ⋯ ( u − v + 1 ) / v ! u(u-1)\cdots(u-v+1)/v! u ( u − 1 ) ⋯ ( u − v + 1 ) / v ! in u u u , and for negative u u u this gives
( u v ) = ( − 1 ) v ( − u + v − 1 v ) . (93) \binom{u}{v}=(-1)^v\binom{-u+v-1}{v}. \tag*{(93)} ( v u ) = ( − 1 ) v ( v − u + v − 1 ) . (93)
Proposition 9.1 (The full polynomial transform). Let n ≥ 1 n\ge1 n ≥ 1 and write [ n ] : = { 1 , … , n } [n]:=\{1,\ldots,n\} [ n ] := { 1 , … , n } . Let s = ( s 1 , … , s n ) s=(s_1,\ldots,s_n) s = ( s 1 , … , s n ) have non-negative integer entries, and set a i = s i + 1 a_i=s_i+1 a i = s i + 1 , a I = ∑ i ∈ I a i a_I=\sum_{i\in I}a_i a I = ∑ i ∈ I a i , and N = ∑ i = 1 n s i N=\sum_{i=1}^{n}s_i N = ∑ i = 1 n s i . Under the polynomial convention, for every k ∈ Z k\in\mathbb{Z} k ∈ Z ,
∑ I ⊆ [ n ] ( − 1 ) ∣ I ∣ ( k − a I + n − 1 n − 1 ) = 0. (94) \sum_{I\subseteq[n]}(-1)^{|I|}\binom{k-a_I+n-1}{n-1}=0. \tag*{(94)} I ⊆ [ n ] ∑ ( − 1 ) ∣ I ∣ ( n − 1 k − a I + n − 1 ) = 0. (94)
Proof. Set f ( x ) = ( x + n − 1 n − 1 ) f(x)=\binom{x+n-1}{n-1} f ( x ) = ( n − 1 x + n − 1 ) , a polynomial of degree n − 1 n-1 n − 1 , and define ∇ h f ( x ) = f ( x ) − f ( x − h ) \nabla_h f(x)=f(x)-f(x-h) ∇ h f ( x ) = f ( x ) − f ( x − h ) . With the shift T h f ( x ) = f ( x − h ) T_hf(x)=f(x-h) T h f ( x ) = f ( x − h ) , we have ∇ h = 1 − T h \nabla_h=1-T_h ∇ h = 1 − T h , and since the shifts commute and T a T b = T a + b T_aT_b=T_{a+b} T a T b = T a + b , ∏ i ( 1 − T a i ) = ∑ I ⊆ [ n ] ( − 1 ) ∣ I ∣ T a I \prod_i(1-T_{a_i})=\sum_{I\subseteq[n]}(-1)^{|I|}T_{a_I} ∏ i ( 1 − T a i ) = ∑ I ⊆ [ n ] ( − 1 ) ∣ I ∣ T a I . Hence the left-hand side of (94) is
( ∏ i = 1 n ∇ a i ) f ( k ) . (95) \left(\prod_{i=1}^{n}\nabla_{a_i}\right)f(k). \tag*{(95)} ( i = 1 ∏ n ∇ a i ) f ( k ) . (95)
Since a i ≥ 1 a_i\geq1 a i ≥ 1 , each nonzero-step difference lowers the degree of a nonconstant polynomial by one and annihilates a constant. As f f f has degree n − 1 n-1 n − 1 , applying n n n such operators annihilates it.
Proposition 9.1 is classical. In the equal-step case a 1 = ⋯ = a n a_1=\cdots=a_n a 1 = ⋯ = a n it is the basic annihilation property of the finite difference calculus, Δ n f = 0 \Delta^n f=0 Δ n f = 0 for deg f < n \deg f<n deg f < n [22 §5.3] . The unequal-step form is the dimension-one case of the annihilation relations of Dahmen and Micchelli [16 ] : for a list X X X of vectors, the operators ∏ x ∈ Y ∇ x \prod_{x\in Y}\nabla_x ∏ x ∈ Y ∇ x indexed by the cocircuits Y Y Y of X X X define the discrete Dahmen–Micchelli space, and in dimension one the single cocircuit is all of X X X . Its polynomial solutions are exactly the polynomials of degree at most n − 1 n-1 n − 1 ; the full discrete space can also contain nonpolynomial quasipolynomials.
The Dahmen–Micchelli setting identifies R s R_s R s as the one-dimensional discrete box spline with unit directions and coordinate bounds 0 ≤ k i < a i 0\leq k_i<a_i 0 ≤ k i < a i . Let B s e q ( k ) = ( k + n − 1 n − 1 ) B_{\mathrm{seq}}(k)=\binom{k+n-1}{n-1} B seq ( k ) = ( n − 1 k + n − 1 ) for k ≥ 0 k\geq0 k ≥ 0 , and let B s e q ( k ) = 0 B_{\mathrm{seq}}(k)=0 B seq ( k ) = 0 for k < 0 k<0 k < 0 . Applying ∇ a \nabla_a ∇ a multiplies its generating series by 1 − x a 1-x^a 1 − x a , so
R s = ( ∏ i = 1 n ∇ a i ) B s e q . (96) R_s=\left(\prod_{i=1}^{n}\nabla_{a_i}\right)B_{\mathrm{seq}}. \tag*{(96)} R s = ( i = 1 ∏ n ∇ a i ) B seq . (96)
Under the polynomial convention, B p o l y ( k ) = ( k + n − 1 n − 1 ) B_{\mathrm{poly}}(k)=\binom{k+n-1}{n-1} B poly ( k ) = ( n − 1 k + n − 1 ) extends the same values to a polynomial of degree n − 1 n-1 n − 1 on all integers. Proposition 9.1 gives ( ∏ i = 1 n ∇ a i ) B p o l y = 0 \left(\prod_{i=1}^{n}\nabla_{a_i}\right)B_{\mathrm{poly}}=0 ( ∏ i = 1 n ∇ a i ) B poly = 0 ; Corollary 9.2 identifies the contribution of the extra terms.
Corollary 9.2 (The tail and the proper-subset transform). Under the hypotheses and notation of Proposition 9.1, for 0 ≤ k ≤ N 0\leq k\leq N 0 ≤ k ≤ N the polynomial convention gives
∑ I ⊆ [ n ] a I > k ( − 1 ) ∣ I ∣ ( k − a I + n − 1 n − 1 ) = − R s ( k ) , (97) \sum_{\substack{I\subseteq[n]\\a_I>k}}(-1)^{|I|}\binom{k-a_I+n-1}{n-1}=-R_s(k), \tag*{(97)} I ⊆ [ n ] a I > k ∑ ( − 1 ) ∣ I ∣ ( n − 1 k − a I + n − 1 ) = − R s ( k ) , (97) and
∑ I ⊊ [ n ] ( − 1 ) ∣ I ∣ ( k − a I + n − 1 n − 1 ) = ( N − k + n − 1 n − 1 ) . (98) \sum_{I\subsetneq[n]}(-1)^{|I|}\binom{k-a_I+n-1}{n-1}=\binom{N-k+n-1}{n-1}. \tag*{(98)} I ⊊ [ n ] ∑ ( − 1 ) ∣ I ∣ ( n − 1 k − a I + n − 1 ) = ( n − 1 N − k + n − 1 ) . (98) The right-hand side of (98) equals R s ( k ) R_s(k) R s ( k ) if and only if N − k ≤ min ( s 1 , … , s n ) N-k\leq\min(s_1,\ldots,s_n) N − k ≤ min ( s 1 , … , s n ) .
Proof. If a I ≤ k a_I\leq k a I ≤ k , then k − a I + n − 1 ≥ n − 1 k-a_I+n-1\geq n-1 k − a I + n − 1 ≥ n − 1 , so the elementary and polynomial conventions agree on that term. The subsets satisfying a I ≤ k a_I\leq k a I ≤ k therefore index precisely the nonzero terms of the elementary inclusion–exclusion formula (11) , whose sum is R s ( k ) R_s(k) R s ( k ) . Subtracting this sum from the vanishing transform (94) proves (97) .
For (98) , isolate the term I = [ n ] I=[n] I = [ n ] in (94) . Since a [ n ] = N + n a_{[n]}=N+n a [ n ] = N + n , the proper-subset sum is
− ( − 1 ) n ( k − N − 1 n − 1 ) = ( N − k + n − 1 n − 1 ) . (99) -(-1)^n\binom{k-N-1}{n-1}=\binom{N-k+n-1}{n-1}. \tag*{(99)} − ( − 1 ) n ( n − 1 k − N − 1 ) = ( n − 1 N − k + n − 1 ) . (99)
For the second equality, apply (93) with u = k − N − 1 < 0 u=k-N-1<0 u = k − N − 1 < 0 and v = n − 1 v=n-1 v = n − 1 , which gives ( k − N − 1 n − 1 ) = ( − 1 ) n − 1 ( N − k + n − 1 n − 1 ) \binom{k-N-1}{n-1}=(-1)^{n-1}\binom{N-k+n-1}{n-1} ( n − 1 k − N − 1 ) = ( − 1 ) n − 1 ( n − 1 N − k + n − 1 ) , and note that − ( − 1 ) n ( − 1 ) n − 1 = 1 -(-1)^n(-1)^{n-1}=1 − ( − 1 ) n ( − 1 ) n − 1 = 1 . Proposition 4.1 gives the stated criterion for equality with R s ( k ) R_s(k) R s ( k ) .
Example 9.3 (Three values from one alternating sum). Take ( n , s , k ) = ( 3 , 2 , 2 ) (n,s,k)=(3,2,2) ( n , s , k ) = ( 3 , 2 , 2 ) , so N = 6 N=6 N = 6 . The proper-subset sum in (13) is
( 4 2 ) − 3 ( 1 2 ) + 3 ( − 2 2 ) \binom{4}{2}-3\binom{1}{2}+3\binom{-2}{2} ( 2 4 ) − 3 ( 2 1 ) + 3 ( 2 − 2 )
Under the elementary convention it equals ( 3 2 ) 2 = 6 \binom{3}{2}_2 = 6 ( 2 3 ) 2 = 6 . Under the polynomial convention, ( − 2 2 ) = 3 \binom{-2}{2} = 3 ( 2 − 2 ) = 3 , so the same expression equals 6 + 9 = 15 6 + 9 = 15 6 + 9 = 15 . Including the final term gives the full polynomial transform
6 + 9 − ( − 5 2 ) = 6 + 9 − 15 = 0. 6 + 9 - \binom{-5}{2} = 6 + 9 - 15 = 0. 6 + 9 − ( 2 − 5 ) = 6 + 9 − 15 = 0.
The value 15 = ( 6 2 ) 15 = \binom{6}{2} 15 = ( 2 6 ) is the unrestricted enumeration for the complementary total N − k = 4 N-k = 4 N − k = 4 , as in (98) ; the extra polynomial terms in the full transform sum to 9 − 15 = − 6 9 - 15 = -6 9 − 15 = − 6 , as in (97) .
Remark 9.4. Equation (98) is a reciprocity statement. Its proof turns on the upper negation (93) , which, when applied to B p o l y B_{\mathrm{poly}} B poly , gives the classical reciprocity for the simplex: under the polynomial convention and for integers k ≥ 1 k \ge1 k ≥ 1 , ( − 1 ) n − 1 B p o l y ( − k ) (-1)^{n-1}B_{\mathrm{poly}}(-k) ( − 1 ) n − 1 B poly ( − k ) is the number of solutions of k 1 + ⋯ + k n = k k_1+\cdots+k_n=k k 1 + ⋯ + k n = k in strictly positive integers. The reciprocity of the rank polynomial itself is the palindromic symmetry (20) , proved in § 4 by the complement bijection; (98) uses the simplex reciprocity above, applied to the single term indexed by I = [ n ] I=[n] I = [ n ] . In this form, the proper-subset transform is the unrestricted enumeration for the complementary total N − k N-k N − k , and by Proposition 4.1 it agrees with the bounded enumeration exactly in the upper boundary regime.
When all s i = s s_i=s s i = s , grouping subsets by their cardinality reduces (94) to the full homogeneous transform. Under the polynomial convention, the same grouping reduces (98) to
∑ j = 0 n − 1 ( − 1 ) j ( n j ) ( k − j ( s + 1 ) + n − 1 n − 1 ) = ( n s − k + n − 1 n − 1 ) , 0 ≤ k ≤ n s . (100) \sum_{j=0}^{n-1}(-1)^j\binom{n}{j}\binom{k-j(s+1)+n-1}{n-1}=\binom{ns-k+n-1}{n-1},\qquad0\le k\le ns. \tag*{(100)} j = 0 ∑ n − 1 ( − 1 ) j ( j n ) ( n − 1 k − j ( s + 1 ) + n − 1 ) = ( n − 1 n s − k + n − 1 ) , 0 ≤ k ≤ n s . (100)
Under the elementary convention, the same alternating sum equals ( n k ) s \binom{n}{k}_s ( k n ) s by (13) . For ( n − 1 ) s ≤ k ≤ n s (n-1)s\le k\le ns ( n − 1 ) s ≤ k ≤ n s , all of its upper arguments are non-negative, so the two conventions agree term by term and (100) reduces to (26) . The polynomial convention thus extends this upper boundary identity to the whole admissible range, where it no longer computes ( n k ) s \binom{n}{k}_s ( k n ) s .
Concluding remarks
The rank polynomial links bounded compositions and rank sizes of products of chains with discrete-uniform sums and S U ( 2 ) \mathrm{SU}(2) SU ( 2 ) tensor-product characters. The complement involution gives coefficient symmetry and rank reversal and transfers the lower-boundary figurate-number identity to the upper boundary. Combined with the support-sharp inclusion–exclusion formula, the involution reduces the alternating sum to one term at either boundary and roughly halves the worst-case number of summands (Corollary 4.4). At the level of profiles, Proposition 6.1 equates the number of chains beginning at each rank with the corresponding irreducible multiplicity and equates chain lengths with constituent dimensions. The de Bruijn–Tengbergen–Kruyswijk induction mirrors the Clebsch–Gordan rule (Remark 6.2). Both statements hold for unequal bounds and hence for mixed spins.
For equal bounds, convolution gives log-concavity and an exact central mode. The Gaussian local approximation determines the asymptotic size of the central coefficient, while a higher-order local expansion determines the central first difference, which is smaller by a factor of order n n n . Corollary 5.2 gives the explicit 1 / n 1/n 1/ n corrections to both leading terms. This difference in order underlies the passage from binomial-type coefficients to Catalan-type first differences. At the boundary, Proposition 8.2 identifies n s / ( s + 1 ) n^{s/(s+1)} n s / ( s + 1 ) as the first crossover scale for D n , s ( k ) D_{n,s}(k) D n , s ( k ) , with limiting correction e − α s s + 1 e^{-\alpha s^{s+1}} e − α s s + 1 . Corollary 8.3 extends this limit to unequal bounds, with factor e − α λ s + 1 e^{-\alpha\lambda^{s+1}} e − α λ s + 1 when the fraction of bounds equal to the fixed minimum s s s tends to α > 0 \alpha>0 α > 0 . A central rank layer is also a largest antichain, which underpins the coding application of § 7.4 .
Under the polynomial convention, the full inclusion–exclusion transform vanishes (Proposition 9.1), and the terms suppressed by the elementary convention sum to − R s ( k ) -R_s(k) − R s ( k ) (Corollary 9.2). The proper-subset transform returns ( N − k + n − 1 n − 1 ) \binom{N-k+n-1}{n-1} ( n − 1 N − k + n − 1 ) instead, so changing the convention replaces the bounded enumeration by the unrestricted enumeration for the complementary total.
Further questions concern compatibility of q q q -deformed chain models with the nested-hook construction, optimization of weighted levels under signature-scheme constraints, and sharper asymptotic estimates for the number of symmetric chain decompositions of homogeneous and unequal products.
CRediT authorship contribution statement
Hacène Belbachir: Conceptualization, formal analysis, investigation, validation, writing – review & editing. José Ricardo G. Mendonça: Conceptualization, formal analysis, investigation, validation, writing – original draft, writing – review & editing.
Declaration of generative AI and AI-assisted technologies in the writing process
During the preparation of this manuscript the authors used Anthropic’s Claude Opus 5.5 and OpenAI’s GPT-6.1-Sol AI models for drafting assistance and algebraic and numerical checking of displayed identities. The authors planned, surveyed, and prepared the majority of the manuscript, reviewed and revised the AI-assisted material, and take full responsibility for the content of the publication.
Funding
H.B. acknowledges support from the RECITS Laboratory, USTHB, and DG-RSDT, Algeria. J.R.G.M. thanks FAPESP, Brazil, for partial support through research grant no. 2020/04475-7.
Data availability
No datasets were used or generated in this work. The curves in Figure 3 were computed in Python from the coefficient formulas in the manuscript.
Declaration of competing interest
The authors have no relevant financial or non-financial interests to disclose.