# In all the subsets of length greater than k, Find how many times an element comes in all the subsets?

Is there a formula or can it be derived for this Problem?

Given a set, First find all the subsets of length $\geq k$ , such that $k<length$ of set.

Then calculate how many time an element comes in all the subsets.

For e.g.

Consider a Set : $\{1,2,3,4\}$ and $k=3$

Possible subsets are : $\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,2,3,4\}$

Number of times each element comes is 4.

For $k=2$ for same set as above. Number of times each element comes is 7.

• I think you mean "k<length of set" – AnalysisStudent0414 May 5 '14 at 12:37
• So, you want to find out how many subsets of a set $A$ of length greater than equal to $k$ contain a particular element (the choice of element doesn't affect the number.) Well, the combinatorics here, is that you fix an element $x$, and then all you need is to compute the number of subsets of the set $A \backslash\{x\}$ that are of length greater than equal to $k-1.$ – Siddharth Venkatesh May 5 '14 at 12:42
• @AnalysisStudent0414 Yes , by mistake i wrote subset sorry. – Arvind May 5 '14 at 12:44
• Number of subsets of size $r$ containing any given element equals number of subsets of size $r-1$ not containing that element. – Gerry Myerson May 5 '14 at 12:57

The number of subsets of size $k$ containing some particular element say $1$ is $\binom{n-1}{k-1}$. Hence, the required sum is $$\sum_{i=k}^{n}\binom{n-1}{i-1}$$