This site is supported by donations to The OEIS Foundation.

# Number of arrangements

The number of arrangements of any subset of ${\displaystyle \scriptstyle n\,}$ distinct objects is the number of one-to-one sequences that can be formed from any subset of ${\displaystyle \scriptstyle n\,}$ distinct objects.[1]

## Formulae

${\displaystyle a_{n}=\sum _{k=0}^{n}{n \choose k}k!=\sum _{k=0}^{n}{\frac {n!}{k!(n-k)!}}k!=n!\sum _{k=0}^{n}{\frac {1}{(n-k)!}}=n!\sum _{k=0}^{n}{\frac {1}{k!}}\,}$

where ${\displaystyle \scriptstyle {n \choose k}\,}$ are binomial coefficients and ${\displaystyle \scriptstyle n!\,}$ is the factorial of n.

A000522 The number of arrangements ${\displaystyle \scriptstyle a_{n},\,n\,\geq \,0.\,}$

{1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486, 236975164805, 3554627472076, 56874039553217, 966858672404690, ...}

The last digit (base 10) of ${\displaystyle \scriptstyle a_{n},\,n\geq 0,\,}$ seems to follow the pattern (of length 10)

{1, 2, 5, 6, 5, 6, 7, 0, 1, 0}

## Comparison of derangement, permutation and arrangement numbers

Comparison of derangement, permutation and arrangement numbers
${\displaystyle n\,}$ Number of derangements

${\displaystyle d_{n}\equiv n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\,}$

${\displaystyle d_{n}\approx (1/e)~n!\,}$

${\displaystyle d_{n}=\left[{\frac {n!}{e}}\right]=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor ,\,n\geq 1\,}$

Number of permutations

${\displaystyle n!\,}$

Number of arrangements

${\displaystyle a_{n}\equiv n!\sum _{k=0}^{n}{\frac {1}{k!}}\,}$

${\displaystyle a_{n}\approx e~n!\,}$

${\displaystyle a_{n}=\left\lfloor e~n!\right\rfloor ,\,n\geq 1\,}$

0 1 1 1
1 0 1 2
2 1 2 5
3 2 6 16
4 9 24 65
5 44 120 326
6 265 720 1957
7 1854 5040 13700
8 14833 40320 109601
9 133496 362880 986410
10 1334961 3628800 9864101
11 14684570 39916800 108505112
12 176214841 479001600 1302061345
13 2290792932 6227020800 16926797486
14 32071101049 87178291200 236975164805
15 481066515734 1307674368000 3554627472076
16 7697064251745 20922789888000 56874039553217
17 130850092279664 355687428096000 966858672404690
18 2355301661033953 6402373705728000 17403456103284421
19 44750731559645106 121645100408832000 330665665962404000
20 895014631192902121 2432902008176640000 6613313319248080001

## Example

The number of one-to-one sequences that can be formed from any subset of 5 distinct objects {a, b, c, d, e} is

${\displaystyle a_{5}={5 \choose 5}5!+{5 \choose 4}4!+{5 \choose 3}3!+{5 \choose 2}2!+{5 \choose 1}1!+{5 \choose 0}0!={\Bigg (}{\frac {1}{0!}}{\Bigg )}5!+{\Bigg (}{\frac {5}{1!}}{\Bigg )}4!+{\Bigg (}{\frac {5\cdot 4}{2!}}{\Bigg )}3!+{\Bigg (}{\frac {5\cdot 4\cdot 3}{3!}}{\Bigg )}2!+{\Bigg (}{\frac {5\cdot 4\cdot 3\cdot 2}{4!}}{\Bigg )}1!+{\Bigg (}{\frac {5\cdot 4\cdot 3\cdot 2\cdot 1}{5!}}{\Bigg )}0!\,}$
${\displaystyle ={\frac {5!}{0!}}+{\frac {5!}{1!}}+{\frac {5!}{2!}}+{\frac {5!}{3!}}+{\frac {5!}{4!}}+{\frac {5!}{5!}}=5!\sum _{k=0}^{5}{\frac {1}{k!}}=120+120+60+20+5+1=326\,}$

## Recurrences

${\displaystyle a_{n}=n\cdot a_{n-1}+1,\,n\,\geq \,1,\,a_{0}\,=\,1.\,}$

## Other formulae

