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.

counting the number of ordered subsets in a n-set is easy, it's $ 2 ^n -1 $ (assuming we don"t want the empty subset, it's the sum of $ n \choose i $ , i>0

now imagine I have a set s=(a, b, x), where x can have 2 possible values x1, x2

the result wanted:

(a), (b), (x1), (x2), (a,b), (a,x1), (a,x2), (b,x1), (b,x2), (a,b,x1), (a,b,x2)

I would like to generalize with s of length n, and x having k possible values

=> Counting the subsets of $ (a_1, a_2, a_3, ...,a_{n-1}, \begin{matrix} x_1\\ x_2 \\ \vdots\\ x_k \end{matrix} ) $

share|improve this question

3 Answers 3

up vote 1 down vote accepted

We include the empty set. You can remove it if you wish: I don't want to be accused of anti-emptyism.

My understanding is that you have a set $A$ of $n-1$ elements, and another (disjoint) set $X$ of $k$ elements. We want to count the subsets of $A\cup X$ that have have no more than one object from $X$. Take any subset of $A$ (there are $2^{n-1}$ of these) and append a single object from $X$, or nothing ($k+1$ choices). That gives $(k+1)2^{n-1}$ possibilities.

share|improve this answer
    
ok and seems to work for the example, thx –  kwak Jun 27 '12 at 18:59
    
@ca11111: The formula in the comment above counts *all the non-empty subsets of $A\cup X$. That is definitely not what your post says you want to count. –  André Nicolas Jun 27 '12 at 19:11
    
yes i know, it's a data indexation problem, and the solution in the post scales better than putting all elts inline –  kwak Jun 29 '12 at 13:04

suppose our subset contains $i$ elements. Case 1,an element of x is in subset,then number of possibilities = $ {n-1 \choose{i-1}}{k \choose 1}$.Case2,element of x is not in subset,then number of possibilities= $ {n-1 \choose {i}}$.Thus total number of subsets = $\sum_1^{n}{n-1 \choose{i-1}}{k \choose 1}+\sum_0^{n-1}{n-1 \choose {i}}$ giving total of $(k+1)(2^{n-1})$ subsets.

share|improve this answer

You are basically asking to choose a subset of $\{ a_1, \dots, a_{n-1} \}$ and up to one element of $\{ x_1, \dots, x_k \}$, which we can think of as picking exactly one element of $\{ x_0, x_1, \dots, x_k \}$. (If we pick $x_0$, then we add nothing to the subset of $\{a_1, \dots, a_{n-1} \}$ chosen.) Since there are $2^{n-1}$ subsets of $\{a_1, \dots, a_{n-1} \}$ and $k+1$ choices for the element $x_i$, there are in total $2^{n-1} \cdot (k+1)$ such subsets. Or $2^{n-1} \cdot (k+1) - 1$ if you want to exclude the empty set (but that's probably a silly thing to do unless you have a good reason to do so).

share|improve this answer

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.