- #1

0rthodontist

Science Advisor

- 1,230

- 0

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:

a

The objects can be permuted within each group of n elements a

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?

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:

a

_{11}a_{21}...a_{n1}a_{12}a_{22}...a_{n2}...a_{1n}a_{2n}...a_{nn}The objects can be permuted within each group of n elements a

_{k1}...a_{kn}, 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: