If we can say n is a natural number, then prove that $(n!)^n \mid (n^2)!$. I want a process involving variables only. Please help me.

  • $\begingroup$ Can any thing be done to prove this using only basic divisibility rules and congruences? I do not understand. $\endgroup$ – Pranesh Ranjan Das Feb 8 '18 at 17:11
  • 2
    $\begingroup$ Can any thing be done to have you edit your questions and include your efforts/workings within the post, and not just post what you want and how you want it? This site wants you to include your own efforts, because it expects you to try on your own; it's okay to get stuck; just show us where your are stuck, and explain why, and what you do not understand at that particular moment. Do not tell users to prove, do, evaluate, solve; We consider that rude. You may ask, but don't command. $\endgroup$ – amWhy Feb 8 '18 at 18:10
  • $\begingroup$ According to this answer, we even have $(n!)^{n+1}\mid\left(n^2\right)!$. $\endgroup$ – robjohn Feb 9 '18 at 2:26

If you have an $n\times n$ grid of cells, and you want to fill those cells with $n$ of each number from $1$ to $n$ so that there is one number in each cell, then $$ \frac{(n^2)!}{(n!)^n} $$ is the number of different ways you can do that, and therefore it has to be an integer.

Different example (which is actually the same example of you look closely): You have $n^2$ people, and you need to divide them into teams: a red team, a blue team, a green team, and so on. There are $n$ different teams, and each team must have $n$ people in them. Then there are $\frac{(n^2)!}{(n!)^2}$ different ways to assign people to these teams.

  • $\begingroup$ what a cool answer!, +1 $\endgroup$ – avz2611 Feb 8 '18 at 16:42
  • $\begingroup$ Uh could you please answer the question in a more algebraic manner? Could not understand what you want to say $\endgroup$ – Pranesh Ranjan Das Feb 8 '18 at 16:43
  • $\begingroup$ @PraneshRanjanDas Sorry, I think an algebraic proof will be significantly longer and a lot more difficult to follow. It will involve prime factorisation, and how many times a given prime goes into $n!$ and $(n^2)!$. It has long sums and floor functions all over. A combinatorial proof like this is by far the simplest way. I can try to come up with a different example. $\endgroup$ – Arthur Feb 8 '18 at 16:47

We can consider $(S_n)^n = S_n \times S_n \times \dots \times S_n$ as a subgroup of $S_{n^2}$ Just let the first copy act on the first $n$ elements in an $n^2$ element set, the second copy on the next $n$ elements etc. This gives a faithful action of $(S_n)^n$ on an $n^2$ element set, hence an embedding $(S_n)^n \hookrightarrow S_{n^2}$.

We get $(n!)^n \mid (n^2)!$ by Lagrange's theorem.

Edit: This method can be generalized to show that the multinomial coefficient $\displaystyle \frac{(n_1 + \ldots + n_k)!}{n_1! \cdot \ldots \cdot n_k!}$ mentioned in other answers is an integer.

Consider $S_{n_1} \times S_{n_2} \times \dots \times S_{n_k}$ and let this group act on an $n_1 + n_2 + \dots + n_k$ element set by having the first factor act on the first $n_1$ elements, the second on the next $n_2$ elements, etc. giving an embedding $S_{n_1} \times S_{n_2} \times \dots \times S_{n_k} \hookrightarrow S_{n_1 + \ldots + n_k}$. Then the statement follows again by Lagrange's theorem.

Edit 2:

With more careful use of group theory, we can even prove a stronger statement.

Consider the semidirect product $S_n \rtimes (S_n)^n$ where $S_n$ acts on $(S_n)^n$ by permuting the different factors (This is also called a wreath product)

We can define an action of $S_n \rtimes (S_n)^n$ on an $n^2$ set as follows: Partition the $n^2$ set in $n$ subsets of $n$ elements. We let the left factor $S_n$ of $S_n \rtimes (S_n)^n$ act by permuting the $n$ subsets and let each factor of $(S_n)^n$ act on one of the $n$ subsets. These actions interact in the right way to define an action of the semidirect product $S_n \rtimes (S_n)^n$, which is also faithful. We get an embedding $S_n \rtimes (S_n)^n \hookrightarrow S_{n^2}$ and we get $(n!)^{n+1} \mid (n^2)!$ by Lagrange's theorem.

  • $\begingroup$ This answer may be beyond the scope of the OP, but I think it's the best explanation among the answers here of why rather than merely how the relation holds. $\endgroup$ – anomaly Feb 8 '18 at 17:04
  • $\begingroup$ @anomaly the OP asked in the comments for a more "algebraic" solution and this is what came to my mind. I agree that it may not be what he had in mind, though. $\endgroup$ – Lukas Heger Feb 8 '18 at 17:12
  • $\begingroup$ No, I think it's great, and gave it a $+1$. I think the OP was looking for an argument along the lines of reading off the prime powers dividing $(n!)^n$ and $(n^2)!$, but that's not a good way of approaching the problem. $\endgroup$ – anomaly Feb 8 '18 at 17:16
  • 1
    $\begingroup$ (+1) The stronger statement was also proven in this answer. $\endgroup$ – robjohn Feb 9 '18 at 11:01
  • $\begingroup$ @robjohn perfect, the linked statement generalizes the extensions of both edits. I have added a group-theoretic proof to the linked question $\endgroup$ – Lukas Heger Feb 9 '18 at 13:37

The given value is the multinomial coefficient $\binom{n^2}{n \cdots n}$. It's thus the coefficient of $x_1^n \cdots x_n^n$ in $(x_1 + \cdots + x_n)^{n^2}$, for example, and in particular is an integer.


Not the answer you're looking for? Browse other questions tagged or ask your own question.