Counting Arrangements and Derangements

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

  1. rpenner Fully Wired Staff Member

    Messages:
    4,833
    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
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. rpenner Fully Wired Staff Member

    Messages:
    4,833
    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}\)
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. rpenner Fully Wired Staff Member

    Messages:
    4,833
    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
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. rpenner Fully Wired Staff Member

    Messages:
    4,833
    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. Confused2 Registered Senior Member

    Messages:
    429
    See next post
     
  9. Confused2 Registered Senior Member

    Messages:
    429
    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. rpenner Fully Wired Staff Member

    Messages:
    4,833
    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. Confused2 Registered Senior Member

    Messages:
    429
    I seem to have posted by accident. Thank you for the courtesy of answering my question.
     
  12. rpenner Fully Wired Staff Member

    Messages:
    4,833
    !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. rpenner Fully Wired Staff Member

    Messages:
    4,833
    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. rpenner Fully Wired Staff Member

    Messages:
    4,833
    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

Share This Page