login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A236339 Association types in 2-dimensional algebra. 10
1, 2, 8, 39, 212, 1232, 7492, 47082, 303336, 1992826, 13299624, 89912992, 614474252, 4238138216, 29463047072, 206234876287, 1452319244772, 10281935334928, 73138728191724, 522475643860940, 3746698673538480, 26961197787989220, 194626504416928080 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,2
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
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.
Elżbieta Liszewska, Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
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)
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 *)
CROSSREFS
Cf. A000108 (Catalan numbers), A236342.
Column k=2 of A237018.
Sequence in context: A162476 A366049 A218321 * A292100 A185650 A059275
KEYWORD
easy,nonn,nice
AUTHOR
Murray R. Bremner, Jan 22 2014
EXTENSIONS
a(17)-a(23) from Alois P. Heinz, Jan 22 2014
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)