# finding 2-element subsets of $S_n$ which contain 2?

For any positive integer $n$ let: $$S_n = \{1,2,\ldots,n\}$$ (a) for any integer $n \ge 2$, find the number of 2-element subsets of $S_n$ which contain 2.

(b) for any integer $n \ge 2$, find the number of subsets $A$ of $S_n$ with the property that $N(A) \in A$ where $N(A)$ is the cardinality of the set $A$. Answer must be in the form $2^N$ where $N$ is a simple expression involving $n$.

any help is appreciated.

• The other element of the two-element set must be something other than $2$. How many numbers other than $2$ belong to this set? – Michael Hardy Mar 20 '13 at 3:03
• would it be $n-1$? so the number would be $\binom{n}{n-1}$? – user60334 Mar 20 '13 at 3:22
• You're still making it too complicated. Consider $\{1,2,3,4\}$. The $2$-element subsets containing the number $2$ are these: $\{1,2\}$, $\{3,2\}$, $\{4,2\}$. Do something similar when $n\ne4$. – Michael Hardy Mar 20 '13 at 3:35
• They're the same set, since they have the same members. Sets are not ordered. – Michael Hardy Mar 20 '13 at 3:55
• Hint for b: $\sum_{k=1}^{n}\binom{n-1}{k-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}=2^{n-1}$. – Julien Mar 20 '13 at 4:28

(a) Picking a $2$-element subset of $S_n$ that contains $2$ is the same as picking a single element from $S_n\setminus\{2\}$.
(b) Let $f(n)$ be the number of subsets of $S_n$ with the property in question. There is $1$ $1$-element subset containing $1$. The answer to (a) is the number of $2$-element subsets containing $2$. Generalize (a) to find a simple expression for the number of $k$-element subsets containing $k$, for $k=3,\dots,n$. For instance, picking a $3$-element subset containing $3$ is the same as picking a $2$-element subset of $S_n\setminus\{3\}$. Now add those partial results and simplify; you’ll need only some basic facts about binomial coefficients.
Here's another way, choose $2$ in the beginning. Now you have to choose one more element from the set $(1,3,4,5,6..n)$.
That is you can choose one element from the set in $n-1 \choose 1$=$n-1$
Therefore, there are $n-1$ subsets which has two elements with $2$ has one of its elements in total.