# What is the number of subsets at size $k$ of the set $\{1,\ldots,n\}$ such that if a subsets contains $2$ it does not contain $1$?

What is the number of subsets at size $$k$$ of the set $$\{1,\ldots,n\}$$ such that if a subsets contains $$2$$ it does not contain $$1$$?

So think about that. We have $$n$$ numbers and $$k$$ subgroups. If $$2$$ contains so have groups on size $$(k-1)n +$$, but how to start with that.

Consider the set $$A=\{1,\ldots,n\}$$ .Count the number of subsets of $$A$$ of cardinality $$k$$. How many subsets of cardinality on size $$k$$ do contain the number $$2$$ and not $$1$$?

• In what sense do you mean 'subgroups' (probably not algebraically?) It would help if you defined more precisely what you are trying to count here. – Beckham Myers Aug 18 '19 at 21:52
• Is this a group (a set together with a binary operation that is associative, has a neutral element, and inverses), or do you mean set and subsets (which some people sometimes translate as “group” and “subgroups”)? – Arturo Magidin Aug 18 '19 at 22:26
• yes i mean that - set and subsets (which some people sometimes translate as “group” and “subgroups” . i need to count how much sub group i have on size k of the grop {1...n} – thebesthere Aug 18 '19 at 22:28
• @thebesthere. Mathematically the translation is a blunder. – William Elliot Aug 18 '19 at 22:50
• maybe now its clear .. thanks :) Consider the set A={1....n} .Count the number of subsets of A of cardinality k. How many subsets of cardinality on size k do contain the number 2 and not 1 – thebesthere Aug 18 '19 at 23:09

## 1 Answer

HINTS:

You need the number of subsets of size $$k$$ that do not contain both $$1$$ and $$2$$. This is the number of subsets of size $$k$$ minus the number of subsets of size $$k$$ that contain both $$1$$ and $$2$$. If a subset of size $$k$$ contains both $$1$$ and $$2$$, then it must contain $$k-2$$ elements other than $$1$$ and $$2$$.

Can you finish it now?

EDIT

The answer is $${n\choose k}-{n-2\choose k-2}$$

• SO the answer is ( n−2 k−1 ) – thebesthere Aug 19 '19 at 13:24
• @thebesthere Do you mean ${n-2\choose k-1}$? – saulspatz Aug 19 '19 at 13:27
• yes but why the answer is ( n k )−( n−2 k−2 ) if u can explain plz =] – thebesthere Aug 19 '19 at 14:31
• The first paragraph explains it. Which part do you have trouble understanding? By the way, you can format ${n\choose k}$ as ${n\choose k}$ – saulspatz Aug 19 '19 at 14:49
• It is not true that ${n \choose k} - {n-2 \choose k-2} = {n-2 \choose k-1}$. – Michael Lugo Aug 19 '19 at 15:04