1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorial proof-is this rigorous?

  1. Oct 30, 2006 #1

    0rthodontist

    User Avatar
    Science Advisor

    First, please don't give me too much information or suggest other ways to do it if you think this is not rigorous. This is not supposed to be collaborative.

    I am asked to prove that [tex]n!^{n+1}[/tex] divides [tex](n^2)![/tex]. I thought of a few ways to try to do this, but the first thing I got is the following combinatorial argument:

    Consider the possible arrangements of [tex](n^2)![/tex] distinct objects. The objects can be grouped into n groups of n objects each:
    a11a21...an1a12a22...an2...a1na2n...ann
    The objects can be permuted within each group of n elements ak1...akn, for n! ways each and [tex]n!^n[/tex] ways total. Then the n groups of objects themselves may be permuted with the other groups for an additional factor of n!, for a total number of arrangements of [tex]n!^{n+1}[/tex].

    These arrangements are not exhaustive of the [tex]n^2![/tex] total arrangements, since they specify that each of the n elements within each group must be contiguous. To produce all of the arrangements in this fashion, we may first choose which of the elements of the n groups are contiguous, and multiply that by number of ways to arrange those groups and objects as above. Therefore [tex]n!^{n+1}[/tex] divides [tex](n^2)![/tex], and specifically the quotient is:
    --for each group choose n elements for that group. [tex]\prod_{k=0}^{n}{{n^2-nk}\choose{n}}[/tex]
    --but this is an overcount since each set of n groups of elements can be picked in n! ways, so divide by n!:
    [tex]\frac{1}{n!}\prod_{k=0}^{n}{{n^2-nk}\choose{n}}[/tex]

    So, [tex]n!^{n+1} \cdot \frac{1}{n!}\prod_{k=0}^{n}{{n^2-nk}\choose{n}} = (n^2)![/tex]

    So if you're good with combinatorial-type proofs (the ones that look something like this, where you show two quantities are equal by counting them two different ways), can you tell me if this is rigorous enough?
     
    Last edited: Oct 30, 2006
  2. jcsd
  3. Oct 30, 2006 #2

    StatusX

    User Avatar
    Homework Helper

    It's a little hard to follow now, but it seems to be alright. I would spell out some of the steps in a little more detail. Also, there's a tiny problem with the last equation for (n!)^2, but I'm afraid to tell you what it is without risking helping you.
     
    Last edited: Oct 30, 2006
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Combinatorial proof-is this rigorous?
  1. Combinatorial Proof (Replies: 3)

  2. Combinatorial proof? (Replies: 2)

  3. Combinatorial Proof (Replies: 2)

  4. Combinatorial Proof? (Replies: 4)

  5. Combinatorial Proof (Replies: 1)

Loading...