|
| |
|
|
A002628
|
|
Number of permutations of length n without 3-sequences.
(Formerly M1536 N0600)
|
|
9
| |
|
|
1, 2, 5, 21, 106, 643, 4547, 36696, 332769, 3349507, 37054436, 446867351, 5834728509, 82003113550, 1234297698757, 19809901558841, 337707109446702, 6094059760690035, 116052543892621951, 2325905946434516516
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 06 2010: (Start)
a(n) = sum of row n of A180185.
(End)
|
|
|
REFERENCES
| Jackson, D. M.; Reilly, J. W. Permutations with a prescribed number of p-runs. Ars Combinatoria 1 (1976), number 1, 297-305.
J. Riordan, Permutations without 3-sequences, Bull. Amer. Math. Soc., 51 (1945), 745-748.
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
| Jackson, D. M. and Read, R. C., A note on permutations without runs of given length, Aequationes Math. 17 (1978), number 2-3, 336-343.
|
|
|
FORMULA
| Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 06 2010: (Start)
a(n) = sum(binom(n-k,k)*[d(n-k)+d(n-k-1)], k=0..floor(n/2)), where d(j)=A000166(j) are the derangement numbers.
(End)
|
|
|
EXAMPLE
| Contribution from Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 06 2010: (Start)
a(4)=21 because only 1234, 2341, and 4123 contain 3-sequences.
(End)
|
|
|
MAPLE
| seq(coeff(convert(series(add(m!*((t-t^3)/(1-t^3))^m, m=0..50), t, 50), polynom), t, n), n=1..25); (Pab Ter)
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, k)*(d[n-k]+d[n-k-1]), k = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 1 .. 20); [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 06 2010]
|
|
|
CROSSREFS
| Cf. A047921.
Cf. A165960, A165961, A165962. [From Isaac E. Lambert (lamberti09(AT)mail.wlu.edu), Oct 07 2009]
A000166, A180185 [From Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 06 2010]
Sequence in context: A008981 A008982 A130471 * A020129 A129582 A152576
Adjacent sequences: A002625 A002626 A002627 * A002629 A002630 A002631
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Pab Ter (pabrlos2(AT)yahoo.com), Nov 06 2005
|
| |
|
|
