betaFeedback

WorksMathematics

Bounded compositions and products of chains, or bi(s)nomials everywhere from de Moivre's formula to spin multiplicities and constant-sum codes

Abstract

How many ways are there to select kk objects from nn types when type ii is available in only sis_{i} copies? For equal bounds, this is de Moivre's problem of obtaining a prescribed total with nn dice, now a textbook application of the principle of inclusion-exclusion. For arbitrary bounds, the answer is encoded by the rank polynomial ∏i=1n(1+x+⋯+xsi)\prod_{i=1}^{n}(1+x+\cdots+x^{s_{i}}). Its coefficients enumerate bounded compositions and submultisets, give, after normalization, the probability mass function of a sum of independent discrete uniform random variables, and are the weight multiplicities of a tensor product of SU(2)\mathrm{SU}(2) representations. Most of these interpretations are classical but dispersed; here we place them in a common notation and document their provenance. A complement involution proves symmetry and boundary identities. For arbitrary bounds, lower-half first differences give both symmetric-chain starts and mixed-spin multiplicities, and the chain-length and irreducible-dimension profiles agree. Convolution gives log-concavity and the central mode. For equal bounds with fixed s≥1s \geq 1 and even nsns, local expansions give central asymptotics with explicit 1/n1/n and 1/n21/n^{2} corrections for the coefficient and its first difference. A Poisson limit gives the first boundary crossover of these differences at scale k∼λns/(s+1)k \sim λn^{s/(s+1)}, with factor e−αλs+1e^{-αλ^{s+1}} when the proportion of bounds equal to the fixed minimum s≥1s \geq 1 tends to α>0α>0. Central first differences include the ss-Catalan numbers, themselves Littlewood-Richardson coefficients; central layers yield maximum-size constant-sum codebooks for hash-based signatures. Under the polynomial binomial convention, the full inclusion-exclusion transform vanishes, and the omitted terms sum to the negative of the number of bounded compositions.

Introduction

Let s=(s1,…,sn)\mathbf{s}=(s_1,\ldots,s_n) be a vector of non-negative integers and put N=s1+⋯+snN=s_1+\cdots+s_n. For 0≤k≤N0\le k\le N, let Rs(k)R_{\mathbf{s}}(k) be the number of integer solutions of

k1+⋯+kn=k,0≤ki≤si,i=1,…,n,(1)k_1+\cdots+k_n=k,\qquad0\le k_i\le s_i,\qquad i=1,\ldots,n, \tag*{(1)}

or, equivalently,

Rs(k)=[xk]∏i=1n(1+x+⋯+xsi).(2)R_{\mathbf{s}}(k)=[x^k]\prod_{i=1}^{n}(1+x+\cdots+x^{s_i}). \tag*{(2)}

Set Rs(k)=0R_{\mathbf{s}}(k)=0 for k<0k<0 or k>Nk>N. In the multiset model, type ii has sis_i indistinguishable objects, of which we choose kik_i. Thus Rs(k)R_{\mathbf{s}}(k) gives the number of size-kk submultisets of a multiset of total size NN.

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 si=2σis_i = 2\sigma_i, with each σi∈12Z≥0\sigma_i \in\frac{1}{2}\mathbb{Z}_{\ge0}, 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 si=ss_i=s with even n=2νn=2\nu, the central first difference is the ss-Catalan number, which Linz identifies with a value of a Littlewood–Richardson stretching polynomial. For s=1s=1 and s=2s=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.

Interpretation of Rs(k)R_s(k)SpecializationSection(s)
Bounded compositions; size-kk submultisetsgeneral ss§ 3–§ 4
Probability mass function of a discrete uniform sum (after normalization)general ss§ 5, § 8
Rank sizes of a product of chains ∏i[0,si]\prod_i[0,s_i]general ss§ 6
One-dimensional discrete box splinegeneral ss§ 9
Weight multiplicities in ⨂iVσi\bigotimes_i V_{\sigma_i}si=2σis_i=2\sigma_i§ 7.1
Irreducible multiplicities (lower-half first differences)si=2σis_i=2\sigma_i§ 7.1
Central first differences: ss-Catalan and Littlewood–Richardson coefficientssi=ss_i=s, n=2νn=2\nu§ 7.2
Constant-sum antichains for hash-based signaturessi=ss_i=s, k=⌊ns/2⌋k=\lfloor ns/2\rfloor§ 7.4

