A002628 Number of permutations of length n without 3-sequences.

1, 1, 2, 5, 21, 106, 643, 4547, 36696, 332769, 3349507, 37054436, 446867351, 5834728509, 82003113550, 1234297698757, 19809901558841, 337707109446702, 6094059760690035, 116052543892621951, 2325905946434516516, 48937614361477154273, 1078523843237914046247

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

a(n) = sum of row n of A180185. - Emeric Deutsch, Sep 06 2010

Examples

			a(4) = 21 because only 1234, 2341, and 4123 contain 3-sequences. - _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.

Crossrefs

Column k=0 of A047921.

Cf. A165960, A165961, A165962. - Isaac Lambert, Oct 07 2009

Cf. A000166, A180185. - Emeric Deutsch, Sep 06 2010

Programs

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 *)

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

Extensions

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

a(0)=1 prepended by Alois P. Heinz, Jul 21 2019