The Block 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.

On The Replication Number of a Balanced Incomplete Block Design page we defined the replication number $r$ of a $(v, k, \lambda)$-BIBD to be the number of blocks containing an arbitrary point $x$. We proved that this number is well-defined and given by the formula:

(1)

\begin{align} \quad r = \frac{\lambda (v - 1)}{k - 1} \end{align}

We now introduce another important number of a $(v, k, \lambda)$-BIBD with the following theorem.

Theorem 1: Let $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD. Then $\mathcal A$ contains exactly $\displaystyle{b = \frac{\lambda ( v^2 - v)}{k^2 - k}}$ blocks.

• Proof: Let $b$ denote the number of blocks in $\mathcal A$, i.e., $\mid \mathcal A \mid = b$.

• Let $x \in X$. Since $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD we have by definition. that $\mid X \mid = v$ so there are $v$ many points $x$ to choose from. Furthermore, every point $x$ is contained in $r$ blocks (where $r$ is the replication number of this BIBD). So $vr$ is the number of points multiplied by the number of blocks containing each point.

• Similarly, there are $b$ blocks and since each block contains $k$ points, $bk$ is the number of points multiplied by the number of blocks containing each point.

• Hence $vr = bk$, i.e., $\displaystyle{b = \frac{vr}{k}}$. We know that $\displaystyle{r = \frac{\lambda ( v - 1)}{k - 1}}$ and hence:

(2)

\begin{align} \quad b = \frac{vr}{k} = \frac{\lambda v(v - 1)}{k(k - 1)} = \frac{\lambda (v^2 - v)}{k^2 - k} \end{align}

• So $\mathcal A$ contains exactly $\displaystyle{b = \frac{\lambda (v^2 - v)}{k^2 - k}}$ blocks. $\blacksquare$

Definition: If $(X, \mathcal A)$ is a $(v, k, \lambda)$-BIBD then the Block Number of this BIBD is $\displaystyle{b = \frac{\lambda (v^2 - v)}{k^2 - k}}$ and denotes the size of $\mathcal A$ (the number of blocks in in $\mathcal A$).

We recall once again the $(5, 3, 3)$-BIBD with $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 \} \}$. We see that $\mathcal A$ contains $10$ blocks so $b = \mid \mathcal A \mid = 10$. Furthermore, $v = 5$, $k = 3$, $\lambda = 3$, and:

(3)

\begin{align} \quad b = \frac{\lambda (v^2 - v)}{k^2 - k} = \frac{3(5^2 - 5)}{3^2 - 3} = \frac{3(20)}{6} = \frac{60}{6} = 10 \end{align}

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 block number of the $\displaystyle{ \left ( v, k, \binom{v - 2}{k-2} \right )}$-BIBD $(X, \mathcal A)$ is:

(4)

\begin{align} \quad b = \frac{\lambda (v^2 - v)}{k^2 - k} = \frac{\binom{v - 2}{k - 2} v(v - 1)}{k(k-1)} = \frac{\frac{(v - 2)!}{(v - k)! (k - 2)!} v(v-1)}{k(k-1)} = \frac{v!}{(v - k)! k!} = \binom{v}{k} \end{align}

This is what should be expected because we know that $\displaystyle{\binom{v}{k}}$ is the number of all $k$-element subsets of a $v$-element set.