8
$\begingroup$

I know a proof that $\frac{(30n)!n!}{(15n)!(10n)!(6n)!}$ is an integer.

The proof goes as:

If a prime $p$ divides $(15n)!(10n)!(6n)!$, then the power of the prime dividing $(15n)!(10n)!(6n)!$ is lesser than the $(30n)!n!$. It is relatively easy to prove this.

$\textbf{My question is there a counting argument to prove that this is an integer?}$

By this, I mean does $\frac{(30n)!n!}{(15n)!(10n)!(6n)!}$ count something?

(I have a gut feeling that this should count something but I have not thought in depth about this).

For instance $\frac{n!}{r!(n-r)!}$ counts the number of ways of choosing $r$ objects out of $n$.

Also, are there other examples similar to this? (I tried searching for other such examples in vain)

  • 1
    (2n)!/(n!(n+1)!) is another example; these are the Catalan numbers. More generally ((k+1)n)!/(n!(kn+1)!) is an example.2010-11-12
  • 1
    Oh, and I think that (2m)!(2n)!/((m+n)!^2) is also an example. As I recall there was an MO thread where the two-variable generating function of this sequence was computed but I don't think it led to a combinatorial interpretation.2010-11-12
  • 0
    Oh cool. I am looking up the wiki on Catalan numbers. I assume these catalan numbers count something.2010-11-12
  • 1
    @Sivaram: yes, in fact they count more things than pretty much any other sequence...2010-11-12
  • 0
    For some reason I thought for such combinations to be integers the numbers within the factorial sign in the numerator and denominator must add up till I saw these Catalan numbers. Your second example falls in the category of my thought process though.2010-11-12
  • 0
    @Sivaram: I think I misremembered the second example. See my answer.2010-11-12

1 Answers 1

4

This MO thread has a lot of good information. I think we should be pessimistic. Pietro Majer's answer and the comments therein suggest that this would be hard, at least in the sense that one should not expect a proof anything like the proof for binomial coefficients.