combinatorics counting sets with a one element having values in another set

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

-

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.

-
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

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

-

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.

-