I am trying to figure out if the following expression:
(n^2 - n)! / ( n! ((n-1)!)^n ) is an integer for all positive integer n.
I tried the induction, but the induction case is running into problems. So, I was looking at permutation/combination problems, but so far, I couldn't come up with a convincing argument.
Does anybody has any thoughts on this to share ?
See values (n^2-n) can be devided by (n-1)n. However you added extra power n. It is hard to beleive that this will be integer.
Thanks Aleks Kleyn. Initial values of n mysteriously works. How do you go about solving this ? It's a problem so far.
Your expression is
(n^2-n)!
_______
n! ((n-1)!)^n
Let n=5
(5^2-5)! 20! 2432902008176640000
----------= --------------=--------------------------------=19799007228000
5!(4!)^5 120 24^5 120 1024
However the question is what is grows faster (you can consider derivative)
(n^2)! or (n!)^n
You can also change fraction like
(n^2-n)!n^n (n-1)(n^2-n-1)!
-----------------=---------------------
(n!)^(n+1) n((n-1)!)^(n+1)
May it will help. Probably you will see some patern for induction
If you are working with integers, integers squared and factorials (of integers), the result will always be an integer.
Gerard, how is your observation, which is obvious , proves my question ?
Hi Tridib,
What I think Gerard meant is somewhat like what I would do if I were to prove your question:
1) Take your big expression, and break it into smaller parts, say, A, B and C. Now show that if A, B and C are integers, then your expression is also an integer.
2) Now show that A, B and C are all integers by themselves.
3) If you can do that, you're done.
To begin, it is worth noting what Gerard said, i.e., that powers of integers are integers and factorials of integers also are. That means a factorial of a power of an integer is also an integer. That might help you solve your question.
Anyway, it is now resolved, but this could be helpful for someone else.
Cheers,
Hi Carvalho, thanks for your explanation.
But proving that statement, don't you have to break it down anyway ? Otherwise, I don't know any other method to prove it by keeping it as it is. The first thing you do to prove it is to break it down as much as possible, without loosing the generality of the statement, and then try to prove that statement. While doing this, we keep in mind, what Gerard has written above. So Gerard's suggestion is useless, and does nothing to prove it. Leaving this type of statement only improves Gerard's score, which is extremely unfair since it is a research forum, and I was looking for some good suggestions, like what Klyne wrote above.
Anyway, thanks for leaving your thoughts.
Hi, Dutta,
By reading Klyne's post carefully, I see the reason of your wrath against Gerard's answer. It doesn't suffice to prove the statements about powers of integers and factorials and bla bla: you need to show which one (denominator or numerator) grows faster.
I'm sorry for bothering you, now I can see the problem. Anyway, everyone who comes here will have the best of all: commom mistakes and the insightful hint of evaluating the derivative of both terms in the ratio, while keeping in mind the obviuos properties of the integers.
Best,
Luiz.
Hi Luiz, thanks.
I wouldn't put is as my wrath ( :) ), but it annoys me when one try's to be too smart, and trivialize everything by making meaningless statements as Gerard's. This problem that I was trying is by no means trivial, and need some work before it can be put into a manageable form, which one can then solve it. Although, I must admit that once you know what to do, it takes only 5 lines to solve it (:)).
Best,
Tridib
Note that (n-1) + (n-1) + ... (n-1) [n times] = n(n-1)=n^2-n so
(n^2-n)! / ((n-1)! ^ n) is a number of decompositions of n^2-n points into n groups of equal size (order of group DOES matter). Denote by A the set of such decompositions. Note that for every such decomposition there are precisely n! decompositions which same groups but with different order of them, so (n^2-n)! / (n! (n-1)! ^ n) is precisely a number of covers of n^2-n-point set by n sets of equal size hence it is an integer.
yes, its always integer for all positive value of n. We can generalize by reducing complexity of given expression using properties of factorial.
Hi Jaipratap, yes, we can certainly do that. But can you explain how u want to go ahead after you reduce it, like Ostap, he actually gave a solution.
Sure i have solution of this problem. I 'll inbox you answer of this problem....!!!
@Jaipratap. Please leave your solution here for others to see. These are searchable entries. Anybody looking for an answer to this question can see these entries. So leave your solution here for others to see.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Algebra