# Counting Arrangements and Derangements

Discussion in 'Physics & Math' started by rpenner, Jan 9, 2017.

1. ### rpennerFully WiredStaff Member

Messages:
4,765
If we have n distinguishable objects, and we want to know how many ways we have to order them, that's the number of arrangements or permutations of a set of size n.

That number is, rather famously, n! (say "n factorial"). And we have a number of ways to write it.

$\textrm{card} \, S_n \equiv \textrm{card} \, \left\{ f \, | \, f : \textrm{ordinal}_n \xrightarrow[\textrm{onto}]{\textrm{1-to-1}} \textrm{ordinal}_n \right\} \\ n! \equiv \prod_{k=1}^{n} k \\ \Gamma ( n + 1 ) \equiv \int_{0}^{\infty} x^n \, e^{-x} \, dx \\ \forall n \in \mathbb{N}_0 \quad \textrm{card} \, S_n \, = \, n! \, = \, \Gamma ( n + 1 )$

Proof:
If n = 0, then the number of ways to map ordinal 0 to ordinal 0 is the set that just has the empty function (set), so cardinality = 1. 0! = the product over the empty set, which is 1 by definition. The integral for n=0 is simply $\int_{0}^{\infty} x^n \, e^{-x} \, dx = e^0 - e^{-\infty} = 1$.

If $\textrm{card} \, S_n = n! = \Gamma ( n + 1 )$ then
$\textrm{card} \, S_{n+1}$ = number of different items a item may be paired with another item, including itself, in a set of n+1 item, times the ways to arrange the remaining items = $(n+1) \textrm{card} \, S_n$
By definition, $(n+1)! = \prod_{k=1}^{n+1} k = (n+1) \prod_{k=1}^{n} k = (n+1) n!$.
$\Gamma(n + 2) = \int_{0}^{\infty} x^{n+1} \, e^{-x} \, dx = \int_{-1}^{0} v du$ with $u = - e^{-x}, \quad du = e^{-x} dx, \quad v = x^{n+1}, \quad dv = (n+1) x^n dx$.
By integration by parts,
$\int_{-1}^{0} v du = \left[ u v \right] _{u=-1}^{u=0} - \int_{0}^{\infty} u dv = \left[ -e^{-\infty} \infty^{n+1} - -e^{-0} 0^{n+1} \right] - \int_{0}^{\infty} -e^{-x} (n+1) x^n dx \\ = 0 + (n+1) \int_{0}^{\infty} x^n e^{-x} dx = (n+1) \Gamma(n+1)$.

So we have what we need to prove the relation for all natural numbers by induction.

Last edited: Jan 11, 2017

3. ### rpennerFully WiredStaff Member

Messages:
4,765
Derangements
A derangement is an arrangement where no element remains in place. The common way of counting it is the subfactorial, !n.

$\begin{array}{r|rr|c} n & !n & n! & !n / !n \\ \hline \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 2 & 1 & 2 & \frac{1}{2} \\ 3 & 2 & 6 & \frac{1}{3} \\ 4 & 9 & 24 & \frac{3}{8} \\ 5 & 44 & 120 & \frac{11}{30} \\ 6 & 265 & 720 & \frac{53}{144} \\ 7 & 1854 & 5040 & \frac{103}{280} \\ 8 & 14833 & 40320 & \frac{2119}{5760} \\ 9 & 133496 & 362880 & \frac{16687}{45360} \\ 10 & 1334961 & 3628800 & \frac{16481}{44800} \end{array}$

$!n = \frac{1}{e} \int_{-1}^{\infty} x^n e^{-x} \, dx = \frac{1}{e} \int_{0}^{\infty} (t-1)^n e^{1-t} \, dt = \int_{0}^{\infty} (x-1)^n e^{-x} \, dx = \sum_{k=0}^{n} (-1)^{k} {n \choose k } (n-k)! = \sum_{k=0}^{n} (-1)^{k} \frac{n!}{k!}$
$!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$ which lends itself to proving $\lim_{n\to\infty} \frac{!n}{n!} = e^{-1}$

