Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
add comment

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.