login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002628 Number of permutations of length n without 3-sequences.
(Formerly M1536 N0600)
9

%I M1536 N0600

%S 1,2,5,21,106,643,4547,36696,332769,3349507,37054436,446867351,

%T 5834728509,82003113550,1234297698757,19809901558841,337707109446702,

%U 6094059760690035,116052543892621951,2325905946434516516

%N Number of permutations of length n without 3-sequences.

%C a(n) = sum of row n of A180185. - _Emeric Deutsch_, Sep 06 2010

%D Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), number 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 D. M. Jackson and R. C. Read, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002031183">A note on permutations without runs of given length</a>, Aequationes Math. 17 (1978), no. 2-3, 336-343.

%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(binom(n-k,k)*[d(n-k)+d(n-k-1)], k=0..floor(n/2)), where d(j)=A000166(j) are the derangement numbers. - _Emeric Deutsch_, Sep 06 2010

%e a(4)=21 because only 1234, 2341, and 4123 contain 3-sequences. - _Emeric Deutsch_, Sep 06 2010

%p seq(coeff(convert(series(add(m!*((t-t^3)/(1-t^3))^m,m=0..50),t,50),polynom),t,n),n=1..25); # Pab Ter, Nov 06 2005

%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, k)*(d[n-k]+d[n-k-1]), k = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 1 .. 20); # _Emeric Deutsch_, Sep 06 2010

%Y Cf. A047921.

%Y Cf. A165960, A165961, A165962. [_Isaac Lambert_, Oct 07 2009]

%Y Cf. A000166, A180185 [_Emeric Deutsch_, Sep 06 2010]

%K nonn

%O 1,2

%A _N. J. A. Sloane_.

%E More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005

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 March 21 04:59 EDT 2019. Contains 321364 sequences. (Running on oeis4.)