${\displaystyle a_{n}=\left\lfloor e~n!\right\rfloor ,n\geq 1.\,}$
 ${\displaystyle n\,}$ ${\displaystyle a_{n}\,}$ ${\displaystyle e~n!\,}$ ${\displaystyle \left[e~n!\right]\,}$ ${\displaystyle \left\lfloor e~n!\right\rfloor \,}$ 0 1 2.7182 3 2 1 2 2.7182 3 2 2 5 5.4365 5 5 3 16 16.3096 16 16 4 65 65.2387 65 65 5 326 326.1938 326 326 6 1957 1957.1629 1957 1957 7 13700 13700.1404 13700 13700 8 109601 109601.1233 109601 109601 9 986410 986410.1099 986410 986410

where ${\displaystyle \scriptstyle \left[n\right]\,}$ is the round function and ${\displaystyle \scriptstyle \left\lfloor n\right\rfloor \,}$ is the floor function.

## Generating function

### Ordinary generating function

${\displaystyle G_{\{a_{n}\}}(x)\equiv \sum _{n=0}^{\infty }a_{n}~x^{n}=?\,}$

### Exponential generating function

${\displaystyle E_{\{a_{n}\}}(x)\equiv \sum _{n=0}^{\infty }a_{n}~{\frac {x^{n}}{n!}}={\frac {e^{x}}{1-x}}\,}$

## Asymptotic behaviour

The limit of the quotient of the number of arrangements ${\displaystyle \scriptstyle a_{n}\,}$ of any subset of ${\displaystyle \scriptstyle n\,}$ distinct objects over the number of permutations ${\displaystyle \scriptstyle p_{n}\,}$ of ${\displaystyle \scriptstyle n\,}$ distinct objects converges to ${\displaystyle \scriptstyle e\,}$ (Cf. A001113 and Euler's number)

${\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{p_{n}}}=\lim _{n\to \infty }{\frac {a_{n}}{n!}}=e\,}$

The limit of the quotient of the number of arrangements ${\displaystyle \scriptstyle a_{n}\,}$ of any subset of ${\displaystyle \scriptstyle n\,}$ distinct objects over the number of derangements ${\displaystyle \scriptstyle d_{n}\,}$ of ${\displaystyle \scriptstyle n\,}$ distinct objects converges to ${\displaystyle \scriptstyle e^{2}\,}$ (Cf. A072334)

${\displaystyle \lim _{n\to \infty }{\frac {a_{n}}{d_{n}}}=e^{2}\,}$

The geometric mean of the number of arrangements and the number of derangements is asymptotic to the number of permutations

${\displaystyle \lim _{n\to \infty }{\sqrt {a_{n}~d_{n}}}=n!\,}$

## Arrangements which are not permutations

The number of arrangements of proper subsets of ${\displaystyle \scriptstyle n\,}$ distinct objects is given by

${\displaystyle a_{n}-n!=n!\left\{\sum _{k=0}^{n}{\frac {1}{k!}}\right\}-n!=n!\sum _{k=1}^{n}{\frac {1}{k!}}\,}$

where the second summation gives the empty sum (defined as 0) for ${\displaystyle \scriptstyle n\,=\,0\,}$.

${\displaystyle a_{n}-n!=\left\lfloor (e-1)~n!\right\rfloor ,n\geq 1.\,}$

## Sequences

A000522 Total number of arrangements of a set with n elements: a(n) = Sum_{k=0..n} n!/k!.

{1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486, 236975164805, 3554627472076, 56874039553217, 966858672404690, 17403456103284421, ...}

A002627 a(n) = n*a(n-1) + 1, a(0) = 0. (Number of arrangements which are not permutations.)

{0, 1, 3, 10, 41, 206, 1237, 8660, 69281, 623530, 6235301, 68588312, 823059745, 10699776686, 149796873605, 2246953104076, 35951249665217, 611171244308690, 11001082397556421, ...}

1. Since the number of derangements of ${\displaystyle \scriptstyle n\,}$ distinct objects is given by the subfactorial (!n) of ${\displaystyle \scriptstyle n\,}$, it would be tempting to define the supfactorial (with ¡n as suggested notation, the dot of the inverted exclamation mark conveniently appearing above instead of below) of ${\displaystyle \scriptstyle n\,}$ as giving the number of arrangements of any subset of ${\displaystyle \scriptstyle n\,}$ distinct objects. We couldn't use the term superfactorial as it is already in use for another concept.