OFFSET
1,2
COMMENTS
This sequence has two equivalent descriptions:
(1) It enumerates the number of decompositions of the unit cube into n rectangular parallelepipeds obtained by the following algorithm.
(a) Start with the unit cube.
(b) Perform the following operation n-1 times: Choose a parallelepiped in the current decomposition. Bisect this parallelepiped into two parallelepipeds by a plane orthogonal to any of the 3 coordinate axes. Different sequences of bisections can produce the same decomposition.
(2) Consider the universal algebra with three nonassociative binary products *1, *2, *3 related only by the three interchange laws from 2-category theory, as follows where (i,j) = (1,2), (1,3), (2,3):
( a *i b ) *j ( c *i d ) = ( a *j c ) *i ( b *i d )
This sequence enumerates the number of distinct monomials of degree n.
REFERENCES
J.-L. Loday and B. Vallette, Algebraic Operads, Grundlehren 346, Springer, 2012, section 13.10.4, page 544 (for the interchange law).
S. Mac Lane, Categories for the Working Mathematician, second edition, Springer, 1978, equation (5), page 43 (also for the interchange law).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..400
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.
Murray Bremner, Sara Madariaga, Permutation of elements in double semigroups, arXiv:1405.2889 [math.RA], 2014-2015.
Murray Bremner, Sara Madariaga, Permutation of elements in double semigroups, Semigroup Forum 92 (2016), no. 2, 335--360. MR3472020.
Wikipedia, Parallelepiped
FORMULA
Recurrence relation:
C(1) = 1,
C(n) = 3 sum_{i1,i2} C(i1)C(i2)
- 3 sum_{i1,i2,i3,i4} C(i1)C(i2)C(i3)C(i4)
+ sum_{i1,i2,i3,i4,i5,i6,i7,i8} C(i1)C(i2)C(i3)C(i4)C(i5)C(i6)C(i7)C(i8).
The first sum is over all 2-compositions of n into positive integers, the second sum is over all 4-compositions, and the third sum is over all 8-compositions.
This recurrence relation has a natural generalization using inclusion-exclusion to k-dimensional algebras for all k > 0, where k = 1 gives the familiar classical Catalan numbers, but with offset 1 not the usual offset 0; that is, k = 1 has the n-th term 1/n*binomial(2*n-2,n-1) instead of the more familiar 1/(n+1)*binomial(2*n,n) (thanks to Alois P. Heinz for pointing this out).
Generating function: G(x) = sum_{n>=1} C(n)x^n satisfies a polynomial of degree 8: G(x)^8 - 3G(x)^4 + 3G(x)^2 - G(x) + x = 0.
a(n) ~ (1/r)^(n-1/2) / (sqrt(2*Pi*(6-36*s^2+56*s^6)) * n^(3/2)), where s = 0.17792425007438691... is the root of the equation 8*s^7-12*s^3+6*s = 1, and r = s*(7-18*s+12*s^3)/8 = 0.085958633749898... - Vaclav Kotesovec, Feb 16 2014
MAPLE
MAXDEG := 24:
C[ 1 ] := 1:
for n from 2 to MAXDEG do
count := 0:
for k to 3 do
count := count +
( (-1)^(k-1) * binomial(3, k) *
add( mul( C[f], f in e ), e in combinat[composition](n, 2^k) ) )
od:
print( n, count ):
C[ n ] := count
od:
MATHEMATICA
Rest[CoefficientList[InverseSeries[Series[-x^8+3*x^4-3*x^2+x, {x, 0, 20}], x], x]] (* Vaclav Kotesovec, Feb 16 2014 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Murray R. Bremner, Jan 22 2014
STATUS
approved