-1
$\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 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.

$\endgroup$
4
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 21, 2012 at 22:08
  • $\begingroup$ 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. $\endgroup$ Jun 21, 2012 at 22:58
  • $\begingroup$ 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? $\endgroup$
    – Cindy
    Jun 21, 2012 at 23:48
  • $\begingroup$ Oh and I apologize for mixing up the two sites. $\endgroup$
    – Cindy
    Jun 21, 2012 at 23:57

1 Answer 1

2
$\begingroup$

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

$\endgroup$

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