login
A002628
Number of permutations of length n without 3-sequences.
(Formerly M1536 N0600)
14
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,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
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 * A370656 A357919 A020129
KEYWORD
nonn
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