Calculating number of times a given element appears in powerset subsets of a particular size.

955 Views Asked by At

Let $X$ be a finite set, and $P(X)$ the power set of $X$. I understand from here how to calculate the number of subsets of a particular size in $P(X)$. For a given member of $X$ (call it $n$) how can I calculate the number of times $n$ appears in a set of subsets of a given size?

For example, suppose $X = \{1, 2, 3\}$ and $n = 2$. Then the subsets of $P(X)$ with two members are $\{1, 2\}, \{1, 3\}$ and $\{2, 3\}$. $n$ is in two thirds of these. But is there a more general way for determining the number of times $n$ appears in a subset of $P(X)$ containing only sets of identical size?

2

There are 2 best solutions below

1
On

HINT- Let the size of the desired subsets be $k$ and the total size of the set $N$. So you want the number of $k$-subsets of the set which have a particular element $n$. Now let's assume element $n$ is present in a subset. That leaves $k-1$ elements inside the subset that have to be filled from the remaining $N-1$. The number of ways to select $k-1$ elements from a group of $N-1$ is ....

EDIT- Since the OP insisted, I'm giving out the answer

$$\binom{N-1}{k-1}$$

2
On

Suppose $X$ has $N$ elements. The probability that a particular element (you call it $n$) is in a randomly chosen subset of size $k$ is just $k/N$.

So if there are $M$ subsets of size $k$ the number of them that contain $n$ is $(k/N)M$.

Since you say you know how to calculate $M$ you're done.