A078482 -id:A078482 - cp's OEIS frontend

A272686 Second differences of A078482.

0, 3, 10, 36, 134, 510, 1976, 7770, 30934, 124456, 505254, 2067250, 8516028, 35292978, 147045490, 615572172, 2587970166, 10922249958, 46257477232, 196532215226, 837432161710, 3577882539792, 15323984114822, 65781749593002, 282979540332660

Offset: 0

N. J. A. Sloane, May 24 2016

nonn

Cf. A078482, A272687.

A272687 First differences of A078482.

Original entry on oeis.org

1, 1, 4, 14, 50, 184, 694, 2670, 10440, 41374, 165830, 671084, 2738334, 11254362, 46547340, 193592830, 809165002, 3397135168, 14319385126, 60576862358, 257109077584, 1094541239294, 4672423779086, 19996407893908, 85778157486910, 368757697819570, 1588465839532628, 6855304750273902

Offset: 0

N. J. A. Sloane, May 24 2016

nonn

Cf. A078482, A272686 (second differences).

Differences[CoefficientList[Series[(1-3 x+x^2-Sqrt[1-6 x+7 x^2-2 x^3+x^4])/(2 x),{x,0,40}],x]] (* Harvey P. Dale, Jun 08 2024 *)

A384685 Triangle read by rows: T(n,k) is the number of rooted ordered trees with node weights summing to n, where the root has weight 0, all internal nodes have weight 1, and leaf nodes have weights in {1,...,k}.

Original entry on oeis.org

1, 0, 1, 0, 2, 3, 0, 5, 8, 9, 0, 14, 25, 28, 29, 0, 42, 83, 95, 98, 99, 0, 132, 289, 337, 349, 352, 353, 0, 429, 1041, 1236, 1285, 1297, 1300, 1301, 0, 1430, 3847, 4652, 4854, 4903, 4915, 4918, 4919, 0, 4862, 14504, 17865, 18709, 18912, 18961, 18973, 18976, 18977

Offset: 0

John Tyler Rascoe, Jun 06 2025

			Triangle begins:
    k=0     1     2     3     4     5     6     7      8
 n=0 [1]
 n=1 [0,    1]
 n=2 [0,    2,    3]
 n=3 [0,    5,    8,    9]
 n=4 [0,   14,   25,   28,   29]
 n=5 [0,   42,   83,   95,   98,   99]
 n=6 [0,  132,  289,  337,  349,  352,  353]
 n=7 [0,  429, 1041, 1236, 1285, 1297, 1300, 1301]
 n=8 [0, 1430, 3847, 4652, 4854, 4903, 4915, 4918, 4919]
...
T(2,2) = 3 counts:
  o    o      o
  |    |     / \
 (2)  (1)  (1) (1)
       |
      (1)

Cf. (column k=1) A000108, A078481, A078482, A088218, (column k=2) A143330, A380761, A384613.

b(k) = {(x^2-x^(k+1))/(1-x)}
P(N,k) = {my(x='x+O('x^N)); Vec((1-b(k)-sqrt((b(k)-1)^2-4*x))/(2*x))}
T(max_row) = { my( N = max_row+1, v = vector(N, i, if(i==1,1,0))~); for(k=1,N, v=matconcat([v,P(N+1,k)~])); vector(N,n, vector(n,k,v[n,k]))}

G.f. of column k is (1 - b(k,x) - sqrt((b(k,x) - 1)^2 - 4*x))/(2*x) where b(k,x) = (x^2 - x^(k + 1))/(1 - x).

T(n,k) = T(n,n) for k > n.

A363809 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, and 2-1-3-5-4.

Original entry on oeis.org

1, 1, 2, 6, 22, 89, 378, 1647, 7286, 32574, 146866, 667088, 3050619, 14039075, 64992280, 302546718, 1415691181, 6656285609, 31436228056, 149079962872, 709680131574, 3390269807364, 16248661836019, 78109838535141, 376531187219762, 1819760165454501

Offset: 0

Andrei Asinowski, Jun 23 2023

nonn

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-3-5-4.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric pattern "7". See the Merino and Mütze reference, Table 3, entry "12347".

Andrei Asinowski and Cyril Banderier. Geometry meets generating functions: Rectangulations and permutations (2023).

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A078482, A033321, A363810, A363811, A363812, A363813, A006012.

The generating function F=F(x) satisfies the equation x^4*(x - 2)^2*F^4 + x*(x - 2)*(4*x^3 - 7*x^2 + 6*x - 1)*F^3 + (2*x^4 - x^3 - 2*x^2 + 5*x - 1)*F^2 - (4*x^3 - 7*x^2 + 6*x - 1)*F + x^2 = 0.

A363810 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-14-3, and 4-5-3-1-2.

Original entry on oeis.org

1, 1, 2, 6, 21, 79, 306, 1196, 4681, 18308, 71564, 279820, 1095533, 4298463, 16913428, 66769536, 264526329, 1051845461, 4197832133, 16813161765, 67571221016, 272448598737, 1101876945673, 4469106749281, 18174503562880, 74093063050412, 302753929958872

