|
| |
|
|
A002629
|
|
Number of permutations of length n with one 3-sequence.
(Formerly M2003 N0792)
|
|
7
| |
|
|
0, 0, 1, 2, 11, 62, 406, 3046, 25737, 242094, 2510733, 28473604, 350651588, 4661105036, 66529260545, 1014985068610, 16484495344135, 283989434253186, 5173041992087562, 99346991708245506, 2006304350543326057, 42505510227603678206
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 07 2010: (Start)
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 *).
(End)
|
|
|
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
| J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.
|
|
|
FORMULA
| Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 07 2010: (Start)
a(n) = Sum(binom(n-k-2,k-1)*d(n-k), k=1..floor((n-1)/2)), where d(j)=A000166(j) are the derangement numbers.
(End)
|
|
|
EXAMPLE
| Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 07 2010: (Start)
a(4)=2 because we have 2341 and 4123.
(End)
|
|
|
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); [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 07 2010]
|
|
|
CROSSREFS
| Cf. A047921.
A000166 [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 07 2010]
Sequence in context: A162274 A183160 A020078 * A065928 A188648 A114175
Adjacent sequences: A002626 A002627 A002628 * A002630 A002631 A002632
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Max Alekseyev (maxale(AT)gmail.com), Feb 20 2010
|
| |
|
|
