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

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

Column k=3 of A237018.

Sequence in context: A047731 A291841 A322139 * A369012 A060909 A074545

Adjacent sequences: A236339 A236340 A236341 * A236343 A236344 A236345

Keyword

easy,nonn

Author

Murray R. Bremner, Jan 22 2014

Status

approved