Suppose I have a set $S=\{1..n\}$.

The number of ways of selecting half of the elements from $S$ is ${n \choose n/2}$.

My question is how to count the number of ways of selecting a different set on the second trial given the set from the first trial (with replacement).

I.e. draw a set $A$ of cardinality $n/2$ from $S$, and replace them. Draw another set $B$ of cardinality $n/2$ from $S$. How many possibilities are there for $B$ such that $A \ne B$?

I've thought of ${n \choose n/2}-1$ but that doesn't seem correct. I've also thought of ${n-1 \choose n/2}$ but that is counting something different also.


Your first thought is fine. As you say, there are ${n \choose n/2}$ subsets and you have excluded one of them.


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.