8
$\begingroup$

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.

$\endgroup$
  • 11
    $\begingroup$ In what sense is $\{1\}$ an "ordering" of the set $\{1,2\}$? $\endgroup$ – David C. Ullrich May 24 '18 at 15:38
  • 9
    $\begingroup$ You are talking about counting all permutations taken from a set without replacement. There is a simple formula for this: $\lfloor n!e\rfloor$ (subtract 1 if you don't want to include the empty selection). Sometimes this is known as the push-button lock sequence problem. $\endgroup$ – N. Shales May 24 '18 at 15:38
  • 2
    $\begingroup$ @N.Shales I think you should post this as an answer, with a link. $\endgroup$ – Ethan Bolker May 24 '18 at 15:43
  • 3
    $\begingroup$ This sequence is on OEIS: oeis.org/A007526 $\endgroup$ – G Tony Jacobs May 24 '18 at 15:53
  • $\begingroup$ I tried earlier to write a title that would be more helpful to someone else searching for a solution to this problem. It got reverted, but I still think the title could be made clearer. $\endgroup$ – Davislor May 25 '18 at 17:48
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You could try some variation on {}^n\text{P}_r which gives ${}^n\text{P}_r$. $\endgroup$ – N. Shales May 24 '18 at 15:46
  • 1
    $\begingroup$ (+1) btw. Here to help ;) $\endgroup$ – N. Shales May 24 '18 at 15:47
  • 1
    $\begingroup$ @N.Shales: If one really wants to use that notation, I recommend using boldface via \mathbf{P} like ${}^n\mathbf{P}_i$. But I think it may be better avoiding that notation as it can be confusing. For example, what does "$2{}^n\mathbf{P}_i$" (2{}^n\mathbf{P}_i) mean? $\endgroup$ – user21820 May 25 '18 at 6:01
  • 1
    $\begingroup$ Even if you isolate the whole term via 2{{}^n\mathbf{P}_i} it does not help much: "$2{{}^n\mathbf{P}_i}$". Unless you consistently use "$·$" like "$2·{{}^n\mathbf{P}_i}$"... $\endgroup$ – user21820 May 25 '18 at 6:04
  • 1
    $\begingroup$ @user21820: My suggestion was on how to achieve the notation Bill was attempting with Mathjax. Boldface is nice too though, good suggestion! I agree with you, I rarely use that notation for those reasons. If I use any special notation at all it is the falling factorial $n^{\underline{r}}$. $\endgroup$ – N. Shales May 25 '18 at 8:09
12
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
8
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.