1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The other element of the two-element set must be something other than $2$. How many numbers other than $2$ belong to this set? $\endgroup$ – Michael Hardy Mar 20 '13 at 3:03
  • $\begingroup$ would it be $n-1$? so the number would be $\binom{n}{n-1}$? $\endgroup$ – user60334 Mar 20 '13 at 3:22
  • 1
    $\begingroup$ 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$. $\endgroup$ – Michael Hardy Mar 20 '13 at 3:35
  • 1
    $\begingroup$ They're the same set, since they have the same members. Sets are not ordered. $\endgroup$ – Michael Hardy Mar 20 '13 at 3:55
  • 1
    $\begingroup$ Hint for b: $\sum_{k=1}^{n}\binom{n-1}{k-1}=\sum_{k=0}^{n-1}\binom{n-1}{k}=2^{n-1}$. $\endgroup$ – Julien Mar 20 '13 at 4:28
2
$\begingroup$

HINTS:

(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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.