A322543 Number of triadic partitions of the unit square into (2n+1) subrectangles.

1, 2, 12, 96, 879, 8712, 90972, 985728, 10979577, 124937892, 1446119664, 16972881120, 201526230555, 2416309004872, 29215072931136, 355800894005760, 4360705642282569, 53744080256387478, 665667989498682936, 8281518339078928800, 103441301833577854041, 1296713265300164761632

Offset: 0

Author

Yu Hin Au, Dec 14 2018

Keywords

• nonn

Comments

A kind of two-dimensional ternary Catalan number. This sequence enumerates the decompositions of the unit square into 2n+1 rectangles obtained by the following algorithm.

(a) Start with the unit square.

(b) Perform the following operation n times:

(1) Choose a rectangle in the current decomposition.

(2) Trisect this rectangle into three rectangles horizontally or vertically.

Note that different sequences of trisections can produce the same decomposition.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..889
• 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.

Crossrefs

Cf. A000108 (Catalan numbers), A005408, A236339 (decompositions of unit square using bisections).

Programs

Maple

a:= n-> coeff(series(RootOf(G^9-2*G^3+G-x, G), x, 2*n+2), x, 2*n+1):
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 14 2018

Mathematica

a[n_] := SeriesCoefficient[InverseSeries[x - 2 x^3 + x^9 + O[x]^(2n+2), x], {x, 0, 2n+1}];
Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Aug 13 2019, from PARI *)

PARI

a(n)={polcoef(serreverse(x - 2*x^3 + x^9 + O(x^(2*n+2))), 2*n+1)} \\ Andrew Howroyd, Dec 14 2018

Formula

Recurrence relation: a(n) = C(2n+1) with C(1) = 1 and C(n) = 2 Sum_{i1,i2,i3} C(i1)C(i2)C(i3) - Sum_{i1,i2,i3,i4,i5,i6,i7,i8,i9} C(i1)C(i2)C(i3)C(i4)C(i5)C(i6)C(i7)C(i8)C(i9). The first sum is over all 3-compositions of n into positive integers (i1+i2+i3=n), and the second sum is over all 9-compositions of n into positive integers (i1+i2+...+i9=n).

a(n) = [x^(2n+1)] G(x), where G(x) satisfies: G(x)^9 - 2*G(x)^3 + G(x) - x = 0.