This site is supported by donations to The OEIS Foundation.
Number of arrangements
The number of arrangements of any subset of distinct objects is the number of one-to-one sequences that can be formed from any subset of distinct objects.[1]
Contents
Formulae
where are binomial coefficients and is the factorial of n.
A000522 The number of arrangements
- {1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101, 108505112, 1302061345, 16926797486, 236975164805, 3554627472076, 56874039553217, 966858672404690, ...}
The last digit (base 10) of 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
Number of derangements
|
Number of permutations
|
Number of arrangements
| |
---|---|---|---|
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
Recurrences
Other formulae
Comparison with approximations 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 is the round function and is the floor function.
Generating function
Ordinary generating function
The ordinary generating function for the number of arrangements is
Exponential generating function
The exponential generating function for the number of arrangements is
Asymptotic behaviour
The limit of the quotient of the number of arrangements of any subset of distinct objects over the number of permutations of distinct objects converges to (Cf. A001113 and Euler's number)
The limit of the quotient of the number of arrangements of any subset of distinct objects over the number of derangements of distinct objects converges to (Cf. A072334)
The geometric mean of the number of arrangements and the number of derangements is asymptotic to the number of permutations
Arrangements which are not permutations
The number of arrangements of proper subsets of distinct objects is given by
where the second summation gives the empty sum (defined as 0) for .
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
Notes
- ↑ Since the number of derangements of distinct objects is given by the subfactorial (!n) of , 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 as giving the number of arrangements of any subset of distinct objects. We couldn't use the term superfactorial as it is already in use for another concept.