5. ### rpennerFully WiredStaff Member

Messages:
4,765
Distinguishable permutations of multisets
Consider a set where there are n "types" of objects, and each type has a certain multiplicity, $m_k$ Then the number of items is $M = \sum_{k=1}^{n} m_k$ so there are M! permutations of this set, but if we can't tell what an object is, but only its type, then it follows that there are only $\frac{ \left( \sum_{k=1}^{n} m_k \right) ! }{ \prod_{k=1}^{n} m_k ! }$ distinguishable ways to arrange them. If we are talking about the M letters (n=26) of a word, this is a count of (potential) anagrams.

In analogy with the binomial, this is called the multinomial.

$\begin{array}{c|rr} \textrm{Word} & M & \frac{ \left( \sum m_k \right) ! }{ \prod m_k ! } \\ \hline \\ \textrm{haha} & 4 & 6 \\ \textrm{queue} & 5 & 30 \\ \textrm{plaque} & 6 & 720 \\ \textrm{hotshots} & 8 & 2520 \\ \textrm{intestines} & 10 & 113400 \end{array}$

Last edited: Jan 11, 2017

7. ### rpennerFully WiredStaff Member

Messages:
4,765
Derangements of multisets
I found a paper (but sent the references down a one-way-hole) where the number of derangements could be counted.

//Edit: Even, S.; J. Gillis (1976). "Derangements and Laguerre polynomials". Mathematical Proceedings of the Cambridge Philosophical Society. 79 (01): 135–143.

But it was written in terms of Laguerre polynomials.

$L_0(x) = 1 \\ L_1(x) = 1 - x \\ L_n(x) = \frac{e^x}{n!} \frac{d^n \; }{d x^n} ( x^n e^{-x} ) = \sum_{k=0}^n \frac{(-1)^k}{k!} { n \choose k } x^k = \frac{1}{n} \left[ (2n -1 - x) L_{n-1} (x) + (1-n) L_{n-2} (x) \right]$

The number we are looking for is given by
$\mathcal{D}( m_1, m_2, \dots ) = (-1)^{M} \int_{0}^{\infty} e^{-x} \left( \prod_{k=1}^{n} m_k ! \; L_{m_k}(x) \right) dx$
which reduces to an integer weighted sum of factorials.

Leaving out the factors of $m_k!$ we obtain the distinguishable derangements of a word.

$\begin{array}{c|rrr} \textrm{Word} & M & \mathcal{D} & \mathcal{D} / \prod m_k! \\ \hline \\ \textrm{aaa} & 3 & 3! - 9 \cdot 2! + 18 \cdot 1! - 6 \cdot 0! = 0 & 0 \\ \textrm{aha} & 3 & 3! - 5 \cdot 2! + 6 \cdot 1! - 2 \cdot 0! = 0 & 0 \\ \textrm{cat} & 3 & 3! - 3 \cdot 2! + 3 \cdot 1! - 1 \cdot 0! = 2 & 2 \\ \textrm{haha} & 4 & 4! - 8 \cdot 3! + 20 \cdot 2! - 16 \cdot 1! + 4 \cdot 0! = 4 & 1 \\ \textrm{queue} & 5 & 5! - 9 \cdot 4! + 28 \cdot 3! - 36 \cdot 2! + 20 \cdot 1! - 4 \cdot 0! = 16 & 4 \\ \textrm{plaque} & 6 & 6! - 6 \cdot 5! + 15 \cdot 4! - 20 \cdot 3! + 15 \cdot 2! - 6 \cdot 1! + 1 \cdot 0! = 265 & 265 \\ \textrm{hotshots} & 8 & 8! - 16 \cdot 7! + 104 \cdot 6! - 352 \cdot 5! + 664 \cdot 4! - 704 \cdot 3! + 416 \cdot 2! - 128 \cdot 1! + 16 \cdot 0! = 4752 & 297 \\ \textrm{intestines} & 10 & 10! - 20 \cdot 9! + 170 \cdot 8! - 800 \cdot 7! + 2280 \cdot 6! - 4064 \cdot 5! + 4560 \cdot 4! - 3200 \cdot 3! + 1360 \cdot 2! - 320 \cdot 1! + 32 \cdot 0! = 440192 & 13756 \end{array}$

Last edited: Jan 9, 2017
8. ### Confused2Registered Senior Member

Messages:
334
See next post

9. ### Confused2Registered Senior Member

Messages:
334
Card Sn is equivalent to {?} notation remains opaque.
Notation in Googlable form would be appreciated

Something(?) n is an element (?) of N0. N0 makes a surprise appearance and is elsewhere defined?

Gamma function (like finding the wreck of the Titanic)
https://en.wikipedia.org/wiki/Gamma_function

Pi function:
http://math.stackexchange.com/questions/234209/derivative-of-gauss-pi-function

I don't expect (at best) to get beyond the first post and even that may take months.

10. ### rpennerFully WiredStaff Member

Messages:
4,765
The cardinality of the symmetric group on n elements is equal to the cardinality of the set of all bijections between the ordinal n and itself, basically by definition as the ordinal n has n elements when n is a natural number and the symmetric group is basically the set of bijections with a rule which allows composition of functions, identical to the ordinary rule of composition of functions.

11. ### Confused2Registered Senior Member

Messages:
334
I seem to have posted by accident. Thank you for the courtesy of answering my question.

12. ### rpennerFully WiredStaff Member

Messages:
4,765
!0 = 1
!1 = 0 # Because one time can never be out of sequence
!2 = 1 # Because flip-flopping is the only non-identity permutation of two items. {21}
!3 = 2 # { 231, 312 }
!n = (n-1) [ !(n-1) + !(n-2) ]
Why? Every derangement is a permutation with no cycles of length 1, because a cycle of length 1 is a fixed point.
If the first item is in a cycle of length k (which can happen in $\frac{(n-1)!}{(n-k)!} = (k-1)! { {n-1} \choose {k-1} }$ ways, then the remaining items can be permuted in !(n-k) ways. k has to be a number between 2 and n. So $!n = \sum_{k=2}^{n} (k-1)! { {n-1} \choose {k-1} } \, !(n-k) \; = \; (n-1) \sum_{k=2}^{n} \frac{(n-2)!}{(n-k)!} \, !(n-k)$.
So if (n > 2) we have:
$!n / (n-1) \; = \; \sum_{k=2}^{n} \frac{(n-2)!}{(n-k)!} \, !(n-k) \; = \; !(n-2) + \sum_{k=3}^{n} \frac{(n-2)!}{(n-k)!} \, !(n-k) \\ \quad = \; !(n-2) + \sum_{k=2}^{n-1} \frac{(n-2)!}{(n-k-1)!} \, !(n-k-1) \; = \; !(n-2) + ((n-1)-1) \sum_{k=2}^{n-1} \frac{((n-1)-2)!}{((n-1)-k)!} \, !((n-1)-k) \; = \; !(n-2) + !(n-1)$.
Thus $!n = (n-1) \left[ !(n-1) + !(n-2) \right]$.

But $(n-1) \left[ (n-1)! + (n-2)! \right] = (n-1) \left[ (n-1) + 1 \right] (n-2)! = (n-1) n (n-2)! = n!$ .

So in general the recurrence $a_n = (n-1) ( a_{n-1} + a_{n-2} )$ has solution $a_n \; = \; a_0 \, !n \; + \; a_1 \, ( n! \, - \, !n ) \approx ( a_0 e^{-1} + ( 1 - e^{-1} ) a_1) n!$

Last edited: Jan 10, 2017
13. ### rpennerFully WiredStaff Member

Messages:
4,765
OK. So maybe that argument could be streamlined with less algebra and manipulation of sums.

If we look at permutations of n distinct, orderable items, each permutation can be factored into cycles (orbits of elements), and each cycle has a size which is the minimum positive number of iterated permutations before every element in the cycle is back in its original place.

Example: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} -> {5, 0, 6, 7, 1, 4, 9, 2, 8, 3} can be written as (0, 5, 4, 1)(2, 6, 9, 3, 7)(8) and

