login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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)
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

CROSSREFS

Cf. A047921.

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

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

Sequence in context: A008982 A185134 A130471 * A020129 A129582 A152576

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 7 15:44 EDT 2020. Contains 333306 sequences. (Running on oeis4.)