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,8

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<j.

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

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.

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

Example

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, ...

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 *)

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.

Sequence in context: A124540 A124550 A306024 * A290605 A292913 A214776

Adjacent sequences: A237015 A237016 A237017 * A237019 A237020 A237021

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 02 2014

Status

approved