Offset: 0

Andrei Asinowski, Jun 23 2023

nonn

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-14-3 and 2-1-3-5-4.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "5" and "8". See the Merino and Mütze reference, Table 3, entry "123458".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363811, A363812, A363813, A006012.

with(gfun): seq(coeff(algeqtoseries(x^8*(-2+x)^2*F^4 - x^3*(x-1)*(-2+x)*(x^5-7*x^4+4*x^3-6*x^2+5*x-1)*F^3 - x*(x-1)*(4*x^7-22*x^6+37*x^5-42*x^4+53*x^3-35*x^2+10*x-1)*F^2 - (5*x^6-16*x^5+15*x^4-28*x^3+23*x^2-8*x+1)*(x-1)^2*F - (2*x^5-5*x^4+4*x^3-10*x^2+6*x-1)*(x-1)^2, x, F, 32, true)[1], x, n+1), n = 0..30); # Vaclav Kotesovec, Jun 24 2023

The generating function F=F(x) satisfies the equation x^8*(x - 2)^2*F^4 - x^3*(x - 1)*(x - 2)*(x^5 - 7*x^4 + 4*x^3 - 6*x^2 + 5*x - 1)*F^3 - x*(x - 1)*(4*x^7 - 22*x^6 + 37*x^5 - 42*x^4 + 53*x^3 - 35*x^2 + 10*x - 1)*F^2 - (5*x^6 - 16*x^5 + 15*x^4 - 28*x^3 + 23*x^2 - 8*x + 1)*(x - 1)^2*F - (2*x^5 - 5*x^4 + 4*x^3 - 10*x^2 + 6*x - 1)*(x - 1)^2 = 0.

A363811 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-3-5-4, and 4-5-3-1-2.

Original entry on oeis.org

1, 1, 2, 6, 22, 88, 362, 1488, 6034, 24024, 93830, 359824, 1357088, 5043260, 18501562, 67120024, 241169322, 859450004, 3041415520, 10699090888, 37448249502, 130518538696, 453276141238, 1569476495000, 5420784841936, 18683861676756, 64286814548706

Offset: 0

Andrei Asinowski, Jun 23 2023

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-3-5-4 and 4-5-3-1-2.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "7" and "8". See the Merino and Mütze reference, Table 3, entry "123478".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (18,-141,630,-1767,3224,-3834,2896,-1312,320,-32).

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363810, A363812, A363813, A006012.

CoefficientList[Series[(1 - x)*(1 - 16*x + 109*x^2 - 410*x^3 + 923*x^4 - 1256*x^5 + 988*x^6 - 400*x^7 + 66*x^8 - 2*x^9)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2*(1 - 2*x)^4),{x,0,26}],x] (* Stefano Spezia, Jun 24 2023 *)

G.f.: (1 - x)*(1 - 16*x + 109*x^2 - 410*x^3 + 923*x^4 - 1256*x^5 + 988*x^6 - 400*x^7 + 66*x^8 - 2*x^9)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2*(1 - 2*x)^4).

A363812 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 3-41-2.

Original entry on oeis.org

1, 1, 2, 6, 20, 69, 243, 870, 3159, 11611, 43130, 161691, 611065, 2325739, 8907360, 34304298, 132770564, 516164832, 2014739748, 7892775473, 31022627947, 122304167437, 483513636064, 1916394053725, 7613498804405, 30313164090695

Offset: 0

Andrei Asinowski, Jun 23 2023

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-4-3 and 3-41-2.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "5", "6", "7". See the Merino and Mütze reference, Table 3, entry "1234567".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363810, A363811, A363813, A006012.

CoefficientList[Series[(1 - 3*x + 3*x^2 - Sqrt[1 - 6*x + 7*x^2 + 2*x^3 + x^4])/(2*x^2*(2 - x)),{x,0,25}],x] (* Stefano Spezia, Jun 24 2023 *)

G.f.: (1 - 3*x + 3*x^2 - sqrt(1 - 6*x + 7*x^2 + 2*x^3 + x^4))/(2*x^2*(2 - x)).

A363813 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 4-5-3-1-2.

Original entry on oeis.org

1, 1, 2, 6, 21, 78, 295, 1114, 4166, 15390, 56167, 202738, 724813, 2570276, 9052494, 31702340, 110503497, 383691578, 1328039043, 4584708230, 15793983638, 54315199642, 186526735307, 639831906594, 2192754259993, 7509139583560, 25699765092254, 87913948206096

Offset: 0

Andrei Asinowski, Jun 23 2023

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-1-4-3 and 4-5-3-1-2.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "5", "7", "8". See the Merino and Mütze reference, Table 3, entry "1234578".

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (10,-37,62,-47,16,-2).

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363810, A363811, A363812, A006012.

CoefficientList[Series[(1 - 9*x + 29*x^2 - 39*x^3 + 20*x^4 - 3*x^5)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2),{x,0,27}],x] (* Stefano Spezia, Jun 24 2023 *)

G.f.: (1 - 9*x + 29*x^2 - 39*x^3 + 20*x^4 - 3*x^5)/((1 - 4*x + 2*x^2)*(1 - 3*x + x^2)^2).

A078483 G.f.: -2x/(1 - 5x - sqrt(1-4x) + xsqrt(1-4x) + 2x^2).

Original entry on oeis.org

1, 1, 2, 6, 20, 69, 243, 869, 3145, 11491, 42312, 156807, 584288, 2187298, 8221257, 31009841, 117331070, 445174418, 1693270531, 6454992143, 24657428519, 94363587324, 361741068087, 1388892123038, 5340282880156, 20560742443041, 79259430563491, 305889059254747

Offset: 0

N. J. A. Sloane, Jan 04 2003

nonn

Number of data structures of a certain wreath product type.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Preprint, 2002.
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.

Cf. A006318, A078482.

catGF = (1 - Sqrt[1 - 4 x])/(2 x); CoefficientList[Normal[Series[1/(1 - (x + x^2 catGF^3)), {x, 0, 20}]], x] (* David Callan, Feb 06 2016 *)
CoefficientList[Series[-2 x / (1 - 5 x - Sqrt[1 - 4 x] + x Sqrt[1 - 4 x] + 2 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, May 28 2016 *)

a(n):=sum(m*sum(((sum(binomial(j,-2*m-k+2*j)*binomial(m+k,j),j,0,m+k))*binomial(n-m-1,k-1))/(m+k),k,1,n-m),m,1,n)+1; /* Vladimir Kruchinin, Oct 11 2011 */

From Gary W. Adamson, Jul 14 2011: (Start)
a(n) is the upper left term in M^n, where M is the following infinite square production matrix:
  1, 1, 0, 0, 0, 0, ...
  1, 2, 1, 0, 0, 0, ...
  1, 1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, 1, ...
  ... (End)
a(n) = 1 + Sum_{m=1..n} m*Sum_{k=1..n-m} (1/(m+k)) * ((Sum_{j=0..m+k} binomial(j,-2*m-k+2*j)*binomial(m+k,j))*binomial(n-m-1,k-1)). - Vladimir Kruchinin, Oct 11 2011
G.f.: 1/(1 - (x + x^2 * C(x)^3)) where C(x) = (1-sqrt(1-4*x))/(2*x) is the g.f. for the Catalan numbers A000108. - David Callan, Feb 06 2016
a(n) ~ 3 * 2^(2*n + 2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Jul 20 2019
D-finite with recurrence: n*a(n) +2*(-5*n+4)*a(n-1) +3*(11*n-18)*a(n-2) +(-41*n+102)*a(n-3) +(21*n-64)*a(n-4) +2*(-2*n+7)*a(n-5)=0. - R. J. Mathar, Jan 23 2020

Replaced definition with g.f. given by Atkinson and Still (2002). - N. J. A. Sloane, May 24 2016

A348351 Number of permutations of [n] avoiding the patterns 2-41-3, 3-14-2, 2-14-3, and 3-41-2.

Original entry on oeis.org

1, 1, 2, 6, 20, 72, 274, 1088, 4470, 18884, 81652, 360054, 1614618, 7346688, 33856008, 157777908, 742637416

Offset: 0

Manfred Scheucher, Oct 20 2021

Also the number of one-sided rectangulations.

L. J. Leifheit, Combinatorial Properties of Rectangulations, Master's thesis, Technische Universität Berlin, 2021.

A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, and R. Y. Pinter, Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations, Electronic Journal of Combinatorics 20(2), 2013.
Andrei Asinowski, Jean Cardinal, Stefan Felsner, and Éric Fusy, Combinatorics of rectangulations: Old and new bijections, arXiv:2402.01483 [math.CO], 2023. See p. 30.
D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek, Area-Universal Rectangular Layouts, arXiv:0901.3924 [cs.CG], 2009.
A. Merino and T. Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Manfred Scheucher, L.J. Leifheit's python program for enumeration.
The Combinatorial Object Server, Rectangulation Generator.

Cf. A001181, A006318, A078482.

Name corrected by Manfred Scheucher, May 24 2023

a(0)=1 prepended by Alois P. Heinz, Feb 05 2024

cp's OEIS Frontend

A272686 Second differences of A078482.

Views

Author

Keywords

Crossrefs

A272687 First differences of A078482.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A384685 Triangle read by rows: T(n,k) is the number of rooted ordered trees with node weights summing to n, where the root has weight 0, all internal nodes have weight 1, and leaf nodes have weights in {1,...,k}.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A363809 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, and 2-1-3-5-4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A363810 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-14-3, and 4-5-3-1-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A363811 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-3-5-4, and 4-5-3-1-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A363812 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 3-41-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A363813 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-1-4-3, and 4-5-3-1-2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A078483 G.f.: -2*x/(1 - 5*x - sqrt(1-4*x) + x*sqrt(1-4*x) + 2*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A078483 G.f.: -2x/(1 - 5x - sqrt(1-4x) + xsqrt(1-4x) + 2x^2).