Table 1. Several interpretations of the coefficient array Rs(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, nn denotes the number of types, cells, or particles, depending on the interpretation. The integer kk is the prescribed total, and kik_i is the contribution of the component indexed by ii. The individual upper bounds are sis_i; in the homogeneous case they all equal ss, and N=s1+⋯+snN=s_1+\cdots+s_n is the maximum possible total. We use Rs(k)R_s(k) for the inhomogeneous enumeration in (2) and write (nk)s\binom{n}{k}_s when all bounds equal ss. In the representation-theoretic sections, σ\sigma denotes a single-particle spin, mm the total magnetization, and JJ the total spin; when the number of particles is even, we write n=2νn=2\nu. The symbol qq is reserved for deformation parameters.

The homogeneous notation (nk)s\binom{n}{k}_s follows Belbachir and Benmezai [4] and Linz [26]; the notation Rs(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 (nk)s\binom{n}{k}_s, defined by the expansion

(1+x+x2+⋯+xs)n=∑k≥0(nk)sxk,(nk)s=0 for k<0 or k>ns.(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)}

Other names for these coefficients include ordinary multinomial coefficients, polynomial coefficients, and extended or generalized binomial coefficients of order s+1s+1. Here polynomial coefficients names the array, not the convention for ordinary binomial coefficients that we discuss in § 9. For s=1s=1, the coefficients reduce to the ordinary binomial coefficients, (k1)=(kk)\binom{k}{1}=\binom{k}{k}. The full coefficient array is the bisnomial triangle, also called the ss-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 bisnomial 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 nn dice having s+1s+1 numbered faces. De Moivre stated the problem for general nn and ss 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 (nk)s\binom{n}{k}_{s} as the number of distributions of kk objects among nn cells with at most ss 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 A1,…,AMA_1,\ldots,A_M of a finite set SS, the first is the principle of inclusion–exclusion in the form

∣S∖⋃i=1MAi∣=∑I⊆{1,…,M}(−1)∣I∣∣⋂i∈IAi∣(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)}

where the intersection indexed by the empty set is SS. The second is the stars-and-bars formula for the number of non-negative solutions of k1+⋯+kn=kk_1+\cdots+k_n=k, namely

(k+n−1n−1)=(k+n−1k)(5)\binom{k+n-1}{n-1}=\binom{k+n-1}{k} \tag*{(5)}

where the equality follows from the symmetry of the ordinary binomial coefficient.

By default, we use the elementary convention for binomial coefficients

(uv)=0unless0≤v≤u.(6)\binom{u}{v}=0\quad\text{unless}\quad0\leq v\leq u. \tag*{(6)}

This convention is standard in the bisnomial 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, (uv)\binom{u}{v} is the polynomial u(u−1)⋯(u−v+1)/v!u(u-1)\cdots(u-v+1)/v! in uu for each fixed integer v≥0v\geq0.

Enumeration in the inhomogeneous case

For 0≤k≤N0\leq k\leq N, let SS be the set of non-negative integer solutions of k1+⋯+kn=kk_1+\cdots+k_n=k, without the upper bounds in (1). The stars-and-bars formula gives

Σ0=∣S∣=(k+n−1n−1).(7)\Sigma_0=|S|=\binom{k+n-1}{n-1}. \tag*{(7)}

For each ii, let Ai⊆SA_i \subseteq S be the set of solutions that violate the upper bound on kik_i, so that ki≥si+1k_i \ge s_i+1. Writing ki=si+1+bik_i=s_i+1+b_i gives a bijection between AiA_i and the non-negative solutions of

k1+⋯+bi+⋯+kn=k−(si+1),(8)k_1+\cdots+b_i+\cdots+k_n=k-(s_i+1), \tag*{(8)}

whose number is, by (5), (k−(si+1)+n−1n−1)\binom{k-(s_i+1)+n-1}{n-1}. Hence

Σ1=∑i=1n∣Ai∣=∑i=1n(k−(si+1)+n−1n−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)}

For distinct indices i1,…,iji_1,\ldots,i_j, shifting the corresponding jj coordinates reduces the prescribed total by ∑l=1j(sil+1)\sum_{l=1}^{j}(s_{i_l}+1). Summing over all jj-element sets of indices gives

