How many selections will contain the element?

Given a set of $n$-elements, how many subsets of $m$ size selected from this set will contain a certain element in the original set.

For example, how many subsets will contain the number $1$ when selecting $2$-elements from the following set:

$1,2,3,4$,

and then from the following set:

$1, 2, 1, 1, 4$.

-
Khaled, for your specific examples, is it not easier to find out how many subsets will NOT contain the number 1 (and subtract from total number of possible subsets if necessary)? Just a thought. – Conan Wong Jan 25 '13 at 17:12
Are the $1$'s distinguishable in the second case? For instance, how many one-element subsets are there -- three, or five? – mjqxxxx Jan 25 '13 at 17:39

The first case is quite simple. You have the set $A = \{1, 2, 3, 4\}$ and the set $B = \{2, 3, 4\}$. Now, every subset of size $m$ of $A$ which contains $1$ can be formed by joining a generic subset of $B$ of size $m-1$ with the set $\{1\}$.

In other word, let $n=4$ and $m=2$ (as you propose), then $\frac{(n-1)!}{(m-1)!(n-1-m+1)!} = \frac{3!}{1!2!} = 3$ is the number of the subset of size $1$ of $B$ and then this is the number of subset of $A$ of size $2$ which contains $1$.

I guess the second case can be solved with similar arguments. Just to give an idea...

Let $A$ be a set (without repeated elements). For example $A = \{1, 2, 4\}$.
Suppose that each element of $A$ has a multiplicity, say $\mu(x)$ where $x$ is an element of $A$ . In the example, $\mu(1) = 3$, $\mu(2) = \mu(4) = 1$. Suppose also that you remove an element $x$ from the set $A$ and you obtain the set $B = A \setminus \{x\}$. Let $n_A = \mu(x)$ and $n_B = \sum_{y \neq x} \mu(y)$. Clearly $n_A+n_B= n$.

When you have to form a group of $m$ element extracted from $A$ (with repeated elements) then you can say that:

• I extract $m$ elements from collection $B$ (if $m \leq n_B$)
• I extract $m-1$ elements from collection $B$ and $1$ from collection $\{x\}$ (if $m-1 \leq n_B$ and $1 \leq n_A$)
• I extract $m-2$ elements from collection $B$ and $2$ from collection $\{x\}$ (if $m-2 \leq n_B$ and $2 \leq n_A$)
• and so on...

and so on

Each case can be easily computed using binomial coefficients so the solution is straight forward!

NOTE I use collection to distinguish from set. A set has unique elements, a collection can have repeated elements. In my answer I use a set or a collection depending from the context.

$A$ as set: $A = \{1, 2, 4\}$

$A$ as collection: $A = \{1, 2, 1, 1, 4\}$

$B$ as set: $B = \{2, 4\}$

$B$ as collection: $B = \{2, 4\}$

$\{x\}$ as set: $\{x\} = \{1\}$

$\{x\}$ as collection: $\{x\} = \{1, 1, 1\}$

-