The Replication Number of a Balanced Incomplete Block Design
Recall from the Balanced Incomplete Block Designs page that if $v$, $k$, and $\lambda$ are positive integers such that $2 \leq k < v$ and $X$ is a finite set (whose elements are called points) then a $(v, k, \lambda)$-BIBD on $X$ is a pair $(X, \mathcal A)$ where $\mathcal A$ is a multiset of nonempty subsets of $X$ (called blocks) for which:
- 1. $\mid X \mid = v$.
- 2. Every block contains exactly $k$ points, that is, for all $A \in \mathcal A$ we have that $\mid A \mid = k$.
- 3. Every pair of distinct points is contained in exactly $\lambda$ blocks, that is, for all $x, y \in X$ with $x \neq y$ there exists blocks $A_1, A_2, ..., A_{\lambda} \in A$ for which $x \in A_1, A_2, ..., A_{\lambda}$ and $y \in A_1, A_2, ..., A_{\lambda}$.
We proved a nice result which said that if $v$ and $k$ are positive integers with $2 \leq k < v$ and $X$ is a finite set with $v$ elements then if $\mathcal A$ is the set of all $k$-element subsets of $X$ then $(X, \mathcal A)$ is a $\displaystyle{\left ( v, k, \binom{v-2}{k-2} \right )}$-BIBD.
We are about to define an important term regarding BIBDs but we will first need to prove the following theorem.
| Theorem 1: Let $(X, \mathcal A)$ be a $(v, k, \lambda)$-BIBD. Then every point $x \in X$ is contained in exactly $\displaystyle{r = \frac{\lambda (v - 1)}{k - 1}}$ blocks. |
- Proof: Let $x \in X$ and let $r_x$ denote the number of blocks in $\mathcal A$ containing $x$.
- Let $y \in X$ be such that $x \neq y$. Then there are $v - 1$ of such $y$ to choose from. Since $(X, \lambda)$ is a $(v, k, \lambda)$-BIBD this means that every pair of distinct points is contained in exactly $\lambda$ blocks. So, for a fixed $x \in X$, there are $\lambda ( v - 1)$ occurrences of pairs of the form $\{ x, y \}$.
- Furthermore, for a fixed $x \in X$, there are $r_x$ blocks containing $x$ and for each of these blocks there are $k - 1$ choices for $y \neq x$, so there are $r_x (k - 1)$ occurences of pairs of the form $\{ x, y \}$.
- So for each fixed $x \in X$, $r_x ( k - 1) = \lambda ( v - 1)$, i.e., $\displaystyle{r_x = \frac{\lambda ( v - 1)}{k- 1}}$, that is, any point $x \in X$ appears in exactly $\displaystyle{r = \frac{\lambda (v - 1)}{k - 1}}$ blocks. $\blacksquare$
With theorem 1 above we known that if $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD then every point in $X$ occurs in exactly $r$ blocks. The number $r$ is important and given a special name.
| Definition: If $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD then the Replication Number of this BIBD is $\displaystyle{r = \frac{\lambda ( v - 1)}{k - 1}}$ and denotes the number of blocks containing any arbitrary point $x \in X$. |
Recall that if $X = \{ 1, 2, 3, 4, 5 \}$ and $\mathcal A = \{ \{ 1, 2, 3 \}, \{ 1, 2, 4 \}, \{1, 2, 5 \}, \{1, 3, 4\}, \{1, 3, 5\}, \{1, 4, 5 \}, \{2, 3, 4 \}, \{2, 3, 5 \}, \{2, 4, 5 \}, \{3, 4, 5 \} \}$ then $(X, \mathcal A)$ is a $(5, 3, 3)$-BIBD. So $v = 5$, $k = 3$, and $\lambda = 3$. Notice that every point in $X$ occurs in $6$ blocks and:
(1)In other words, the replication number of the $(5, 3, 3)$-BIBD above is $r = 6$.
In general, if $X$ is a finite set containing $v$ elements and $\mathcal A$ is the collection of all $k$-element subsets of $X$ then we know that $\displaystyle{\lambda = \binom{v - 2}{k - 2}}$, so the replication number of the $\displaystyle{\left ( v, k, \binom{v - 2}{k - 2} \right )}$-BIBD $(X, \mathcal A)$ is:
(2)