Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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 substract 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\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

closed as off-topic by Douglas Zare, Carlo Beenakker, Chris Godsil, Daniel Moskovich, Andrey Rekalo Jul 22 '13 at 13:38

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Douglas Zare, Carlo Beenakker, Chris Godsil, Daniel Moskovich, Andrey Rekalo
If this question can be reworded to fit the rules in the help center, please edit the question.

1  
@Cindy: Is your $x$ meant to be a $t$, i.e., is $u≤t$? If not the result is false. If it is then it can be proved by inclusion-exclusion, and this would not be an unreasonable exercise for a design theory course. –  Chris Godsil Jun 21 '12 at 22:08
    
This website is for questions with a research interest. This question is presented more as an exercise, so I think a better place for it is math.stackexchange.com. –  Gerry Myerson Jun 21 '12 at 22:58
    
Chris you are right, it had to be a t. Using Incl. Excl. I get a summation which will not reduce tto the given answer? –  Cindy Jun 21 '12 at 23:48
    
Oh and I apologize for mixing up the two sites. –  Cindy Jun 21 '12 at 23:57

1 Answer 1

See "Combinatorics of Symmetric Designs" by Y.J. Ionin and M.S. Shrikhande, Cambridge University Press, 2006, Theorem 6.1.17.

share|improve this answer

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