login
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.
12

%I #53 Mar 11 2019 06:44:50

%S 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,

%T 50,314,1080,1232,132,0,1,7,72,615,3440,9450,7492,429,0,1,8,98,1065,

%U 8450,40320,86544,47082,1430,0,1,9,128,1694,17604,124250,494736,819154,303336,4862,0

%N 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.

%C 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.

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

%H Alois P. Heinz, <a href="/A237018/b237018.txt">Antidiagonals n = 0..140, flattened</a>

%H Yu Hin (Gary) Au, Fatemeh Bagherzadeh, Murray R. Bremner, <a href="https://arxiv.org/abs/1903.00813">Enumeration and Asymptotic Formulas for Rectangular Partitions of the Hypercube</a>, arXiv:1903.00813 [math.CO], Mar 03 2019, p. 8.

%F 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)).

%F A(n,k) = Sum_{i=0..k} C(k,i) * A255982(n,i). - _Alois P. Heinz_, Mar 13 2015

%e A(3,1) = 5:

%e [||-|---], [-|||---], [-|-|-|-], [---|||-], [---|-||].

%e .

%e A(2,2) = 8:

%e ._______. ._______. ._______. ._______.

%e | | | | | | | | |_______| | |

%e | | | | | | | | |_______| |_______|

%e | | | | | | | | | | |_______|

%e |_|_|___| |___|_|_| |_______| |_______|

%e ._______. ._______. ._______. ._______.

%e | | | | | | | | | | |

%e |___| | | |___| |___|___| |_______|

%e | | | | | | | | | | |

%e |___|___| |___|___| |_______| |___|___|.

%e .

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 2, 3, 4, 5, 6, ...

%e 0, 2, 8, 18, 32, 50, 72, ...

%e 0, 5, 39, 132, 314, 615, 1065, ...

%e 0, 14, 212, 1080, 3440, 8450, 17604, ...

%e 0, 42, 1232, 9450, 40320, 124250, 311472, ...

%e 0, 132, 7492, 86544, 494736, 1912900, 5770692, ...

%p A:= (n, k)-> coeff(series(RootOf(x*(-1)^k=add((-1)^i*

%p binomial(k, i)*(G*x)^(2^(k-i)), i=0..k), G), x, n+1), x, n):

%p seq(seq(A(n, d-n), n=0..d), d=0..10);

%p # second Maple program:

%p b:= proc(n, k, t) option remember; `if`(t=0, 1, `if`(t=1,

%p A(n-1, k), add(A(j, k)*b(n-j-1, k, t-1), j=0..n-2)))

%p end:

%p A:= proc(n, k) option remember; `if`(n=0, 1,

%p -add(binomial(k, j)*(-1)^j*b(n+1, k, 2^j), j=1..k))

%p end:

%p seq(seq(A(n, d-n), n=0..d), d=0..10);

%t 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_ *)

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

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

%Y Main diagonal gives A237026.

%Y Cf. A255982.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Feb 02 2014