So the natural way to go from a permutation with n elements to the list of similar permutation with n+1 elements is to insert the new (largest) element in a cycle by itself (1 distinct way to do this) or to insert the new element into a non-initial position in an existing cycle, (n ways). So $a_{n+1} = a_{n} + n a_{n} = (a+1) a_{n}$ is the natural recursion and since $a_0 = 1$ has particular solution of $a_n = n!$.

A derangement is a permutation without any 1-cycles. So we can't add an element in a cycle by itself, to increase the number of cycles we need to add a 2-cycle (in either order) of elements to derangements of 2 less elements. But while one of the elements is the largest, the other in the new 2-cycle can be smaller than any other element, while the other way this could go is to augment one of the existing cycles of a derangement with one less element. So $a_{n+2} = (n+1) a_{n} + (n+1) a_{n+1} = (n+1) ( a_{n} + a_{n+1} )$. This recursion, with $a_0 = 1, \; a_1 = 0$, as noted above, naturally gives, $a_{n} = !n$.

The permanent ( https://en.wikipedia.org/wiki/Permanent ) of a n×n square matrix with only ones is n!. If the diagonal is zero and every other element is 1, the permanent is !n. In general, the permanent of a n×n square matrix with elements restricted to only 0's and 1's is a count of all allowable permutations on n elements where the transition from i to j is allowed only when $a_{ij} = 1$. But since the permanent is a sum over all permuations of products of elements corresponding to each permutation, this is not obviously useful to simplify thinking.

$\frac{!n}{n!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!} \\ e^z = \sum_{k=0}^{\infty} \frac{z^k}{k!} \\ e^{-1} = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!} \\ !n = n! e^{-1} - n! \sum_{k=n+1}^{\infty} \frac{(-1)^k}{k!} \approx n! e^{-1} + \frac{(-1)^n}{n + 2}$

Last edited: Jan 11, 2017
14. ### rpennerFully WiredStaff Member

Messages:
4,765
Partial derangements

If I have n distinct items, and I want to know how many permutations of them have exactly m fixed points (alternately, 1-cycles), that number is (obviously) the product of the ways to select m items to be fixed points times the number of ways to derange n-m elements. These are the rencontres numbers.

$D_{n,m} \; = \; { n \choose m } \, D_{n-m, 0} \; = \; { n \choose m } \, !(n - m) \; = \; \frac{n!}{m!} \sum_{k=0}^{n-m} \frac{(-1)^k}{k!}$

It appears (a conjecture based on experiment) that $\sum_{m=0}^{n} m^k D_{n,m} \; = \; n! \sum_{m=0}^{\infty} \frac{m^k}{e \, m!} \; = \; n! B_k$ when $0 \leq k \leq n$. Specifically, the average number of 1-cycles in a random permutation is 1.

//Edit: This result was proven in Pitman, J. "Some Probabilistic Aspects of Set Partitions." Amer. Math. Monthly 104, 201-209, 1997.

Which would mean in the limit of large n, $\lim_{n\to\infty} \frac{1}{n!} D_{n,m} = \frac{1}{e m!}$ which means the rencontres numbers have the limiting form of the Poisson distribution with mean of 1.

https://en.wikipedia.org/wiki/Dobiński's_formula
http://mathworld.wolfram.com/BellNumber.html

Last edited: Jan 13, 2017