This site is supported by donations to The OEIS Foundation.

# Number of arrangements

The number of arrangements of any subset of $n\,$ distinct objects is the number of one-to-one sequences that can be formed from any subset of $n\,$ distinct objects.

## Formulae

$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 ${n \choose k}\,$ are binomial coefficients and $n!\,$ is the factorial of n.

A000522 The number of arrangements $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 $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
$n\,$ Number of derangements

$d_{n}\equiv n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}\,$ $d_{n}\approx (1/e)~n!\,$ $d_{n}=\left[{\frac {n!}{e}}\right]=\left\lfloor {\frac {n!}{e}}+{\frac {1}{2}}\right\rfloor ,\,n\geq 1\,$ Number of permutations

$n!\,$ Number of arrangements

$a_{n}\equiv n!\sum _{k=0}^{n}{\frac {1}{k!}}\,$ $a_{n}\approx e~n!\,$ $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

$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!\,$ $={\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

$a_{n}=n\cdot a_{n-1}+1,\,n\,\geq \,1,\,a_{0}\,=\,1.\,$ ## Other formulae

$a_{n}=\left\lfloor e~n!\right\rfloor ,n\geq 1.\,$ $n\,$ $a_{n}\,$ $e~n!\,$ $\left[e~n!\right]\,$ $\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 $\left[n\right]\,$ is the round function and $\left\lfloor n\right\rfloor \,$ is the floor function.

## Generating function

### Ordinary generating function

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

$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 $a_{n}\,$ of any subset of $n\,$ distinct objects over the number of permutations $p_{n}\,$ of $n\,$ distinct objects converges to $e\,$ (Cf. A001113 and Euler's number)

$\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 $a_{n}\,$ of any subset of $n\,$ distinct objects over the number of derangements $d_{n}\,$ of $n\,$ distinct objects converges to $e^{2}\,$ (Cf. A072334)

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

$\lim _{n\to \infty }{\sqrt {a_{n}~d_{n}}}=n!\,$ ## Arrangements which are not permutations

The number of arrangements of proper subsets of $n\,$ distinct objects is given by

$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 $n\,=\,0\,$ .

$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, ...}