References

  1. [1]G. Almkvist, W. Dicks, and E. Formanek, Hilbert series of fixed free algebras and noncommutative classical invariant theory, J. Algebra 93 (1) (1985), 189–214. doi:10.1016/0021-8693(85)90183-8DOI
  2. [2]A. Bazeniar, M. Ahmia, and H. Belbachir, Connection between biˢnomial coefficients and their analogs and symmetric functions, Turkish J. Math. 42 (2018), 807–818. doi:10.3906/mat-1705-27DOI
  3. [3]H. Belbachir, Determining the mode for convolution powers of discrete uniform distribution, Probab. Engrg. Inform. Sci. 25 (4) (2011), 469–475. doi:10.1017/S0269964811000131DOI
  4. [4]H. Belbachir and A. Benmezai, A q-analogue for biˢnomial coefficients and generalized Fibonacci sequences, C. R. Acad. Sci. Paris Sér. I 352 (2014), 167–171. doi:10.1016/j.crma.2014.01.009DOI
  5. [5]H. Belbachir, S. Bouroubi, and A. Khelladi, Connection between ordinary multinomials, Fibonacci numbers, Bell polynomials and discrete uniform distribution, Ann. Math. Inform. 35 (2008), 21–30.
  6. [6]H. Belbachir and O. Iguergouera, Combinatorial interpretation of biˢnomial coefficients and generalized Catalan numbers, in: Proc. 1st Int. Conf. on Algebras, Graphs and Ordered Sets (ALGOS 2020), 2020, pp. 47–54. https://hal.science/hal-02918958
  7. [7]H. Belbachir and O. Iguergouera, Congruence properties for biˢnomial coefficients and like extended Ram and Kummer theorems under suitable hypothesis, Mediterr. J. Math. 17:36 (2020), 14 pp. doi:10.1007/s00009-019-1457-0DOI
  8. [8]H. Belbachir and L. Szalay, Unimodal rays in the ordinary and generalized Pascal triangles, J. Integer Seq. 11 (2008), Article 08.2.4.
  9. [9]E. A. Bender, Central and local limit theorems applied to asymptotic enumeration, J. Combin. Theory Ser. A 15 (1) (1973), 91–111. doi:10.1016/0097-3165(73)90038-1DOI
  10. [10]P. Biane, P. Bougerol, and N. O’Connell, Littelmann paths and Brownian paths, Duke Math. J. 130 (1) (2005), 127–167. doi:10.1215/S0012-7094-05-13014-9DOI
  11. [11]B. A. Bondarenko, Generalized Pascal Triangles and Pyramids, Their Fractals, Graphs and Applications, The Fibonacci Association, Santa Clara, 1993. Translated from the Russian by R. C. Bollinger.
  12. [12]Ch. A. Charalambides, On the enumeration of certain compositions and related sequences of numbers, Fibonacci Quart. 20 (2) (1982), 132–146. doi:10.1080/00150517.1982.12430010DOI
  13. [13]Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, FL, 2002. doi:10.1201/9781315273112
  14. [14]E. Cohen, T. Hansen, and N. Itzhaki, From entanglement witness to generalized Catalan numbers, Sci. Rep. 6 (2016), 30232. doi:10.1038/srep30232DOI
  15. [15]T. Curtwright, T. S. Van Kortryk, and C. K. Zachos, Spin multiplicities, Phys. Lett. A 381 (5) (2017), 422–427. doi:10.1016/j.physleta.2016.12.006
  16. [16]W. Dahmen and C. A. Micchelli, The number of solutions to linear Diophantine equations and multivariate splines, Trans. Amer. Math. Soc. 308 (2) (1988), 509–532. doi:10.1090/S0002-9947-1988-0951619-XDOI
  17. [17]N. G. de Bruijn, C. van Ebbenh​orst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde (2) 23 (1951), 191–193.
  18. [18]J.-M. Deshouillers, Valeur maximale des coefficients p-nomiaux d’ordre n, C. R. Acad. Sc. Paris Sér. A 278 (1974), 401–404. gallica:ark:/12148/bpt6k6236963/f415.item
  19. [19]A. V. Doumas, An alternative approach to a problem by A. de Moivre, Math. Gaz. 97 (540) (2013), 446–454. doi:10.1017/S002555720000019XDOI
  20. [20]S. Eger, Stirling’s approximation for central extended binomial coefficients, Amer. Math. Monthly 121 (2014), 344–349. doi:10.4169/amer.math.monthly.121.04.344DOI
  21. [21]J. E. Freund, Restricted occupancy theory—A generalization of Pascal’s triangle, Amer. Math. Monthly 63 (1) (1956), 20–27. doi:10.1080/00029890.1956.11988751DOI
  22. [22]R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison–Wesley, Reading, MA, 1994.
  23. [23]J. R. Griggs, Maximum antichains in the product of chains, Order 1 (1) (1984), 21–28. doi:10.1007/BF00396270DOI
  24. [24]J. A. Gyamfi and V. Barone, On the composition of an arbitrary collection of SU(2) spins: An enumerative combinatoric approach, J. Phys. A: Math. Theor. 51 (10) (2018), 105202. doi:10.1088/1751-8121/aaa8faDOI
  25. [25]A. de Moivre, A. Hald: ‘De Mensura Sortis’ or ‘On the Measurement of Chance’, Int. Statist. Rev. 52 (3) (1984), 229–262. (Annotated translation of de Moivre’s 1711 memoir.) doi:10.2307/1403045DOI
  26. [26]W. Linz, s-Catalan numbers and Littlewood–Richardson polynomials, Enumer. Comb. Appl. 2 (2) (2022), Article S2R14. doi:10.54550/ECA2022V2S2R14DOI
  27. [27]P. A. MacMahon, An Introduction to Combinatory Analysis, Cambridge University Press, Cambridge, 1920.
  28. [28]J. R. G. Mendonça, Exact eigenspectrum of the symmetric simple exclusion process on the complete, complete bipartite, and related graphs, J. Phys. A: Math. Theor. 46 (29) (2013), 295001. doi:10.1088/1751-8113/46/29/295001DOI
  29. [29]J. R. G. Mendonça, Statistical thermodynamics of the quantum spin-s XXZ Heisenberg model in the Weiss limit, Nucl. Phys. B 1032 (2026), 117688. doi:10.1016/j.nuclphysb.2026.117688DOI
  30. [30]V. V. Menon and N. K. Indira, A Poisson approximation in an urn model with indistinguishable balls, J. Statist. Plann. Inference 26 (1990), 93–101. doi:10.1016/0378-3758(90)90098-FDOI
  31. [31]P. Mounaix, S. N. Majumdar, and G. Schehr, Statistics of the number of records for random walks and Lévy flights on a 1D lattice, J. Phys. A: Math. Theor. 53 (2020), 415003. doi:10.1088/1751-8121/abac97DOI
  32. [32]T. Neuschel, A note on extended binomial coefficients, J. Integer Seq. 17 (2014), Article 14.10.4.arxiv.org/abs/1407.7429
  33. [33]L. P. Perin, G. Zambonin, R. Custódio, L. Moura, and D. Panario, Improved constant-sum encodings for hash-based signatures, J. Cryptogr. Eng. 11 (2021), 329–351. doi:10.1007/s13388-021-00264-9DOI
  34. [34]V. V. Petrov, Sums of Independent Random Variables, Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 82, Springer-Verlag, Berlin, Heidelberg, and New York, 1975. Translated from the Russian by A. A. Brown. doi:10.1007/978-3-642-65809-9DOI
  35. [35]A. P. Polychronakos and K. Sfetsos, Composition of many spins, random walks and statistics, Nucl. Phys. B 913 (2016), 664–693. doi:10.1016/j.nuclphysb.2016.09.023DOI
  36. [36]R. A. Proctor, Representations of sl(2, C) on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (2) (1982), 275–280. doi:10.1137/0603026DOI
  37. [37]J. Riordan, An Introduction to Combinatorial Analysis, Wiley, New York, 1958.
  38. [38]A. Schilling and S. O. Warnaar, Supernomial coefficients, polynomial identities and q-series, Ramanujan J. 2 (1998), 459–494. doi:10.1023/A:1009780810189DOI
  39. [39]A. Schilling and S. O. Warnaar, Inhomogeneous lattice paths, generalized Kostka polynomials and Aₙ₋₁ supernomials, Commun. Math. Phys. 202 (2) (1999), 359–401. doi:10.1007/s002200050586DOI
  40. [40]M. K. Srinivasan, Symmetric chains, Gelfand–Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme, J. Algebraic Combin. 34 (2) (2011), 301–322. doi:10.1007/s10801-010-0272-2DOI
  41. [41]R. P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (2) (1980), 168–184. doi:10.1137/0601021DOI
  42. [42]I. Tomon, The number of symmetric chain decompositions, Proc. Amer. Math. Soc. 153 (4) (2025), 1511–1518. doi:10.1090/proc/17142DOI
  43. [43]D. B. West, Combinatorial Mathematics, Cambridge University Press, Cambridge, 2021.
  44. [44]K. Zhang, H. Cui, and Y. Yu, Revisiting the constant-sum Winternitz one-time signature with applications to SPHINCS⁺ and XMSS, in: H. Handschuh and A. Lysyanskaya (Eds.), Advances in Cryptology — CRYPTO 2023, Lecture Notes in Computer Science, vol. 14085, Springer, Cham, 2023, pp. 455–483. doi:10.1007/978-3-031-38554-4_15DOI

Paper details

vlnc:W_cjs69mk2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5.5 (bare), GPT-6.1 Sol (bare)

View statement
Looking for related papers…
Contents