A236339 Association types in 2-dimensional algebra.

1, 2, 8, 39, 212, 1232, 7492, 47082, 303336, 1992826, 13299624, 89912992, 614474252, 4238138216, 29463047072, 206234876287, 1452319244772, 10281935334928, 73138728191724, 522475643860940, 3746698673538480, 26961197787989220, 194626504416928080

Offset: 1

Author

Murray R. Bremner, Jan 22 2014

Keywords

• easy
• nonn
• nice

Comments

A kind of two-dimensional Catalan number.

This sequence has two equivalent descriptions:

(1) This sequence enumerates the number of decompositions of the unit square into n rectangles obtained by the following algorithm.

(a) Start with the unit square.

(b) Perform the following operation n-1 times:

Choose a rectangle in the current decomposition.

Bisect this rectangle into two rectangles horizontally or vertically.

Different sequences of bisections can produce the same decomposition.

(2) Consider the universal algebra with two nonassociative binary products *1 and *2 related only by the interchange law from 2-category theory:

( a *1 b ) *2 ( c *1 d ) = ( a *2 c ) *1 ( b *2 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 R. Bremner, Diagrams representing 2-dimensional Catalan numbers for n = 2,3,4,5
• 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.
• Elżbieta Liszewska, Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.

Crossrefs

Cf. A000108 (Catalan numbers), A236342.

Cf. A001002, A046736.

Column k=2 of A237018.

Programs

Maple

c := table():
c[1] := 1:
printf( "\n" ):
for n from 2 to 50 do
c[n] := 0:
for ij in combinat[composition](n,2) do
    c[n] := c[n] + 2*c[ij[1]]*c[ij[2]]
od:
for ijkl in combinat[composition](n,4) do
    c[n] := c[n] - c[ijkl[1]]*c[ijkl[2]]*c[ijkl[3]]*c[ijkl[4]]
od:
   printf( "%2d      %d \n", n, c[n] )
od:
# second Maple program:
a:= proc(n) option remember; `if`(n<3, n, (
      8*(2*n-5)*(148*n-243)*(4*n-13)*(4*n-11)*a(n-3)
      +16*(n-2)*(4736*n^3-31456*n^2+68444*n-48609)*a(n-2)
      -32*(n-1)*(n-2)*(148*n^2-613*n+594)*a(n-1)) /
      (5*n*(n-1)*(n-2)*(148*n-391)))
    end:
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 22 2014

Mathematica

max = 30; c[1] = 1; c[2] = 2; g = Sum[c[k]*x^k, {k, 1, max}]; eq = Take[Thread[CoefficientList[g^4 - 2*g^2 + g - x, x] == 0], max+1]; sol = Solve[eq] // First; Array[c, max] /. sol (* Jean-François Alcover, Jan 27 2014 *)
Rest[CoefficientList[InverseSeries[Series[x^4-2*x^2+x, {x, 0, 20}], x],x]] (* Vaclav Kotesovec, Feb 16 2014 *)

Formula

Recurrence relation:

C(1) = 1,

C(n) = 2 Sum_{i,j} C(i)C(j) - Sum_{i,j,k,l} C(i)C(j)C(k)C(l).

The first sum is over all 2-compositions of n into positive integers (i+j=n), and the second sum is over all 4-compositions of n into positive integers (i+j+k+l=n).

Generating function G(x) = Sum_{n>=1} C(n) x^n satisfies a quartic polynomial equation: G(x)^4 - 2*G(x)^2 + G(x) - x = 0.

a(n) ~ (1/r)^(n-1/2) / (2 * sqrt(2*Pi*(1-3*s^2)) * n^(3/2)), where s = 0.2695944364054445582... is the root of the equation 4*s*(1-s^2) = 1, and r = s*(1-2*s+s^3) = 0.1295146671633141285... - Vaclav Kotesovec, Feb 16 2014

From Seiichi Manyama, Jan 10 2023: (Start)

G.f.: Series_Reversion( x * (1-x) * (1-x-x^2) ).

a(n+1) = (1/(n+1)) * Sum_{k=0..floor(n/2)} binomial(n+k,k) * binomial(3*n-k+1,n-2*k). (End)

Extensions

a(17)-a(23) from Alois P. Heinz, Jan 22 2014