A158005 Numbers of pattern-matching permutations of (1234) for the permutations of {1, 2, ..., n} on n = 4, 5, 6, ... elements.

1, 17, 207, 2279, 24553, 268521, 3042210, 36153510, 454208895, 6059942223, 86030083110, 1299647574882, 20865826165777, 355277740280849, 6399391841784282, 121623163346687166, 2432739049821421911, 51089720946192154791, 1123991502048375026337

Offset

4,2

Comments

Same series for 1243 1432 2134 2143 4123 3214 3412 2341 3421 4321 4312. - R. H. Hardin, Mar 15 2009

Links

Alois P. Heinz, Table of n, a(n) for n = 4..170

Eric Weisstein's World of Mathematics, Permutation Pattern

Formula

a(n) = A214152(n,4) = A000142(n) - A005802(n) = A000142(n) - A214015(n,3). - Alois P. Heinz, Jul 05 2012

Maple

h:= proc(l) local n; n:=nops(l); add(i, i=l)!/mul(mul(1+l[i]-j
      +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
    end:
g:= proc(n, i, l)
      `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
       add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i)))
    end:
a:= n-> n! -g(n, 3, []):
seq(a(n), n=4..30);  # Alois P. Heinz, Jul 05 2012
# second Maple program
a:= proc(n) option remember; `if`(n<3, 0, `if`(n=4, 1,
      ((13-11*n-40*n^2+10*n^3+n^4)*a(n-1) -(10*n^2-9*n-31)*(n-1)^2*a(n-2)
       +9*(n-1)^2*(n-2)^2*a(n-3)) / ((n-4)*(n+2)^2)))
    end:
seq(a(n), n=4..30);  # Alois P. Heinz, Sep 26 2012

Mathematica

a[2] = a[3] = 0; a[4] = 1; a[n_] := a[n] = (1/((n-4)*(n+2)^2))* (9*(n-2)^2*a[n-3]*(n-1)^2 - (10*n^2 - 9*n - 31)*a[n-2]*(n-1)^2 + (n^4 + 10*n^3 - 40*n^2 - 11*n + 13)*a[n-1]); Table[a[n], {n, 4, 22}] (* Jean-François Alcover, Oct 22 2012, after Alois P. Heinz *)

Crossrefs

Cf. A000142, A005802, A214015, A214152.

Sequence in context: A246989 A016981 A158009 * A158006 A239157 A014921

Adjacent sequences: A158002 A158003 A158004 * A158006 A158007 A158008

Keyword

nonn

Author

Eric W. Weisstein, Mar 11 2009

Extensions

More terms from R. H. Hardin, Mar 15 2009

Two more terms from Vladeta Jovovic, Aug 17 2009

Corrected a(19)-a(20) and extended by Alois P. Heinz, Jul 05 2012

Status

approved