A002629 Number of permutations of length n with one 3-sequence.

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

Author

N. J. A. Sloane

Keywords

• nonn

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

Examples

			a(4) = 2 because we have 2341 and 4123. - _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.

Crossrefs

Cf. A000166, A047921.

Programs

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

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

Extensions

More terms from Max Alekseyev, Feb 20 2010