Let $S$ be the set of subsets of size $k$ from $\{1,\dots,n\}$.

Let $a$ be an element of $S$.

Determine the number of other elements of $S$ that have an intersection of size $l$ with $a$.

I have worked through this and found that it is (I think): $k \choose l$$(n-k)$. Because there are $k \choose l$ choices of numbers to change and $(n-k)$ choices for each.

I also questioning my answer now because if there are $(n-k)$ choices of numbers to change each number to, some may get changed to the same number which is not allowed as the set can't have repeats.

  • $\begingroup$ HINT: Every such set $X$ is the disjoint union $$(X \cap a) \cup (X \setminus a)$$ hence you have to choose $l$ elements of $a$ to form the first and $k-l$ from $a^c$ to form the second. $\endgroup$ – Crostul Jun 20 '17 at 17:31
  • $\begingroup$ I've made significant changes to my answer since you accepted it. I hope the explanation is even clearer now. $\endgroup$ – Trevor Gunn Jun 20 '17 at 17:56

You choose $l$ elements from $a$ and $k - l$ elements from outside of $a$. Therefore the answer is

$$ {k \choose l}{n - k \choose k - l}. $$

If you do it your way it should be

$$ (n - k)^{k \choose l} $$

i.e. the product, not the sum. You are making the choices simultaneously. But this formula is still wrong for several reasons:

  1. You are not replacing ${k \choose l}$ elements you are replacing $k - l$ elements so that should have been $(n - k)^{k - l}$ what you are doing with ${k \choose l}$ is choosing a distinguished set of $l$ elements (equiv. a distinguished set of $k - l$ elements). Thus you now have ${k \choose l}(n - k)^{k - l}$
  2. You are doing nothing to ensure that you do not replace two or more elements by the same element. It should not be $n - k$ choices for every one of the $k - l$ vertices, it should be $n - k$ for the first, $n - k - 1$ for the second, etc. This gives ${k \choose l}(n - k)^{\underline{l - k}}$ where the underline denotes the falling product: $$x^{\underline{n}} = x(x - 1)(x - 2)\cdots(x - (n - 1))$$
  3. Now you have to account for the order in which you make the replacements: it doesn't matter. Thus you finally have $${k \choose l}\frac{(n - k)^{\underline{l - k}}}{(l - k)!} = {k \choose l}{n - k \choose l - k}.$$

Fix $A\subseteq \{1,\ldots,n\}$ with $\#A=k$. Fix a subset $B\subseteq A$ with $\#B=\ell$ (this can be done in $\binom{k}{\ell}$ ways). Then you need to find all subsets of $C\subseteq \{1,\ldots,n\}\setminus A$ with $\#C=k-\ell$ (this can be done in $\binom{n-k}{k-\ell}$ ways). Considering that the collection of all $B\cup C$ are the wanted sets, the answer is $$ \binom{k}{\ell}\binom{n-k}{k-\ell}. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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