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

From Gus Wiseman, Jun 22 2019: (Start)

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:

  {}  {{1}}  {{1,2}}    {{1,2,3}}      {{1,2,3,4}}

             {{1},{2}}  {{1},{2,3}}    {{1},{2,3,4}}

                        {{1,2},{3}}    {{1,2},{3,4}}

                        {{1,3},{2}}    {{1,2,3},{4}}

                        {{1},{2},{3}}  {{1,2,4},{3}}

                                       {{1,3},{2,4}}

                                       {{1,3,4},{2}}

                                       {{1},{2},{3,4}}

                                       {{1},{2,3},{4}}

                                       {{1,2},{3},{4}}

                                       {{1},{2,4},{3}}

                                       {{1,3},{2},{4}}

                                       {{1,4},{2},{3}}

                                       {{1},{2},{3},{4}}

Cf. A000108, A000110, A058681, A326212, A326237, A326243, A326244, A326249, A326254, A326255.

(End)

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

Nickolas Hein, Jia Huang, Variations of the Catalan numbers from some nonassociative binary operations, arXiv:1807.04623 [math.CO], 2018.

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

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 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, ...

Conjectured to be equal to A326254.

Sequence in context: A088355 A113485 A326254 * 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 03:15 EDT 2019. Contains 328038 sequences. (Running on oeis4.)