Analytical formula for all combinations of n items without repetition where order is not important

Question

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.

Answer 1

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