I do have n items and would like to get the number of all possible combinations whereby the order can be ignored and repetitions are not allowed.
For example, for n = 3 I expect
x1,
x2,
x3,
x1, x2
x1, x3
x2, x3
x1, x2, x3
so the number should be 7.
I can calculate this number, I think, by summing up the binomial coefficients:
$$\sum_{k=1}^{n} \binom{n}{k}$$.
I can calculate this in Python as follows
from scipy.special import binom
n = 3
sum(binom(n, k) for k in range(n))
which indeed returns 7.
What I am wondering is whether there is an analytical equation for this. The closest I could find is
$$\binom{n + r – 1}{r} = \frac{(n+r-1)!}{r!(n-1)!}$$,
but that allows for repetition.
Best Answer
Judging by your example, what you wish to calculate is the number of all nonempty subsets of a set.
Each subset is determined by choosing whether or not to include a particular element. For instance, if our set is $S = \{1, 2, 3, 4, 5\}$, if we choose to include $1$, not include $2$, not include $3$, include $4$, and not include $5$, we obtain the subset $\{1, 4\}$. For a set with $n$ elements, there are two choices for each element, giving $2^n$ subsets, of which one is the empty set, so there are $2^n - 1$ nonempty subsets of a set with $n$ elements.
The number of subsets with exactly $k$ elements is $\binom{n}{k}$. Hence, the number of nonempty subsets of a set with $n$ elements is $$\sum_{k = 1}^{n} \binom{n}{k} = \sum_{k = 0}^{n} \binom{n}{k} - \binom{n}{0} = \sum_{k = 0}^{n} \binom{n}{k} - 1$$
The Binomial Theorem states that $$(x + y)^n = \sum_{k = 0}^{n} \binom{n}{k}x^{n - k}y^k$$ If we substitute $1$ for both $x$ and $y$, we obtain $$2^n = (1 + 1)^n = \sum_{k = 0}^{n} \binom{n}{k}1^{n - k}1^k = \sum_{k = 0}^{n} \binom{n}{k}$$ Hence, $$\sum_{k = 1}^{n} \binom{n}{k} = \sum_{k = 0}^{n} \binom{n}{k} - 1 = 2^n - 1$$