login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054391 Number of permutations with certain forbidden subsequences. 5
1, 1, 2, 5, 14, 41, 123, 374, 1147, 3538, 10958, 34042, 105997, 330632, 1032781, 3229714, 10109310, 31667245, 99260192, 311294876, 976709394, 3065676758, 9625674442, 30231524869, 94972205349, 298419158008, 937861780439, 2947969125284 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Hankel transform is [1,1,1,....] = A000012. - Paul Barry, Jan 19 2009

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

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

LINKS

G. C. Greubel, Table of n, a(n) for n = 0..1000

E. Barcucci et al., From Motzkin to Catalan Permutations, Discr. Math., 217 (2000), 33-49.

P. Barry, On sequences with {-1, 0, 1} Hankel transforms, arXiv preprint arXiv:1205.2565 [math.CO], 2012. - From N. J. A. Sloane, Oct 18 2012

J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5

Toufik Mansour and Mark Shattuck, Pattern Avoiding Partitions, Sequence A054391 and the Kernel Method, Applications and Applied Mathematics, Vol. 6, Issue 2 (December 2011), pp. 397-411.

T. Mansour and M. Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From N. J. A. Sloane, Oct 13 2012

FORMULA

G.f.: 1 - 2*x^2 / (2*x^2-3*x+1-sqrt(1-2*x-3*x^2)). - Mansour and Shattuck

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

From Gary W. Adamson, Jul 29 2011: (start)

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,...):

1, 1, 0, 0, 0, 0,...

1, 1, 1, 0, 0, 0,...

1, 1, 1, 1, 0, 0,...

1, 1, 1, 0, 1, 0,...

1, 1, 1, 1, 0, 1,...

1, 1, 1, 1, 1, 0,...

... (end)

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

Conjecture: (-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

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

EXAMPLE

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).

MAPLE

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);

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);

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);

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

MATHEMATICA

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 *)

PROG

(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

(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

CROSSREFS

Interpolates between Motzkin numbers (A001006) and Catalan numbers (A000108). Cf. A005773, A054392, ...

Sequence in context: A124302 A088355 A113485 * A176677 A108626 A159772

Adjacent sequences:  A054388 A054389 A054390 * A054392 A054393 A054394

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Elisa Pergola (elisa(AT)dsi.unifi.it), May 21 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 07:06 EST 2018. Contains 299473 sequences. (Running on oeis4.)