Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: A counting problem

  1. Feb 19, 2005 #1
    show that [tex]\frac{ ((n^2)!)!}{(n!)^{n+1}}[/tex] is an integer.

    i was thinking of saying that there are so many people who can be put on a committee, etc etc which would make an integer. i don't think this is real hard but nothing is really jumping out at me
     
  2. jcsd
  3. Feb 20, 2005 #2
    [tex]\frac{ ((n^2)!)!}{(n!)^{n+1}}[/tex]

    Not to bad. The denominator can be broken into:
    [tex]
    (n^{n+1})((n-1)^{n+1})... ... ...
    [/tex]

    Each one of these term must be in the [itex] (n^2)![/itex] term in the numerator or be a divisor of this term.

    [tex]
    (n^2)! > n^{n+1}
    [/tex]

    Therefore [tex]\frac{ ((n^2)!)!}{(n!)^{n+1}}[/tex] must be an integer.
     
  4. Feb 20, 2005 #3
    update: i thought of something that might be easier. check this out


    the multinomial theorem says

    [tex]\left(\begin{array}{cc}n\\ r_1, r_2, ..., r_k \end{array} \right) = \frac{n!}{r_1!r_2!...r_k!}[/tex] for [tex]r_1 + r_2 + ... + r_k = n[/tex]

    so if i set [tex]r_1 = r_2 = ... = r_k = k[/tex], then [tex]r_1 + r_2 + ... + r_k = k.k = k^2[/tex] in which case the multimonial theorem gives me [tex]\frac{(k^2)!}{(k!)^k}[/tex] which is an integer by definiton, so i'm almost there & i just need to do the rest somehow
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook