The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A002628 Number of permutations of length n without 3-sequences. (Formerly M1536 N0600) 10
 1, 1, 2, 5, 21, 106, 643, 4547, 36696, 332769, 3349507, 37054436, 446867351, 5834728509, 82003113550, 1234297698757, 19809901558841, 337707109446702, 6094059760690035, 116052543892621951, 2325905946434516516, 48937614361477154273, 1078523843237914046247 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS a(n) = sum of row n of A180185. - Emeric Deutsch, Sep 06 2010 REFERENCES Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), number 1, 297-305. N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence). N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). LINKS Alois P. Heinz, Table of n, a(n) for n = 0..450 D. M. Jackson and R. C. Read, A note on permutations without runs of given length, Aequationes Math. 17 (1978), no. 2-3, 336-343. J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748. FORMULA a(n) = Sum_{k=0..floor(n/2)} binomial(n-k,k)*(d(n-k) + d(n-k-1)) for n>0, where d(j) = A000166(j) are the derangement numbers. - Emeric Deutsch, Sep 06 2010 EXAMPLE a(4) = 21 because only 1234, 2341, and 4123 contain 3-sequences. - Emeric Deutsch, Sep 06 2010 MAPLE seq(coeff(convert(series(add(m!*((t-t^3)/(1-t^3))^m, m=0..50), t, 50), polynom), t, n), n=0..25); # Pab Ter, Nov 06 2005 d[-1]:= 0: for n from 0 to 51 do d[n] := n*d[n-1]+(-1)^n end do: a:= proc(n) add(binomial(n-k, k)*(d[n-k]+d[n-k-1]), k = 0..floor((1/2)*n)) end proc: seq(a(n), n = 0..25); # Emeric Deutsch, Sep 06 2010 # third Maple program: a:= proc(n) option remember; `if`(n<5, [1\$2, 2, 5, 21][n+1], (n-3)*a(n-1)+(3*n-6)*a(n-2)+ (4*n-12)*a(n-3)+(3*n-12)*a(n-4)+(n-5)*a(n-5)) end: seq(a(n), n=0..25); # Alois P. Heinz, Jul 21 2019 MATHEMATICA d[0] = 1; d[n_] := d[n] = n d[n - 1] + (-1)^n; T[n_, k_] := If[n == 0 && k == 0, 1, If[k <= n/2, Binomial[n - k, k] d[n + 1 - k]/(n - k), 0]]; a[n_] := Sum[T[n, k], {k, 0, Quotient[n, 2]}]; a /@ Range[0, 25] (* Jean-François Alcover, May 23 2020 *) CROSSREFS Column k=0 of A047921. Cf. A165960, A165961, A165962. - Isaac Lambert, Oct 07 2009 Cf. A000166, A180185. - Emeric Deutsch, Sep 06 2010 Sequence in context: A185134 A347497 A130471 * A357919 A020129 A129582 Adjacent sequences: A002625 A002626 A002627 * A002629 A002630 A002631 KEYWORD nonn AUTHOR N. J. A. Sloane EXTENSIONS More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005 a(0)=1 prepended by Alois P. Heinz, Jul 21 2019 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 8 03:15 EST 2023. Contains 367662 sequences. (Running on oeis4.)