A236342 Association types in 3-dimensional algebra.

1, 3, 18, 132, 1080, 9450, 86544, 819154, 7949532, 78671736, 790930728, 8055355698, 82935309996, 861772240368, 9025745922656, 95183320362093, 1009853631571878, 10771405762277094, 115438084007465376, 1242437345193084264, 13423511539998223884

Offset: 1

Author

Murray R. Bremner, Jan 22 2014

Keywords

• easy
• nonn

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

Crossrefs

Cf. A000108 (for 1-dimensional algebra), A236339 (for 2-dimensional algebra).

Column k=3 of A237018.

Programs

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

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