MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.

@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 – 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

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

share|cite|improve this answer

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