A237018 Number A(n,k) of partitions of the k-dimensional hypercube resulting from a sequence of n bisections, each of which splits any part perpendicular to any of the axes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 8, 5, 0, 1, 4, 18, 39, 14, 0, 1, 5, 32, 132, 212, 42, 0, 1, 6, 50, 314, 1080, 1232, 132, 0, 1, 7, 72, 615, 3440, 9450, 7492, 429, 0, 1, 8, 98, 1065, 8450, 40320, 86544, 47082, 1430, 0, 1, 9, 128, 1694, 17604, 124250, 494736, 819154, 303336, 4862, 0

Offset: 0

Author

Alois P. Heinz, Feb 02 2014

Keywords

• nonn
• tabl

Comments

The g.f. given below is a generalization of formulas given by Murray R. Bremner and Sara Madariaga in A236339 and A236342. According to them A(n,k) also gives the number of distinct monomials of degree n+1 in the universal algebra with k nonassociative binary products {*1,...,*k} related only by the interchange laws from k-category theory: (a *i b) *j (c *i d) = (a *j c) *i (b *j d) for i,j in {1,...,k} and i

These numbers can be regarded as (one of many possible definitions of) higher-dimensional Catalan numbers. - N. J. A. Sloane, Feb 12 2014

Examples

			A(3,1) = 5:
  [||-|---], [-|||---], [-|-|-|-], [---|||-], [---|-||].
  .
A(2,2) = 8:
  ._______.  ._______.  ._______.  ._______.
  | | |   |  |   | | |  |_______|  |       |
  | | |   |  |   | | |  |_______|  |_______|
  | | |   |  |   | | |  |       |  |_______|
  |_|_|___|  |___|_|_|  |_______|  |_______|
  ._______.  ._______.  ._______.  ._______.
  |   |   |  |   |   |  |   |   |  |       |
  |___|   |  |   |___|  |___|___|  |_______|
  |   |   |  |   |   |  |       |  |   |   |
  |___|___|  |___|___|  |_______|  |___|___|.
  .
Square array A(n,k) begins:
  1,   1,    1,     1,      1,       1,       1, ...
  0,   1,    2,     3,      4,       5,       6, ...
  0,   2,    8,    18,     32,      50,      72, ...
  0,   5,   39,   132,    314,     615,    1065, ...
  0,  14,  212,  1080,   3440,    8450,   17604, ...
  0,  42, 1232,  9450,  40320,  124250,  311472, ...
  0, 132, 7492, 86544, 494736, 1912900, 5770692, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• Yu Hin (Gary) Au, Fatemeh Bagherzadeh, Murray R. Bremner, Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube, arXiv:1903.00813 [math.CO], Mar 03 2019, p. 8.

Crossrefs

Columns k=0-10 give: A000007, A000108, A236339(n+1), A236342(n+1), A237019, A237020, A237021, A237022, A237023, A237024, A237025.

Rows n=0-2 give: A000012, A001477, A001105.

Main diagonal gives A237026.

Cf. A255982.

Programs

Maple

A:= (n, k)-> coeff(series(RootOf(x*(-1)^k=add((-1)^i*
    binomial(k, i)*(G*x)^(2^(k-i)), i=0..k), G), x, n+1), x, n):
seq(seq(A(n, d-n), n=0..d), d=0..10);
# second Maple program:
b:= proc(n, k, t) option remember; `if`(t=0, 1, `if`(t=1,
       A(n-1, k), add(A(j, k)*b(n-j-1, k, t-1), j=0..n-2)))
    end:
A:= proc(n, k) option remember; `if`(n=0, 1,
      -add(binomial(k, j)*(-1)^j*b(n+1, k, 2^j), j=1..k))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

b[n_, k_, t_] := b[n, k, t] = If[t == 0, 1, If[t == 1, A[n-1, k], Sum[A[j, k]*b[n-j-1, k, t-1], {j, 0, n-2}]]]; A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[ Binomial[k, j]*(-1)^j*b[n+1, k, 2^j], {j, 1, k}]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Jan 19 2015, after Alois P. Heinz *)

Formula

G.f. G_k of column k satisfies: (-1)^k*x = Sum_{i=0..k} (-1)^i*C(k,i)*(G_k*x)^(2^(k-i)).

A(n,k) = Sum_{i=0..k} C(k,i) * A255982(n,i). - Alois P. Heinz, Mar 13 2015

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.