# Combinatorial proof-is this rigorous?

1. Oct 30, 2006

### 0rthodontist

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 $$n!^{n+1}$$ divides $$(n^2)!$$. 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 $$(n^2)!$$ 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 $$n!^n$$ 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 $$n!^{n+1}$$.

These arrangements are not exhaustive of the $$n^2!$$ 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 $$n!^{n+1}$$ divides $$(n^2)!$$, and specifically the quotient is:
--for each group choose n elements for that group. $$\prod_{k=0}^{n}{{n^2-nk}\choose{n}}$$
--but this is an overcount since each set of n groups of elements can be picked in n! ways, so divide by n!:
$$\frac{1}{n!}\prod_{k=0}^{n}{{n^2-nk}\choose{n}}$$

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

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. Oct 30, 2006

### StatusX

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