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

Author

Eric W. Weisstein, Mar 11 2009

Keywords

• nonn

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

Crossrefs

Cf. A000142, A005802, A214015, A214152.

Programs

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

Formula

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

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