login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002629 Number of permutations of length n with one 3-sequence.
(Formerly M2003 N0792)
8

%I M2003 N0792

%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

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 April 9 07:30 EDT 2020. Contains 333344 sequences. (Running on oeis4.)