Proof of the integrality of A211417 and A211418.

Peter Bala, April 2012 (revised and corrected October 2015)

For the convenience of users of the database we include a proof of a result of Chebyshev:

	A211417(n) = (30*n)!*n!/((15*n)!*(10*n)!*(6*n)!) is an integer for all n.

We also prove the generalization: for real r >= 0

	floor(30*r)!*floor(r)!/(floor(15*r)!*floor(10*r)!*floor(6*r)!)
	
is an integer.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Let a(n) = A211417(n).

Let c/d be a rational number and let ord_p(c/d) denote the power to which a prime p
appears in the prime factorization of c/d. In order to show the rational number a(n)
is an integer it will suffice to show that ord_p(a(n)) is nonnegative for each prime
p. The proof of this assertion makes use of Legendre's theorem on the order in which
a prime divides a factorial:

	ord_p(n!) = floor(n/p) + floor(n/p^2) + floor(n/p^3) + ....

By Legendre's theorem we see that ord_p(a(n)) equals the sum over k = 1,2,... of the
terms 

	floor(30*n/p^k) + floor(n/p^k)

	- floor(15*n/p^k) - floor(10*n/p^k) - floor(6*n/p^k)

(the sum of course has only a finite number of nonzero terms). The nonnegativity of
this sum, and hence the integrality of a(n), is then a consequence of the following
result:

LEMMA

For real x >= 0 we have

  	floor(15*x) + floor(10*x) + floor(6*x) <= floor(30*x) + floor(x).

PROOF

We require the following simple property of the floor function:

For real x and y

 	floor(x) + floor(y) <= floor(x + y).	   			... (1)

We can write the real number 30*x in the form

	30*x = 30*n + m + e						... (2)

where n and m are nonnegative integers with 0 <= m < 30, and where

0 <= e < 1.  

From (2) we find

	floor(30*x) = 30*n + m
and
	floor(x) = n.

Thus

	floor(30*x) + floor(x) = (30*n + m) + n = 31*n + m.		... (3)

Again using (2) we find

	floor(15*x) + floor(10*x) + floor(6*x) 

	= (15*n + floor(m/2)) + (10*n + floor(m/3)) + (6*n + floor(m/5))

	= 31*n + floor(m/2) + floor(m/3) + floor(m/5)

	<= 31*n + floor(m/2 + m/3 + m/5) 	(by (1))

	= 31*n + floor(31*m/30) 

	= 31*n + m 			(since 0 <= m < 30)

	= floor(30*x) + floor(x).	(by (3)).

END PROOF.

We now give a generalization of Chebyshev's result, which includes the integrality of
A211418 as a particular case. It will be convenient in what follows to abbreviate notation
and write f(x) for floor(x). We require the following standard result for the floor function:

for positive integers m and n and real x

	f(f(x/m)/n) = f(x/(m*n)).				.	.. (4)
	
PROPOSITION 

Let r >= 0 be a real number. The sequence of rational numbers a(r,n) defined by

	a(r,n) = f(30*r*n)!*f(r*n)!/(f(15*r*n)!*f(10*r*n)!*f(6*r*n)!)

takes only integer values.

PROOF

The result is clearly true when r = 0, so from now on we assume r > 0. The approach to
integrality is the same as above: we show that ord_p(a(r,n)), the power to which a prime p
appears in a(r,n), is nonnegative for all p.

We first establish this for the case when r is a rational number

		r = c/d, 	(c, d  positive integers).

By Legendre's theorem, ord_p(a(c/d,n)) is given by the sum over k of the expressions

	f(f(30*c*n/d)/p^k) + f(f(c*n/d)/p^k)

	- f(f(15*c*n/d)/p^k) - f(f(10*c*n/d)/p^k) - f(f(6*c*n/d)/p^k).

By means of (4) this simplifies to the sum over k of

	f(30*c*n/(d*p^k)) + f(c*n/(d*p^k))

	- f(15*c*n)/(d*p^k)) - f(10*c*n)/(d*p^k)) - f(6*c*n)/(d*p^k))

and for each k the expression is nonnegative by the above Lemma.

Finally, to deal with the case when r is irrational let {r_k}k>=0 be a sequence of positive rational
numbers tending to r

			lim {k -> inf} r_k = r.

For a fixed nonnegative integer n, a(r,n), qua function of r, is a piecewise constant function
on [0,inf) having step discontinuities at a discrete set of rational points. Hence for irrational
values of r

		a(r,n) = lim {k -> inf} a(r_k,n)

is a limit of a sequence of integers and so must also be an integer.

END PROOF

The particular case of the proposition when r = 1/30 is listed in the database as A211418.