Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
You might want to edit in a link to your posting of this question at MathOverflow, so people here could benefit from the comments there. –  Gerry Myerson Jun 21 '12 at 23:56
    
@Cindy: I've merged your old account into your new one. –  Willie Wong Jun 22 '12 at 13:19
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.