A063074 Number of partitions of 2n^2 whose Ferrers-plot fits within a 2n X 2n box; number of ways to cut a 2n X 2n chessboard into two equal-area pieces along a non-descending line from lower left to upper right.

1, 2, 8, 58, 526, 5448, 61108, 723354, 8908546, 113093022, 1470597342, 19499227828, 262754984020, 3589093760726, 49596793134484, 692260288169282, 9747120868919060, 138298900243896166, 1975688102624819336, 28396056820503468894, 410363630540693436398

Offset

0,2

Comments

Also the number of subsets of {1,...,4n} containing exactly 2n elements with total sum n*(4n+1) (see also A060468 for a related sequence). This is of course the same as the number of partitions of n*(4n+1) having 2n distinct parts of length at most 4n. This number is the coefficient of t^0 q^0 in the product('(t*q^k+1/(t*q^k)','k'=1..4*n). - Roland Bacher, May 02 2002

A bijection with a dissection as above of the 2n X 2n checkerboard is given by subtracting 1,2,3,...,2n of the smallest, second-smallest, etc. element in the subset. Example for n=2: {1,2,7,8} (yields the checkerboard partition {1-1,2-2,7-3,8-4}={0,0,4,4}), {1,3,6,8} (yields {1-1,3-2,6-3,8-4}={0,1,3,4}), {1,4,5,8} (yields {0,2,2,4}), {1,4,6,7} (yields {0,2,3,3}), {3,4,5,6} (yields {2,2,2,2}), {2,4,5,7} (yields {1,2,2,3}), {2,3,6,7} (yields {1,1,3,3}), {2,3,5,8} (yields {1,1,2,4}).

Appears to be the number of random walks of length 4n, moves +/-1, starting and ending at 0 and with signed area 0 under the path. It would be nice to have a lower bound of the form a(n) > c*2^{4n}/n^d. - David_Mumford(AT)brown.edu, Jun 25 2003

Links

Alois P. Heinz, Table of n, a(n) for n = 0..100

H. Prodinger, On the number of partitions of 1...n into two sets of equal cardinalities and equal sums, Canad. Math. Bull. 25(1982), pp. 238-241.

Formula

a(n) = A029895(2n) = A067059(2n, 2n) = A107110(2n, 2n^2). a(n) seems to be close to (sqrt(75)/Pi)*16^n/(20n^2+6n+1). - Henry Bottomley, May 12 2005

Example

For a 4 X 4 board (n=2) the 8 partitions are (4,4,0,0), (4,3,1,0), (4,2,1,1), (4,2,2,0), (3,3,2,0), (3,3,1,1), (3,2,2,1), (2,2,2,2).

Maple

b:= proc(n, i, t) option remember;
      `if`(i<t or n<t*(t+1)/2 or n>t*(2*i-t+1)/2, 0,
      `if`(n=0, 1, b(n, i-1, t) +`if`(n<i, 0, b(n-i, i-1, t-1))))
    end:
a:= n-> b(n*(4*n+1), 4*n, 2*n):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 18 2012

Mathematica

Table[ Length@Select[ IntegerPartitions[ 2n^2 ], Length[ # ] <= 2n && First[ # ] <= 2n& ], {n, 1, 5} ] or faster: Table[ T[ 2n^2, 2n, 2n ], {n, 0, 24} ] with T[ m, a, b ] as defined in A047993.
(* second program: *)
b[n_, i_, t_] := b[n, i, t] =  If[i < t || n < t (t + 1)/2 || n > t (2i - t + 1)/2, 0, If[n == 0, 1, b[n, i - 1, t] + If[n < i, 0, b[n - i, i - 1, t - 1]]]]; a[n_] := b[n (4n + 1), 4n, 2n]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 29 2016, after Alois P. Heinz *)

Crossrefs

Cf. A047993, A063075.

Bisection of row n=2 of A204459. - Alois P. Heinz, Jan 18 2012

Sequence in context: A027257 A308352 A185898 * A319590 A005804 A162067

Adjacent sequences: A063071 A063072 A063073 * A063075 A063076 A063077

Keyword

nonn

Author

Wouter Meeussen, Aug 03 2001

Extensions

More terms from Alois P. Heinz, Jan 18 2012

Status

approved