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

0, 1, 2, 6, 20, 70, 254, 948, 3618, 14058, 55432, 221262, 892346, 3630680, 14885042, 61432382, 255025212, 1064190214, 4461325382, 18780710508, 79357572866, 336466650450, 1431007889744, 6103431668830, 26099839562738, 111877997049648, 480635694869218

Offset

0,3

Comments

Number of data structures of a certain wreath product type.

a(n) is also the number of (2-14-3, 3-41-2, 2-4-1-3, 3-1-4-2)-avoiding permutations. - Mireille Bousquet-Mélou, Jul 13 2012

Number of permutations that are separable by a point. And also the number of rectangulations that are guillotine and one-sided. - Manfred Scheucher, May 24 2023

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.

Andrei Asinowski, Gill Barequet, Mireille Bousquet-Mélou, Toufik Mansour, and Ron Y. Pinter, Orders induced by segments in floorplan partitions and (2-14-3, 3-41-2)-avoiding permutations arXiv:1011.1889 [math.CO], 2010-2012, page 32.

Andrei Asinowski and Toufik Mansour, Separable d-Permutations and Guillotine Partitions, arXiv 0803.3414 [math.CO], 2008. Annals of Combinatorics 14 (1) pp.17-43 Springer, 2010; Abstract

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.

Christian Bean, Émile Nadeau, and Henning Ulfarsson, Enumeration of Permutation Classes and Weighted Labelled Independent Sets, arXiv:1912.07503 [math.CO], 2019.

CombOS - Combinatorial Object Server, Generate 1-sided guillotine rectangulations

Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, and Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.

Arturo Merino and Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.

Formula

a(n) = Sum_{m=1..n+1} (C(m,n-m+1)*(sum(i=0..m-1, C(m,i)*C(2*m-i-2,m-1)))* (-1)^(n-m+1))/m), n>0, a(0)=0. - Vladimir Kruchinin, May 21 2011

n*(n+1)*a(n) - 3*n*(2n-1)*a(n-1) + 7*n*(n-2)*a(n-2) - n*(2n-7)*a(n-3) + n*(n-5)*a(n-4) = 0. - R. J. Mathar, Jul 08 2012

G.f. satisfies: A(x) = x*(1 + A(x)) * (1 + A(x)/(1-x)). G.f.: x*exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 / (1-x)^k ). - Paul D. Hanna, Sep 12 2012

Example

G.f.: A(x) = x + 2*x^2 + 6*x^3 + 20*x^4 + 70*x^5 + 254*x^6 + 948*x^7 + ...
From Paul D. Hanna, Sep 12 2012: (Start)
The logarithm of the g.f. begins
log(A(x)/x) = (1 + 1/(1-x))*x + (1 + 2^2/(1-x) + 1/(1-x)^2)*x^2/2 +
(1 + 3^2/(1-x) + 3^2/(1-x)^2 + 1/(1-x)^3)*x^3/3 +
(1 + 4^2/(1-x) + 6^2/(1-x)^2 + 4^2/(1-x)^3 + 1/(1-x)^4)*x^4/4 +
(1 + 5^2/(1-x) + 10^2/(1-x)^2 + 10^2/(1-x)^3 + 5^2/(1-x)^4 + 1/(1-x)^5)*x^5/5 + ...
(End)
a(5) = 70 = (1, 1, 2, 6, 20) dot product (1, 1, 3, 9, 29) = (29 + 9 + 6 + 6 + 20). - Gary W. Adamson, May 20 2013

Mathematica

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] (* Vincenzo Librandi, May 28 2016 *)

Prog

(Maxima) a(n):=if n=0 then 0 else sum((binomial(m, n-m+1)* (sum(binomial(m, i)* binomial(2*m-i-2, m-1), i, 0, m-1)) *(-1)^(n-m+1))/m, m, 1, n+1); /* Vladimir Kruchinin, May 21 2011 */
(PARI) {a(n)=local(A=x); for(i=1, n, A=x*(1+A)*(1+A/(1-x +x*O(x^n)))); polcoeff(A, n)} \\ Paul D. Hanna, Sep 12 2012
(PARI) {a(n)=polcoeff(x*exp(sum(m=1, n+1, x^m/m*sum(k=0, m, binomial(m, k)^2/(1-x +x*O(x^n))^k))), n)} \\ Paul D. Hanna, Sep 12 2012

Crossrefs

Cf. A006318 (separable permutations), A078483.

Sequence in context: A151284 A049138 A095929 * A049128 A192540 A369630

Adjacent sequences: A078479 A078480 A078481 * A078483 A078484 A078485

Keyword

nonn

Author

N. J. A. Sloane, Jan 04 2003

Extensions

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

Status

approved