A002629 Number of permutations of length n with one 3-sequence. (Formerly M2003 N0792)

0, 0, 1, 2, 11, 62, 406, 3046, 25737, 242094, 2510733, 28473604, 350651588, 4661105036, 66529260545, 1014985068610, 16484495344135, 283989434253186, 5173041992087562, 99346991708245506, 2006304350543326057, 42505510227603678206, 942678881135812883321

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(binomial(n-k-2,k-1)*A000166(n-k), k=1..floor((n-1)/2)). - Emeric Deutsch, Sep 07 2010

a(n) ~ (n-1)! * (1 - 4/n + 13/(2*n^2) + 29/(6*n^3) - 551/(24*n^4) - 1101/(20*n^5) + 58879/(720*n^6)). - Vaclav Kotesovec, Mar 16 2015

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. A000166, A047921.

Sequence in context: A183160 A020078 A365131 * 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