how many subsets of size k from {1,2,...n} such that if subset contains 2 it doesn't contain 1

Question

How many subsets are there of size k from the set {1,2,...n} such that if a subset contains 2 it doesn't contain 1?

My answer:

The total number of possible subsets of size k is just $|\Omega| ={n \choose k}$. Let $A_k$ be subset of size $k$ and divide by cases:

• i) subset contains both 1 and 2
• ii) subset containers neither 1 nor 2
• iii) subset contains 1 but not 2, or 2 but not 1 (same amount for both cases)

In other words, $$ |\Omega| = |1,2\in A_k| + |1,2\notin A_k| +2 |1\in A_k,2\notin A_k| $$.

For case i), we know that $1,2\in A_k$, so we count how many subsets of size $k-2$ there are from set $\{3,4,...n\}$, which is ${n-2} \choose {k-2}$. For case ii), we have to choose $k$ elements from $\{3,4,....n\}$, which gives $n-2 \choose k$ options. Thus, my answer would be

$$\dfrac{1}{2} ({n \choose k} - {n-2 \choose k} - {n-2\choose k-2})$$

The actual solution isn't given, so I don't know if my answer is correct or not. Any help?

Answer 1

It seems you've given the number of subsets $A$ of $\{1,\dots,n\}$ such that:

• $|A|=k,$
• $1\notin A,$ and
• $2\in A.$

However, this is not what you're asked to find. To have "$2\in A\implies 1\notin A$" be true, we need one or both of the following to be true:

• $1\notin A.$
• $2\notin A.$

Fortunately, it's an easy fix. You've already found the number of ways that both can hold (case 2), as well as the number of ways that exactly one can hold (case 3). Thus, we must add $\binom{n-2}k$ to twice your answer, yielding $$\binom nk-\binom{n-2}{k-2}.$$

More simply, we could do it this way. The following statements are equivalent:

• One or both of "$1\notin A$," "$2\notin A$" is true.
• "$\{1,2\}\subseteq A$" is false.

Thus, it's more straightforward to simply subtract your case 1 possibilities from the total number of possibilities, which of course yields the same result.

Answer 2

"does not contain $1$ if it contains $2$" is the same as "does not contain $1$ or does not contain $2$".

For $i=1,2$ let $\mathcal S_i$ denote the subcollection of subsets of $\{1,\dots,n\}$ having size $k$ and such that $i\notin S$ for every $S\in\mathcal S_i$.

So actually $\mathcal S_i:=\{S\in\wp(\{1,\dots,n\})\mid i\notin S\wedge|S|=k\}$

Then with inclusion/exclusion and symmetry we find:$$|\mathcal S_1\cup \mathcal S_2|=|\mathcal S_1|+|\mathcal S_2|-|\mathcal S_1\cap \mathcal S_2|=2|\mathcal S_1|-|\mathcal S_1\cap \mathcal S_2|=2\binom{n-1}{k}-\binom{n-2}k$$

This under the convention that $\binom{m}k=0$ if $k>m$.

Answer 3

$ \binom{n-2}{k-1} + \binom{n-2}{k-1} + \binom{n-2}{k} $ up to isomorphism.

Let $F(A,X) =_{def} A \cdot F'(X)$ be a species of sort X and a constant A.

Then the species in the problem is:

$E_kE_m(A,B,X) =A.B. (E_kE_m)''(X) = \cdots =$

$E_k(A,B,X).E_m(X) + E_k( A,X).E_m( B,X) + E_k( B,X).E_m( A,X) + E_k(X).E_m(A,B,X)$

The coefficient of $ab\frac{x^{n-2}}{(n-2)!} $ of the sum of the last three terms is the required number.

$ Answer = \binom{n-2}{k-1} + \binom{n-2}{k-1} + \binom{n-2}{k} $

Why there are terms like $\binom nk$ and $\binom{n-1}k$ i.e containing $n!$ and $(n-1)!$ in the previous answers ? This is because the coefficient of $\frac{x^{n-2}}{(n-2)!} $ in the e.g.f. of F" is the same with coefficient of $ \frac{x^{n-1}}{(n-1)!} $ for F' and with coefficient of $\frac{x^n}{n!} $ for F (even we do not have species isomorphisms).