How many ways are there to select elements from a set, without replacement?

Question

Most of the examples I see are that of permutations. This query is whether there is a formal formula for a more exhaustive ordering:

Eg:
The set $\{1\}$ is ordered as $\{1\}$. Just one possibility.
The set $\{1,2\}$ can only be ordered as: $\{1\},\{2\},\{1,2\},\{2,1\}$. Four possibilities.
The set $\{1,2,3\}$ can be ordered as:
$\{1\},\{2\},\{3\},\{1,2\},\{2,1\},\{1,3\},\{3,1\},\{2,3\},\{3,2\},\{1,2,3\},\{1,3,2\},\{2,1,3\},\{2,3,1\},\{3,1,2\},\{3,2,1\}$. Fifteen possibilities.

Since the sequence is 1,4 and 15, I'm not sure what formula would apply.

I'm developing a program that randomly generates a few numbers from this set, but to know the total possibilities, I was hoping for a formula which could predict it.

Answer 1

Did you want to count the empty set $\{\}$ as well? If yes, then just start the index $i$ at $0$ instead of $1$ in the below summation.

So far, you're doing $$ \sum_{i=1}^{n} {}^n\text{P}_{i} $$ for each natural number $n \in \mathbb{N}$, where ${}^n\text{P}_{i}$ is the permutation formula given by $$ {}^n\text{P}_{i} = \frac{n!}{(n-i)!}. $$ For example, to get $15$ you're doing $$ \frac{3!}{(3-1)!} + \frac{3!}{(3-2)!} + \frac{3!}{(3-3)!} = \frac{3!}{2!} + \frac{3!}{1!} + \frac{3!}{0!} = 3 + 6 + 6 = 15. $$ I will leave it to you to see how each term corresponds to each set type, and hopefully you can understand where this formula comes from. If not, I'd be happy to elaborate later.

Answer 2

Let $f(n)$ be the number of possible words of any length over the alphabet $\{1,\dotsb, n\}$ where each letter appears at most once(including the empty word). Then $$ f(n)=\sum_{i=0}^n\frac{n!}{(n-i)!}=n!\sum_{i=0}^n\frac{1}{i!} $$ Note that $$ \begin{align} 0\leq en!-f(n)&=n!\left(\frac{1}{(n+1)!}+\frac{1}{(n+2)!}+\frac{1}{(n+3)!}\dotsb\right)\\ &=\frac{1}{(n+1)}+\frac{1}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}+\dotsb\\ &<\frac{1}{(n+1)}+\frac{1}{(n+1)^2}+\frac{1}{(n+1)^3}+\dotsb\\ &=1/n\leq1 \end{align} $$ So $f(n)=\lfloor{en!}\rfloor$. If you want to exclude the empty word subtract one.

Answer 3

As Bill Wallis posted, you are currently taking the sum

$$\sum_{r=1}^{n}\frac{n!}{(n-r)!}\, ,$$

or

$$\sum_{r=0}^{n}\frac{n!}{(n-r)!}$$

if we include the empty selection.

Another way to write this is

$$\sum_{r=0}^{n}\frac{n!}{r!}\, .\tag{1}$$

If we now remember the expansion for $e^x$:

$$e^x=\sum_{r\ge 0}\frac{1}{r!}x^r\tag{2}$$

then the sum $(1)$ is approximated by putting $x=1$ in $(2)$ and multiplying by $n!$:

$$n!e=\sum_{r\ge 0}\frac{n!}{r!}\, .\tag{3}$$

Now, all that remains is to show is that the difference between $(3)$ and $(1)$ is less than $1$ (hint: perform a term by term comparison with a geometric series) and we have

$$\lfloor n!e\rfloor = \sum_{r=0}^{n}\frac{n!}{(n-r)!}\, .$$

Or, if you exclude the empty selection

$$\lfloor n!e\rfloor - 1 = \sum_{r=1}^{n}\frac{n!}{(n-r)!}\, .$$

The only reference I have for a push-button lock sequence is page 82 of An Introduction to Enumeration by Alan Camina and Barry Lewis. Unfortunately there are pages missing in the sample.