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

%I #25 Apr 19 2018 17:16:19

%S 1,17,207,2279,24553,268521,3042210,36153510,454208895,6059942223,

%T 86030083110,1299647574882,20865826165777,355277740280849,

%U 6399391841784282,121623163346687166,2432739049821421911,51089720946192154791,1123991502048375026337

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

%C Same series for 1243 1432 2134 2143 4123 3214 3412 2341 3421 4321 4312. - _R. H. Hardin_, Mar 15 2009

%H Alois P. Heinz, <a href="/A158005/b158005.txt">Table of n, a(n) for n = 4..170</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PermutationPattern.html">Permutation Pattern</a>

%F a(n) = A214152(n,4) = A000142(n) - A005802(n) = A000142(n) - A214015(n,3). - _Alois P. Heinz_, Jul 05 2012

%p h:= proc(l) local n; n:=nops(l); add(i, i=l)!/mul(mul(1+l[i]-j

%p +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)

%p end:

%p g:= proc(n, i, l)

%p `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,

%p add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i)))

%p end:

%p a:= n-> n! -g(n, 3, []):

%p seq(a(n), n=4..30); # _Alois P. Heinz_, Jul 05 2012

%p # second Maple program

%p a:= proc(n) option remember; `if`(n<3, 0, `if`(n=4, 1,

%p ((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)

%p +9*(n-1)^2*(n-2)^2*a(n-3)) / ((n-4)*(n+2)^2)))

%p end:

%p seq(a(n), n=4..30); # _Alois P. Heinz_, Sep 26 2012

%t 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_ *)

%Y Cf. A000142, A005802, A214015, A214152.

%K nonn

%O 4,2

%A _Eric W. Weisstein_, Mar 11 2009

%E More terms from _R. H. Hardin_, Mar 15 2009

%E Two more terms from _Vladeta Jovovic_, Aug 17 2009

%E Corrected a(19)-a(20) and extended by _Alois P. Heinz_, Jul 05 2012