The design whose blocks consist of all \(k\)-element multisets drawn from a \(v\)-set, denoted \(M(v,k)\), is a classical example of a balanced \((k+1)\)-ary design. Although its parameters are well known, existing derivations often rely on general multiset design theory. This paper gives unified elementary derivations of the parameters \(b\), \(r\), and \(\lambda\) using stars-and-bars and double counting. We exhibit a natural multiplicity-layer decomposition: removing \(s\) copies of a fixed point from all blocks in which it has multiplicity exactly \(s\) yields a family of subdesigns naturally in bijection with \(M(v-1,k-s)\). This viewpoint clarifies the recursive structure underlying complete multiset designs. Finally, the multiplicity vectors of blocks of \(M(v,k)\) form a \((k+1)\)-ary code of length \(v\) with constant coordinate sum \(k\) and minimum Hamming distance \(2\), achieving size \(\binom{v+k-1}{k}\).
Balanced \(n\)-ary designs, first formalized by Tocher [9], generalize balanced incomplete block designs by allowing repeated elements within a block. Comprehensive surveys are given by Billington [2, 3], while Assaf, Hartman, and Mendelsohn [1], McSorley and Phillips [7], and Phillips and Wallis [8] provide further foundational and recent results.
The complete multiset design \(M(v,k)\) provides a canonical example. Its blocks consist of all \(k\)-element multisets drawn from a \(v\)-set \(E=\{1,\dots,v\}\), each occurring exactly once. Since a point \(x\) may appear with multiplicity \(0 \le m_x(B) \le k\), the design \(M(v,k)\) is \((k+1)\)-ary. In general, a balanced \(n\)-ary design on \(v\) points with block size \(k\) is a collection of \(k\)-multisets such that the entries of the incidence matrix are elements of \(\{0, 1, \dots, n-1\}\) and every unordered 2-multiset \(\{x,y\}\) (allowing repetition) occurs together in exactly \(\lambda\) blocks [9, 2]. Throughout this paper we adopt the support-containment convention: \[\lambda(x,y) := \#\{B : m_x(B)\ge 1,\, m_y(B)\ge 1\}.\]
(The weighted alternative \(\sum\limits_B m_x(B)m_y(B)=\binom{v+k-1}{k-2}\) is noted only for contrast and is not used here.) For \(M(v,k)\) we prove \(\lambda(x,y)=\binom{v+k-3}{k-2}\).
While the properties of \(M(v,k)\) have been studied in the context of general \(n\)-ary designs [2, 9], the literature often treats its parameters as a specialized case of more complex existence theorems. Our contribution is an expository synthesis that offers a new unifying viewpoint; specifically, we demonstrate that the design’s properties arise naturally from the “hockey-stick” identity and a stars-and-bars framework. This approach provides a substantially simplified derivation of the parameters compared to standard recursive methods.
The purpose of this paper is twofold: first, to derive the parameters \(b\), \(r\), and \(\lambda\) using only stars-and-bars and double counting; second, to formalize a multiplicity-layer decomposition by stratifying blocks according to the multiplicity of a fixed point. This decomposition illustrates how the collection of complete multiset designs can be viewed as a graded family, where each design is partitioned into sub-structures isomorphic to designs of lower arity. These contributions—simplified proofs plus unifying decomposition—offer a self-contained treatment accessible without general multiset design theory, while revealing \(M(v,k)\)’s natural layered architecture.
Existing literature typically derives parameters for \(M(v,k)\) through the lens of \((\nu, k, \lambda)\)-designs or general incidence matrix algebra. In contrast, the following proofs utilize only basic combinatorial principles, providing a direct and transparent verification of the parameter set.
For a multiset block \(B\), let \(m_x(B)\) denote the multiplicity of point \(x\).
Theorem 2.1. For integers \(v\ge 2\) and \(k\ge 1\), the design \(M(v,k)\) is a balanced \((k+1)\)-ary design with parameters \[b=\binom{v+k-1}{k},\quad r=\binom{v+k-1}{k-1}\quad\text{(total point-occurrences with multiplicity)},\] \[\quad \lambda=\binom{v+k-3}{k-2}\quad\text{(support-containment)},\] where \(\binom{n}{k}=0\) for \(k<0\) or \(n<k\).
Proof. Each block corresponds to a nonnegative integer solution of \(x_1+\cdots+x_v=k\), so \[b=\binom{v+k-1}{k},\] by stars-and-bars. Total point-occurrences are \(bk\), hence \(vr=bk\). Here \(r\) denotes the total multiplicity of each point across all blocks (i.e., \(\sum\limits_B m_x(B)\)), not merely the number of blocks containing \(x\). The identity \[k\binom{v+k-1}{k}=v\binom{v+k-1}{k-1},\] yields \(r=\binom{v+k-1}{k-1}\).
To compute \(\lambda\), fix distinct points \(x,y\in E\). We count the number of blocks that contain at least one copy of \(x\) and at least one copy of \(y\). By pre-allocating one copy of \(x\) and one copy of \(y\) (to guarantee the “at least one” condition), we distribute the remaining \(k-2\) indistinguishable units among all \(v\) points (including \(x\) and \(y\)), allowing zero allocations. This is the number of nonnegative integer solutions to \(x_1+\cdots+x_v=k-2\), which by stars-and-bars is \[\lambda=\binom{v+(k-2)-1}{k-2}=\binom{v+k-3}{k-2}.\] ◻
For repeated pairs of the form \(\{x,x\}\) (i.e., \(m_x(B)\ge 2\)), the support-containment count is obtained analogously: pre-allocate two copies of \(x\) and distribute the remaining \(k-2\) indistinguishable units freely among all \(v\) points (repetition allowed). This yields \[\#\{B\in M(v,k):m_x(B)\ge 2\}=\binom{v+(k-2)-1}{k-2}=\binom{v+k-3}{k-2}.\]
Thus, under our support-containment convention, the value of \(\lambda\) is the same for both distinct pairs \(\{x,y\}\) (\(x\neq y\)) and repeated pairs \(\{x,x\}\).
Remark 2.2. In the general theory of balanced \(n\)-ary designs, the standard consistency condition involves the weighted incidence sum \(\sum\limits_B m_x(B)m_y(B)\) [9, 2]. Under our support-containment convention \(\lambda(x,y)=\#\{B:m_x(B)\ge1,\,m_y(B)\ge1\}\), this weighted sum equals \[\sum\limits_B m_x(B)m_y(B)=\binom{v+k-1}{k-2},\] which is strictly larger than \(\lambda=\binom{v+k-3}{k-2}\) (with equality if and only if \(m_x(B)=m_y(B)=1\) in every block that contains both points). The pre-allocation argument in the proof of Theorem 2.1 confirms consistency under the chosen convention.
As a numerical illustration of Theorem 2.1, Table 1 lists the parameters \((b,r,\lambda)\) for several small values of \(v\) and \(k\).
| \(v \setminus k\) | \(k=2\) | \(k=3\) | \(k=4\) | \(k=5\) |
|---|---|---|---|---|
| 3 | (6, 4, 1) | (10, 10, 3) | (15, 20, 6) | (21, 35, 10) |
| 4 | (10, 5, 1) | (20, 15, 4) | (35, 35, 10) | (56, 70, 20) |
| 5 | (15, 6, 1) | (35, 21, 5) | (70, 56, 15) | (126, 126, 35) |
| 6 | (21, 7, 1) | (56, 28, 6) | (126, 84, 21) | (252, 210, 56) |
Fix a point \(x\in E\) and an integer \(s\) with \(0\le s\le k\). Define \[M_x^{(s)}=\bigl\{\,B\setminus (s\text{ copies of }x)\,:\,B\in M(v,k),\ m_x(B)=s\,\bigr\}.\]
Here \(B\setminus (s\text{ copies of }x)\) denotes the \((k-s)\)-multiset obtained from \(B\) by reducing the multiplicity of \(x\) by \(s\) and leaving all other multiplicities unchanged.
Lemma 3.1(Multiplicity Decomposition).The block set of \(M(v,k)\) is the disjoint union \[M(v,k)=\bigsqcup_{s=0}^k M_x^{(s)}.\]
Proof. The layers \(M_x^{(s)}\) partition \(M(v,k)\) by definition of multiplicity, and are nonempty precisely when \(0\le s\le k\). ◻
The key insight is the multiplicity-layer decomposition, which provides the first explicit isomorphism between fixed-multiplicity layers and complete designs on reduced parameters:
Theorem 3.2(Multiplicity-Layer Decomposition).For \(0\le s\le k\), the layer \(M_x^{(s)}\) is isomorphic to \(M(v-1,k-s)\) via the elementary bijection \(B \mapsto B \setminus \{x^s\}\). Consequently, \(M_x^{(s)}\) inherits the balanced \((k-s+1)\)-ary parameters \((b', r', \lambda')\) directly from \(M(v-1,k-s)\) as: \[b'=\binom{v+k-s-2}{k-s},\quad r'=\binom{v+k-s-2}{k-s-1},\quad \lambda'=\binom{v+k-s-3}{k-s-2}.\]
Remark 3.3. By the convention \(\binom{n}{k}=0\) for \(k<0\) or \(n<k\), the parameter formulas remain valid in boundary cases such as \(k-s\le 1\), where \(\lambda'=0\).
Proof. A block \(B\) with \(m_x(B)=s\) admits a unique decomposition \(B=\{x^s\}\uplus B'\), where \(B'\) is a \((k-s)\)-multiset on \(E\setminus\{x\}\). Since \(M(v,k)\) contains every \(k\)-multiset exactly once, it follows that \(M_x^{(s)}\) contains every \((k-s)\)-multiset on \(v-1\) points exactly once. Hence \(M_x^{(s)} \cong M(v-1,k-s)\). The stated parameters follow by substituting \(v\mapsto v-1\) and \(k\mapsto k-s\) into Theorem 2.1. ◻
Remark 3.4. The decomposition \[M(v,k)=\bigsqcup_{s=0}^k M_x^{(s)},\] immediately implies the classical generating function identity
\[\frac{1}{(1-x)^v} = \frac{1}{1-x} \cdot \frac{1}{(1-x)^{v-1}},\] where the factor \(1/(1-x)=\sum\limits_{s\ge0}x^s\) enumerates multiplicities of \(x\) and \(1/(1-x)^{v-1}\) enumerates \((k-s)\)-multisets on \(E\setminus\{x\}\). Thus the multiplicity-layer structure reflects the canonical combinatorial product decomposition underlying the generating function. Extracting coefficients of \(x^k\) in this identity yields Corollary 3.8.
Corollary 3.5(Recurrence for the Replication Number \(r\)).The replication number \(r\) of \(M(v,k)\) satisfies: \[r = \sum\limits_{s=1}^{k} s \cdot |M_x^{(s)}| = \sum\limits_{s=1}^{k} s \binom{v+k-s-2}{k-s}.\]
This identity reflects the fact that the total occurrences of point \(x\) are distributed across layers where it appears with multiplicity exactly \(s\).
Remark 3.6. Using \(|M_x^{(s)}|=\binom{v+k-s-2}{k-s}\) and summing over \(s\) recovers \[r=\binom{v+k-1}{k-1}=\frac{k}{v}\binom{v+k-1}{k},\] which is equivalent to the standard relation \(vr=bk\) and confirms internal parameter consistency of \(M(v,k)\).
Remark 3.7. Reindexing with \(t=k-s\) gives \[\binom{v+k-1}{k} = \sum\limits_{t=0}^{k} \binom{v+t-2}{t},\] which is the classical “hockey-stick” identity or multichoose recurrence [6]. Thus the multiplicity-layer decomposition endows the family \(\{M(v,k)\}\) with a graded recursive structure analogous to Pascal’s identity for ordinary binomial coefficients.
Corollary 3.8(Multiplicity Recurrence).\[\binom{v+k-1}{k} = \sum\limits_{s=0}^k \binom{v+k-s-2}{k-s}.\]
Proof. By Lemma 3.1, the blocks partition into layers \(M_x^{(s)}\). By Theorem 3.2, each layer has size \(\binom{v+k-s-2}{k-s}\). Summing over \(s\) yields the identity. ◻
Corollary 3.9. Iterated application of the multiplicity-layer decomposition recovers the entire family of balanced \(n\)-ary complete multiset designs on \(v-j\) points for every \(n \ge 2\) and every admissible \(j \ge 0\). In particular, successive multiplicity reductions generate all complete multiset designs of smaller arity and smaller ground set, illustrating the nested recursive architecture of the \(M(v,k)\) family.
Example 3.10. Consider the design \(M(6,4)\), a balanced \(5\)-ary design with parameters \((b,r,\lambda)=(126,84,21)\) as shown in Table 1.
1. Fixing a point \(x \in E\) and selecting the layer \(s=2\) yields a subdesign \(M_x^{(2)} \cong M(5,2)\), which is a balanced \(3\)-ary design with parameters \((b', r', \lambda') = (15, 6, 1)\).
2. Iterating the process by fixing a second point \(y \in E \setminus \{x\}\) and selecting a sub-layer \(s'=1\) yields a design isomorphic to \(M(4,1)\), consisting of the \(4\) singletons on \(v-2\) points with \(\lambda'' = 0\).
This sequence \((126,84,21) \to (15,6,1) \to (4,4,0)\) demonstrates how the decomposition reduces both the ground set and the arity of the design step by step, eventually terminating at the trivial singleton set.
Each block \(B \in M(v,k)\) corresponds to its multiplicity vector \(c_B = (m_1(B), \dots, m_v(B)) \in \{0, 1, \dots, k\}^v\) with \(\sum\limits_i c_{B,i} = k\). Let \(C = \{c_B : B \in M(v,k)\}\).
We consider \(C\) under the Hamming metric with constant coordinate sum \(k\) (distinct from standard binary constant-weight codes). The \(A_q(n,d,w)\) notation denotes the maximum size of a code over alphabet size \(q\), length \(n\), minimum distance \(d\), and fixed weight \(w = \sum c_i\).
Theorem 4.1. The code \(C \subseteq \{0, 1, \dots, k\}^v\) has \(|C| = \binom{v+k-1}{k}\), minimum Hamming distance \(d_{\min}=2\) (attained), and is optimal: \(A_{k+1}(v,2,k) = \binom{v+k-1}{k}\).
Proof. \(|C| = \binom{v+k-1}{k}\) since \(M(v,k)\) enumerates all \(k\)-multisets exactly once.
For \(d_{\min}=2\): Let \(c \neq c' \in C\). Since \(\sum c_i = \sum c'_i = k\) but \(c \neq c'\), these vectors must differ in at least two coordinates (if they differed in exactly one, the sums would be unequal, a contradiction). Thus \(d_{\min} \ge 2\).
\(d_{\min}=2\) is attained: Consider \(c = (k, 0, \dots, 0)\) and \(c' = (k-1, 1, 0, \dots, 0)\). Then \(d_H(c, c') = 2\), yet both vectors maintain weight \(k\).
Optimality follows: \(C\) achieves size \(\binom{v+k-1}{k}\) with \(d=2\), so \(A_{k+1}(v,2,k) \ge \binom{v+k-1}{k}\). Because \(C\) includes all vectors in \(\{0, \dots, k\}^v\) of weight \(k\), any additional vector would either duplicate an entry or violate the weight constraint. Thus, \(A_{k+1}(v,2,k) = |C| = \binom{v+k-1}{k}\). ◻
Remark 4.2. This formulation differs from the non-binary constant-weight codes discussed by Braun [4] and Etzion [5], which often focus on restricted support or specific distance bounds. Here, the constant-sum constraint yields \(d_{\min}=2\) as a direct structural consequence.
Proposition 4.3(Layer decomposition of the code).Fix a coordinate \(x\). For each \(s\) with \(0 \le s \le k\), define \[C_x^{(s)} = \{\mathbf{c} \in C : c_x = s\}.\]
Then \[C = \bigsqcup_{s=0}^k C_x^{(s)},\] and the projection obtained by deleting coordinate \(x\) gives a bijection \[C_x^{(s)} \; \cong \; \{\mathbf{u} \in \{0, 1, \dots, k\}^{v-1} : \sum\limits_{i \ne x} u_i = k-s\}.\]
In particular, each layer \(C_x^{(s)}\) is itself a \((k+1)\)-ary constant-sum code of length \(v-1\) and size \(\binom{v+k-s-2}{k-s}\).
Proof. By definition, \(C_x^{(s)}\) consists of those multiplicity vectors whose \(x\)-th coordinate equals \(s\). Removing that coordinate yields a vector of length \(v-1\) whose coordinates sum to \(k-s\). Conversely, any such vector extends uniquely to an element of \(C\) by inserting the coordinate \(s\) at the \(x\)-th position. Thus the correspondence is bijective, and the size follows from the stars-and-bars formula for a reduced ground set. ◻
Thus the multiplicity-layer decomposition of \(M(v,k)\) corresponds naturally to a coordinate-layer decomposition of the associated code.
The complete multiset design \(M(v,k)\) occupies a fundamental position in the theory of designs with repeated elements. This paper serves as an expository synthesis that clarifies the combinatorial organization of \(M(v,k)\). By framing the design through its multiplicity-layer decomposition, we provide a unifying viewpoint that simplifies parameter derivation and highlights the natural symmetry between balanced \(n\)-ary designs and constant-weight codes.
The authors thank the anonymous referee for the thorough and constructive report, which substantially improved the mathematical precision, framing of contributions, and clarity of the manuscript.
Apurv Srivastav is a Ph.D. student at the University of Delaware, Newark, whose training is supported in part by the National Institutes of Health (NIH) under Award Number T32GM142603. The content is solely the responsibility of the authors and does not necessarily represent the official views of the NIH.