login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002629 Number of permutations of length n with one 3-sequence.
(Formerly M2003 N0792)
8
0, 0, 1, 2, 11, 62, 406, 3046, 25737, 242094, 2510733, 28473604, 350651588, 4661105036, 66529260545, 1014985068610, 16484495344135, 283989434253186, 5173041992087562, 99346991708245506, 2006304350543326057, 42505510227603678206, 942678881135812883321 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

a(n) is also the number of successions in all permutations of [n-1] with no 3-sequences. A succession of a permutation p is a position i such that p(i+1) - p(i) = 1. Example: a(4)=2 because in 132, 213, 2*31, 31*2, 321 we have 0+0+1+1+0=2 successions (marked *). - Emeric Deutsch, Sep 07 2010

REFERENCES

Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), no. 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 = 1..200

J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.

FORMULA

a(n) = Sum(C(n-k-2,k-1)*d(n-k), k=1..floor((n-1)/2)), where d(j) = A000166(j) are the derangement numbers. - Emeric Deutsch, Sep 07 2010

a(n) ~ (n-1)!. - Vaclav Kotesovec, Mar 17 2014

EXAMPLE

a(4) = 2 because we have 2341 and 4123. - Emeric Deutsch, Sep 07 2010

MAPLE

d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-k-2, k-1)*d[n-k], k = 1 .. floor((1/2)*n-1/2)) end proc; seq(a(n), n = 1 .. 23); # Emeric Deutsch, Sep 07 2010

# second Maple program:

a:= proc(n) option remember;

      `if`(n<5, -n*(n-1)*(n-2)*(n-5)/12,

         (n-4) *a(n-1)+(3*n-6) *a(n-2)+(4*n-8) *a(n-3)

       +(3*n-6)*a(n-4)+(n-2)   *a(n-5))

    end:

seq(a(n), n=1..25);  # Alois P. Heinz, Jan 25 2014

MATHEMATICA

a[n_] := Sum[Binomial[n-k-2, k-1]*Subfactorial[n-k], {k, 1, (n-1)/2}]; Array[a, 23] (* Jean-Fran├žois Alcover, Mar 13 2014, after Emeric Deutsch *)

CROSSREFS

Cf. A047921.

Cf. A000166. - Emeric Deutsch, Sep 07 2010

Sequence in context: A162274 A183160 A020078 * A235937 A065928 A188648

Adjacent sequences:  A002626 A002627 A002628 * A002630 A002631 A002632

KEYWORD

nonn

AUTHOR

N. J. A. Sloane.

EXTENSIONS

More terms from Max Alekseyev, Feb 20 2010

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified July 28 00:26 EDT 2014. Contains 244987 sequences.