|
%I M2003 N0792 #32 Dec 19 2021 10:08:13
%S 0,0,1,2,11,62,406,3046,25737,242094,2510733,28473604,350651588,
%T 4661105036,66529260545,1014985068610,16484495344135,283989434253186,
%U 5173041992087562,99346991708245506,2006304350543326057,42505510227603678206,942678881135812883321
%N Number of permutations of length n with one 3-sequence.
%C a(n) is also the number of successions in all permutations of [n-1] with no 3-sequences. A succession of a permutation p is a position i such that p(i+1) - p(i) = 1. Example: a(4)=2 because in 132, 213, 2*31, 31*2, 321 we have 0+0+1+1+0=2 successions (marked *). - _Emeric Deutsch_, Sep 07 2010
%D Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), no. 1, 297-305.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A002629/b002629.txt">Table of n, a(n) for n = 1..200</a>
%H J. Riordan, <a href="http://projecteuclid.org/euclid.bams/1183507357">Permutations without 3-sequences</a>, Bull. Amer. Math. Soc., 51 (1945), 745-748.
%F a(n) = Sum(binomial(n-k-2,k-1)*A000166(n-k), k=1..floor((n-1)/2)). - _Emeric Deutsch_, Sep 07 2010
%F a(n) ~ (n-1)! * (1 - 4/n + 13/(2*n^2) + 29/(6*n^3) - 551/(24*n^4) - 1101/(20*n^5) + 58879/(720*n^6)). - _Vaclav Kotesovec_, Mar 16 2015
%e a(4) = 2 because we have 2341 and 4123. - _Emeric Deutsch_, Sep 07 2010
%p d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-k-2, k-1)*d[n-k], k = 1 .. floor((1/2)*n-1/2)) end proc; seq(a(n), n = 1 .. 23); # _Emeric Deutsch_, Sep 07 2010
%p # second Maple program:
%p a:= proc(n) option remember;
%p `if`(n<5, -n*(n-1)*(n-2)*(n-5)/12,
%p (n-4) *a(n-1)+(3*n-6) *a(n-2)+(4*n-8) *a(n-3)
%p +(3*n-6)*a(n-4)+(n-2) *a(n-5))
%p end:
%p seq(a(n), n=1..25); # _Alois P. Heinz_, Jan 25 2014
%t a[n_] := Sum[Binomial[n-k-2, k-1]*Subfactorial[n-k], {k, 1, (n-1)/2}]; Array[a, 23] (* _Jean-François Alcover_, Mar 13 2014, after _Emeric Deutsch_ *)
%Y Cf. A000166, A047921.
%K nonn
%O 1,4
%A _N. J. A. Sloane_
%E More terms from _Max Alekseyev_, Feb 20 2010
|
