cp's OEIS Frontend

Roberts states that Gupta and Khare show that a(n) > A002110(n) for 2 < n < 1794 and that a(n) < A002110(n) for n >= 1794, where A002110(n) is the product of the first n primes. - T. D. Noe, Oct 03 2007

This sequence describes the number of ways to arrange n objects in an n X n array (for example, stars in a flag's field pattern). - Tom Young (mcgreg265(AT)msn.com), Jun 17 2010

It appears that a(n) == n (mod n^3) only if n is 1, an odd prime, the square of an odd prime, or the cube of an odd prime. - Gary Detlefs, Aug 06 2013; corrected by Michel Marcus, May 29 2015

Theorem: binomial(n^2, n)/(n+1) is an integer for n >= 2.

Proof 1 from William J. Keith, May 08 2010:

binomial(n^2, n) * 1/(n+1)

= (n^2)*(n^2-1)*(n^2-2)!/((n^2-n)!*n*(n-1)*(n-2)!) * 1/(n+1)

= n*(n^2-2)!/((n^2-n)!*(n-2)!) = n * binomial(n^2-2,n-2). QED

Proof 2 from Max Alekseyev, May 08 2010:

Recall that the valuation of m! w.r.t. prime p equals the sum floor(m/p^i) over i=1,2,3,...

Moreover, if m=a+b where a and b are nonnegative integers, then floor(m/p^i) - floor(a/p^i) - floor(b/p^i) >= 0.

Let n>1. To prove that binomial(n^2, n)/(n+1) is an integer, it is enough to show that its valuation w.r.t. any prime p is nonnegative.

It is clear that trouble may come only from primes dividing n+1.

Let valuation(n+1,p)=k > 0, i.e., n+1=p^k*m where prime p does not divide m.

Then n = p^k*m - 1, n^2 = p^(2k)*m^2 - 2*p^k*m + 1 and n^2 - n = p^(2k)*m^2 - 3*p^k*m + 2.

It is easy to check that floor(n^2/p^i) - floor(n/p^i) - floor((n^2-n)/p^i) = 1 for i=1,2,...,k if p>2 and for i=2,3,...,k+1 if p=2, implying that valuation(binomial(n^2, n)/(n+1),p) >= 0. QED

n divides binomial(n^2,n+1).

Proof 1 :(n+1)*binomial(n^2,n+1) = n*(n-1)*binomial(n^2,n) => n divide binomial(n^2,n+1) because gcd(n,n+1) = 1.

Proof 2 : a(n) = binomial(n^2,n+1)/n = (n-1)*binomial(n^2-2,n-1)=> a(n) is an integer. - Michel Lagneau, May 13 2010