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


    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:
    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!:

    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


    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook