2
$\begingroup$

We are given set $\{1, \dots n\}$ and $A = \{A_1 \dots A_s\}$ such as $|A_i|=k$, $|A| = s = \binom n k$, namely $A$ contists of all possible subsets of size $k$.
We say that $S$ is a set of common representatives, if $\forall i \in 1\dots k :S\cap A_i \ne \emptyset$.

Task is to find amount of possible distinct representative sets $S$.
Example $A = \{\{1,4,5\}\{1,2,5\},\{1,2,3\},\{2,3,4\},\{3,4,5\}\}$
Here, $\tau(S) = 5$, since there are two possible set of representatives: $\{1,4\},\{1,3\},\{2,5\},\{3,5\},\{2,4\}$

Solution draft
I figured, that $|S| = n-k+1$ but probably I lack combinatorial experience to apply pigeonhole principle to my problem.
All formulations of it say that that exists at least one box, for which some measure applies, but here I must guarantee that measure applies for all of the boxes.
Yours help would be immensely appreciated.

$\endgroup$
6
  • $\begingroup$ You are on the right track. One part, probably the easy one, is to show that any smaller set $S$ is not "a set of common representatives. The other part is to show that if $S$ is at least as big as what you figured, then it is a set of common representatives as you've defined that. $\endgroup$
    – hardmath
    Commented Dec 20, 2014 at 18:43
  • $\begingroup$ @hardmath It's easy to show that: if we strip our $S$ for at least 1 element, than, since $s = \binom m k$, we would have one $A_x$ not covered by $S$. And our $S$ is big enough, because $S$ of size $n$ is definitely a set of common representatives, and we may decrease size till it reaches $|n-k+1|$. But you are missing my point. What I am asking is, how many $\underline{\text{different}}$ sets of representatives exists for our $A$. My original guess was $\binom n k \cdot k$ (like we choose one $A_i$ and then choose one element of $A_i$, which will stay in $S$, while others removed) $\endgroup$
    – Dmitri K
    Commented Dec 20, 2014 at 18:53
  • 1
    $\begingroup$ If you mean different sets $S$ that satisfy your definition, then the only tweak I'd make to your "solution draft" is to say $|S| \ge n-k+1$. Counting these is a sum of binomial coefficients. $\endgroup$
    – hardmath
    Commented Dec 20, 2014 at 18:58
  • $\begingroup$ @hardmath We are only interested in possible representative sets of minimal size. So $\ge$ is not needed. Would you be so kind to comment on my guess for $\tau(S)$ in my previous comment? I'm not sure that it's correct since it don't take into account possible duplicates. $\endgroup$
    – Dmitri K
    Commented Dec 20, 2014 at 19:01
  • 1
    $\begingroup$ @hardmath OOh. I guess I get what you are saying. $\tau(S) = \binom n {n-k+1}$ $\endgroup$
    – Dmitri K
    Commented Dec 20, 2014 at 19:08

1 Answer 1

1
$\begingroup$

If I understand correctly a set $S$ is of common representatives if every subset of $\{1,2\dots n\}$ that has $k$ elements has an element in common with $S$.

A set $S$ is of common representatives if and only if $S$ has $n-k+1$ elements or more. How many elements have $n-k+1$ subsets? $\sum\limits_{j=n-k+1}^n\binom{n}{j}$.

If you only want those of minimal size the answer is $\binom{n}{n-k+1}$

$\endgroup$
2
  • $\begingroup$ Yes, it's correct. We have posted answers almost simultaneously) We are only interested in minimal size $S$, so sum aren't required, but it was mentioned only in comments. Hence, I'm going to accept this. $\endgroup$
    – Dmitri K
    Commented Dec 20, 2014 at 19:10
  • $\begingroup$ Oh I see. thank you very much. $\endgroup$
    – Asinomás
    Commented Dec 20, 2014 at 19:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .