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
a(n) ~ sqrt(11*sqrt(2) - 16 + sqrt(16*sqrt(2) - 22)) * 2^(n - 1/2) / (sqrt(Pi) * n^(3/2) * (1 - sqrt(8*sqrt(2) - 11))^(n+1)). - Vaclav Kotesovec, May 17 2024
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
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