Results 1 to 11 of 11

Math Help - Number of derangements of n objects

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    Number of derangements of n objects

    Recall that a derangement of a set S is a permutation \pi of S having no fixed points, i.e. \pi(s)\neq s \ \ \forall s \in S. If the number of derangements of \{1,\dots,n\} is !n, show that

    !n = \sum_{j=0}^n{n \choose j}(-1)^{n-j} j!.

    Hint :

    Spoiler:
    You might first want to show that if b_n is an arbitrary sequence and a_n=\sum_{j=0}^n{n\choose j}b_j, then b_n can be retrieved by b_n = \sum_{j=0}^n{n\choose j}(-1)^{n-j}a_j.

    Last edited by Bruno J.; February 9th 2010 at 03:49 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    769

    Question

    Is n! the same as !n?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    No! n! is the factorial and !n is the number of derangements of a set having n elements.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Recall that a derangement of a set S is a permutation \pi of S having no fixed points, i.e. \pi(s)\neq s \ \ \forall s \in S. If the number of derangements of \{1,\dots,n\} is !n, show that

    !n = \sum_{j=0}^n{n \choose j}(-1)^j j!.

    Hint :

    Spoiler:
    You might first want to show that if b_n is an arbitrary sequence and a_n=\sum_{j=0}^n{n\choose j}b_j, then b_n can be retrieved by b_n = \sum_{j=0}^n{n\choose j}(-1)^ja_j.

    A well-worded argument with the inclusion-exclusion principle shows that !n=n!\sum_{j=0}^{n}\frac{(-1)^j}{j!}. But \sum_{j=0}^{n}{n\choose j}(-1)^j j!. Applying the symmetry of the sum finishes the argument. I suppose you want me to show that inclusion-exclusion argument?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Haha... well yeah, that would certainly complete your proof!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1
    Quote Originally Posted by Bruno J. View Post
    Recall that a derangement of a set S is a permutation \pi of S having no fixed points, i.e. \pi(s)\neq s \ \ \forall s \in S. If the number of derangements of \{1,\dots,n\} is !n, show that

    [CENTER] !n = \sum_{j=0}^n{n \choose j}(-1)^j j!.
    Bruno J
    You need to adjust this form. For odd n it gives a negative of the correct answer.
    n=3 gives 1-3\cdot 1!+ 3\cdot 2! -3!=-2
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Bruno J. View Post
    Haha... well yeah, that would certainly complete your proof!
    I'll post one up later, if anyone else doesn't. Also, you can solve this with recurrence relations.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by Plato View Post
    Bruno J
    You need to adjust this form. For odd n it gives a negative of the correct answer.
    n=3 gives 1-3\cdot 1!+ 3\cdot 2! -3!=-2
    Quite right! I made a mistake. I have corrected it. Thank you Plato!
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    Spoiler:
    For j=1,2,\dots,n, let

    A_j=\{\sigma \in S_n|\, \sigma(j)=j\}.

    Then

    !n = n!-\left|\bigcup_{j=1}^nA_j\right|.

    By the inclusion-exclusion principle

    \left|\bigcup_{j=1}^nA_j\right|=\sum_{j=1}^{n}|A_i  |-\sum_{1\le j<k \le n} |A_j \cap A_k|+ \cdots +(-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n|.

    Consider the intersection

    A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_r}=\{\sigma \in S_n|\, \sigma(j_1)=j_1, \sigma(j_2)=j_2, \dots ,\sigma(j_r)=j_r\}, for 1 \le r \le n.

    There are \binom{n}{r} of these r-intersections, each of them having (n-r)! permutations. Thus, we have

    \sum_{1 \le j_{1} < j_{2} < \cdots < j_{r} \le n}|A_{j_1} \cap A_{j_2} \cap \cdots \cap A_{j_r}|=\binom{n}{r}(n-r)!,

    so

    !n = \binom{n}{0}n! -\left[\binom{n}{1}(n-1)!-\cdots +(-1)^{n-1}\binom{n}{n}(n-n)!\right]

     =\binom{n}{n}(-1)^{n-n}n!+\binom{n}{n-1}(-1)^{n-(n-1)}(n-1)!+\cdots+\binom{n}{0}(-1)^n0!

    =\sum_{j=0}^{n}\binom{n}{j}(-1)^{n-j}j!.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Good job, Black! You are an impressive new member. Are you a university student?

    I will post another nice solution later today.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Here is another proof.

    First, I prove the statement in the hint that I gave. Consider the exponential generating function

    g_B(z)=\sum_{j=0}^\infty b_j \frac{z^j}{j!}

    of the sequence B=\{b_j\}. By the basic properties of exponential generating functions, the product of the exponential generating functions of two sequences is the exponential generating function of their binomial convolution. So we have

    g_A(z) = \sum_{j=0}^\infty a_j \frac{z^j}{j!} = e^zg_B(z)

    and so g_B(z)=e^{-z}g_A(z). Extracting the coefficient of \frac{z^n}{n!} on both sides we obtain b_n = \sum_{j=0}^n {n \choose j}(-1)^{n-j}a_j as required.

    Now let us partition the set S_n of permutations of \{1,\dots,n\} as follows; let T_j \subset S_n denote those permutations which have precisely j fixed points, for j=0, \dots, n. Clearly there are {n \choose j} ways of picking the elements which are to be fixed, and the remaining n-j elements have to be deranged. So |T_j| = {n \choose j}!(n-j). Since the T_j are clearly distinct we have

    |S_n|=n!=\sum_{j=0}^n|T_j| = \sum_{j=0}^n{n \choose j}!(n-j) = \sum_{j=0}^n{n \choose j}!j

    because {n \choose j} = {n \choose n-j}. Now just apply the binomial involution just proved!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of different pairings of 2n objects.
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 21st 2011, 11:33 AM
  2. Mathematical Thinking: 2 Derangements/proof questions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 11th 2010, 05:48 AM
  3. Replies: 2
    Last Post: December 10th 2010, 12:38 PM
  4. Derangements(help me asap)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 13th 2010, 02:07 AM
  5. Replies: 10
    Last Post: May 28th 2009, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum