Number of arrangements

This article needs more work.

Please help by expanding it!

The number of arrangements of any subset of $\scriptstyle n\,$ distinct objects is the number of one-to-one sequences that can be formed from any subset of $\scriptstyle 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 $\scriptstyle {n \choose k}\,$ are binomial coefficients and $\scriptstyle n!\,$ is the factorial of n.

A000522 The number of arrangements $\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 $\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

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

Comparison with approximations

$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 $\scriptstyle \left[n\right]\,$ is the round function and $\scriptstyle \left\lfloor n\right\rfloor \,$ is the floor function.

Generating function

Ordinary generating function

The ordinary generating function for the number of arrangements is

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

Exponential generating function

The exponential generating function for the number of arrangements is

$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 $\scriptstyle a_{n}\,$ of any subset of $\scriptstyle n\,$ distinct objects over the number of permutations $\scriptstyle p_{n}\,$ of $\scriptstyle n\,$ distinct objects converges to $\scriptstyle 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 $\scriptstyle a_{n}\,$ of any subset of $\scriptstyle n\,$ distinct objects over the number of derangements $\scriptstyle d_{n}\,$ of $\scriptstyle n\,$ distinct objects converges to $\scriptstyle 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 $\scriptstyle 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 $\scriptstyle 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, ...}

See also

• Number of derangements (given by the subfactorial, recognized term)
• Number of arrangements (given by the supfactorial, suggested term, since superfactorial refers to another concept)
• Factorial