|
%I #74 Jun 20 2023 22:28:29
%S 1,1,2,5,14,41,123,374,1147,3538,10958,34042,105997,330632,1032781,
%T 3229714,10109310,31667245,99260192,311294876,976709394,3065676758,
%U 9625674442,30231524869,94972205349,298419158008,937861780439,2947969125284
%N Number of permutations with certain forbidden subsequences.
%C Hankel transform is [1,1,1,...] = A000012. - _Paul Barry_, Jan 19 2009
%C The inverse Motzkin transform apparently yields 1 followed by A000930, which implies a generating function g(x)=1+z/(1-z-z^3) where z=x*A001006(x). - _R. J. Mathar_, Jul 07 2009
%C It appears that the infinite set of interpolated sequences between the Motzkin and the Catalan can be generated with a succession of INVERT transforms, given each sequence has two leading 1's. Also, the N-th sequence in the set starting with (N=1, A001006) can be generated from a production matrix of the form "M" in the formula section, such that the main diagonal is (N leading 1's, 0, 0, 0, ...). M with a diagonal of (1, 0, 0, 0, ...) generates A001006, while M with a main diagonal of all 1's is the production matrix for A000108. - _Gary W. Adamson_, Jul 29 2011
%C From _Gus Wiseman_, Jun 22 2019: (Start)
%C Conjecture: Also the number of non-capturing set partitions of {1..n} (A326254). A set partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting. The a(0) = 1 through a(4) = 14 non-capturing set partitions are:
%C {} {{1}} {{1,2}} {{1,2,3}} {{1,2,3,4}}
%C {{1},{2}} {{1},{2,3}} {{1},{2,3,4}}
%C {{1,2},{3}} {{1,2},{3,4}}
%C {{1,3},{2}} {{1,2,3},{4}}
%C {{1},{2},{3}} {{1,2,4},{3}}
%C {{1,3},{2,4}}
%C {{1,3,4},{2}}
%C {{1},{2},{3,4}}
%C {{1},{2,3},{4}}
%C {{1,2},{3},{4}}
%C {{1},{2,4},{3}}
%C {{1,3},{2},{4}}
%C {{1,4},{2},{3}}
%C {{1},{2},{3},{4}}
%C Cf. A000108, A000110, A058681, A326212, A326237, A326243, A326244, A326249, A326254, A326255.
%C (End)
%H G. C. Greubel, <a href="/A054391/b054391.txt">Table of n, a(n) for n = 0..1000</a>
%H E. Barcucci et al., <a href="http://dx.doi.org/10.1016/S0012-365X(99)00254-X">From Motzkin to Catalan Permutations</a>, Discr. Math., 217 (2000), 33-49.
%H Jean-Luc Baril and Sergey Kirgizov, <a href="https://arxiv.org/abs/2104.01186">Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths</a>, arXiv:2104.01186 [math.CO], 2021.
%H Paul Barry, <a href="http://arxiv.org/abs/1205.2565">On sequences with {-1, 0, 1} Hankel transforms</a>, arXiv preprint arXiv:1205.2565 [math.CO], 2012. - From _N. J. A. Sloane_, Oct 18 2012
%H Petr Gregor, Torsten Mütze, and Namrata, <a href="https://arxiv.org/abs/2306.08420">Combinatorial generation via permutation languages. VI. Binary trees</a>, arXiv:2306.08420 [cs.DM], 2023.
%H Nickolas Hein and Jia Huang, <a href="https://arxiv.org/abs/1807.04623">Variations of the Catalan numbers from some nonassociative binary operations</a>, arXiv:1807.04623 [math.CO], 2018.
%H J. W. Layman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL4/LAYMAN/hankel.html">The Hankel Transform and Some of its Properties</a>, J. Integer Sequences, 4 (2001), #01.1.5
%H Toufik Mansour and Mark Shattuck, <a href="https://digitalcommons.pvamu.edu/aam/vol6/iss2/1">Pattern Avoiding Partitions, Sequence A054391 and the Kernel Method</a>, Applications and Applied Mathematics, Vol. 6, Issue 2 (December 2011), pp. 397-411.
%H T. Mansour and M. Shattuck, <a href="https://web.archive.org/web/20210613072823/http://puma.dimai.unifi.it/22_2/mansour_shattuck.pdf">Restricted partitions and generalized Catalan numbers</a>, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012
%H Eric Marberg, <a href="http://arxiv.org/abs/1203.5738">Crossings and nestings in colored set partitions</a>, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
%F G.f.: 1 - 2*x^2 / (2*x^2 - 3*x + 1 - sqrt(1 - 2*x - 3*x^2)). - Mansour and Shattuck
%F G.f.: 1/(1-x-x^2/(1-2x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-x-x^2/(1-... (continued fraction) (conjecture). - _Paul Barry_, Jan 19 2009
%F From _Gary W. Adamson_, Jul 29 2011: (start)
%F a(n) = upper left term of M^n, a(n+1) = sum of top row terms of M^n; M = an infinite square production matrix as follows with a main diagonal of (1, 1, 1, 0, 0, 0, ...):
%F 1, 1, 0, 0, 0, 0, ...
%F 1, 1, 1, 0, 0, 0, ...
%F 1, 1, 1, 1, 0, 0, ...
%F 1, 1, 1, 0, 1, 0, ...
%F 1, 1, 1, 1, 0, 1, ...
%F 1, 1, 1, 1, 1, 0, ...
%F ... (End)
%F a(n) = Sum_{k=1..n-1} (sum(l=1..k, (binomial(k,l)*l*sum(j=0..n+l-k-1, binomial(j,1-n-2*l+k+2*j)*binomial(n-1+l-k,j)))/(n+l-k-1))) + 1. - _Vladimir Kruchinin_, Oct 31 2011
%F D-finite with recurrence (-n+1)*a(n) + 3*(2*n-3)*a(n-1) + (-8*n+11)*a(n-2) + (-5*n+32)*a(n-3) + (7*n-31)*a(n-4) + 3*(-n+4)*a(n-5)= 0. - _R. J. Mathar_, Nov 26 2012
%F G.f.: 1 - x*(2*x^2-3*x+1 + 1/G(0))/(2*(x^3-3*x^2+4*x-1)), where G(k)= 1 + x*(2+3*x)*(4*k+1)/( 4*k+2 - x*(2+3*x)*(4*k+2)*(4*k+3)/(x*(2+3*x)*(4*k+3) + 4*(k+1)/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Jun 29 2013
%e a(4) = 14, a(5) = 41 since the top row of M^4 = (14, 14, 9, 3, 1), with 41 = (14 + 14 + 9 + 3 + 1).
%p c := x->(1-sqrt(1-4*x))/(2*x); a := (x,j)->(x)/((1-4*x)*(c(x))^2*(1-c(x))^(j))*(-x^2*(c(x))^2*(1-c(x))*(x^2*(c(x))^4)^(j)-(1-3*x-2*x^2)*(c(x))^2*(x*(c(x))^2)^(j)+x);
%p b := (x,j)->1+(1)/((1-4*x)*c(x)*(1-c(x))^(j))*(-2*x^3*(c(x))^2*(x^2*(c(x))^4)^(j)+(1-3*x-2*x^2)*c(x)*(x*(c(x))^2)^(j)-2*x^2);
%p co := (x,j)->(1)/((1-4*x)*(1-c(x))^(j))*(x^2*(x^2*(c(x))^4)^(j)-(1-3*x-2*x^2)*(x*(c(x))^2)^(j)+x^2);
%p s := (x,j)->(1-b(x,j)+(-1)^j*sqrt((1-b(x,j))^2-4*a(x,j)*co(x,j)))/(2*a(x,j)); j := 3; series(s(x,j),x=0..60); od; # j=1,2,3,... inf gives A001006, A005773, A054391, A054392, ..., A000108
%t CoefficientList[Series[1 - 2*x^2/(2*x^2 - 3*x + 1 - Sqrt[1 - 2*x - 3*x^2]), {x, 0, 50}], x] (* _G. C. Greubel_, Apr 27 2017 *)
%o (Maxima) a(n):=sum((sum((binomial(k,l)*l*sum(binomial(j,1-n-2*l+k+2*j)*binomial(n-1+l-k,j),j,0,n+l-k-1))/(n+l-k-1),l,1,k)),k,1,n-1)+1; \\ _Vladimir Kruchinin_, Oct 31 2011
%o (PARI) x='x+O('x^66); gf=1-2*x^2/(2*x^2-3*x+1-sqrt(1-2*x-3*x^2)); Vec(gf) \\ _Joerg Arndt_, Jun 29 2013
%Y Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A005773, A054392, ...
%Y Conjectured to be equal to A326254.
%K nonn
%O 0,3
%A _N. J. A. Sloane_, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000
|
