2
$\begingroup$

Question Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$?

The answer is: $\lambda {v-u\choose k}/{v-t\choose k-t}$.

How to find this answer?

I know that $b$ the number of blocks in the original design equals: $\lambda {v \choose t}/{k\choose t}$ and that for a $s\leq t$ the design is also a $s-(v,k,\lambda_s)$ design with $\lambda_s=\lambda {v-s\choose t-s}/{k-s\choose t-s}$.

I tried: first thing I tried was calculating $b-\lambda_u$ and rewriting it, but then I realized this gives the number of blocks that do not contain a given $u$-set, which is not the question (in the original question we want to subtract from $b$ the number of all the blocks that even contain one point of $U$.

So then I figured I could use the Principle of Inclusion/Exclusion, but it did not work either.

Looking at the expression it seems to me that some sort of Double Counting proof can be applied. ${v-u\choose k}$ counts the number of $k$-sets we can make in the set $X\setminus U$, which has $v-u$ points... But it's not the derived design, because then the blocks would be of size $k-u$.

Any hint/help is highly appreciated.

  • 0
    @Cindy: I've merged your old account into your new one.2012-06-22

1 Answers 1

1

Solved it. Inclusion exclusion would work I guess, but I prefer a double counting method. So here it goes: Let $b^u$ be the numer of blocks that have empty intersection with the set $U$.

Count pairs $(U,B)$ with $U$ a $u$-subset of $X$ en $B$ a block, with $U\cap B=\emptyset$. First way: ${v\choose u}$ options for $U$ each having $b^u$ blocks that have empty intersection with $U$. Second way: $b$ options for choosing a block and ${v-k\choose u}$ options for choosing a $U$ which does not intersect the block. Furthermore, $b$ equals $\lambda {v\choose t}/{k\choose t}$ and rewriting the above double counting identity will show the result.