# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a002628
Showing 1-1 of 1

%I A002628 M1536 N0600 #40 Apr 20 2021 12:58:35
%S A002628 1,1,2,5,21,106,643,4547,36696,332769,3349507,37054436,446867351,
%T A002628 5834728509,82003113550,1234297698757,19809901558841,337707109446702,
%U A002628 6094059760690035,116052543892621951,2325905946434516516,48937614361477154273,1078523843237914046247
%N A002628 Number of permutations of length n without 3-sequences.
%C A002628 a(n) = sum of row n of A180185. - _Emeric Deutsch_, Sep 06 2010
%D A002628 Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), number 1, 297-305.
%D A002628 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002628 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002628 Alois P. Heinz, <a href="/A002628/b002628.txt">Table of n, a(n) for n = 0..450</a>
%H A002628 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 A002628 J. Riordan, <a href="http://projecteuclid.org/euclid.bams/1183507357">Permutations without 3-sequences</a>, Bull. Amer. Math. Soc., 51 (1945), 745-748.
%F A002628 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
%e A002628 a(4) = 21 because only 1234, 2341, and 4123 contain 3-sequences. - _Emeric Deutsch_, Sep 06 2010
%p A002628 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
%p A002628 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
%p A002628 # third Maple program:
%p A002628 a:= proc(n) option remember; `if`(n<5,
%p A002628       [1$2, 2, 5, 21][n+1], (n-3)*a(n-1)+(3*n-6)*a(n-2)+
%p A002628       (4*n-12)*a(n-3)+(3*n-12)*a(n-4)+(n-5)*a(n-5))
%p A002628     end:
%p A002628 seq(a(n), n=0..25);  # _Alois P. Heinz_, Jul 21 2019
%t A002628 d[0] = 1; d[n_] := d[n] = n d[n - 1] + (-1)^n;
%t A002628 T[n_, k_] := If[n == 0 && k == 0, 1, If[k <= n/2, Binomial[n - k, k] d[n + 1 - k]/(n - k), 0]];
%t A002628 a[n_] := Sum[T[n, k], {k, 0, Quotient[n, 2]}];
%t A002628 a /@ Range[0, 25] (* _Jean-François Alcover_, May 23 2020 *)
%Y A002628 Column k=0 of A047921.
%Y A002628 Cf. A165960, A165961, A165962. - _Isaac Lambert_, Oct 07 2009
%Y A002628 Cf. A000166, A180185. - _Emeric Deutsch_, Sep 06 2010
%K A002628 nonn
%O A002628 0,3
%A A002628 _N. J. A. Sloane_
%E A002628 More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005
%E A002628 a(0)=1 prepended by _Alois P. Heinz_, Jul 21 2019

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE