0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you mean "k<length of set" $\endgroup$ – AnalysisStudent0414 May 5 '14 at 12:37
  • $\begingroup$ 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.$ $\endgroup$ – Siddharth Venkatesh May 5 '14 at 12:42
  • 1
    $\begingroup$ @AnalysisStudent0414 Yes , by mistake i wrote subset sorry. $\endgroup$ – Arvind May 5 '14 at 12:44
  • $\begingroup$ Number of subsets of size $r$ containing any given element equals number of subsets of size $r-1$ not containing that element. $\endgroup$ – Gerry Myerson May 5 '14 at 12:57
0
$\begingroup$

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}$$

$\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.