|
Search: id:A061018
|
|
|
| A061018 |
|
Triangle: a(n,m) = number of permutations of (1,2,...,n) with one or more fixed points in the m first positions. |
|
+0
2
|
|
| 1, 1, 1, 2, 3, 4, 6, 10, 13, 15, 24, 42, 56, 67, 76, 120, 216, 294, 358, 411, 455, 720, 1320, 1824, 2250, 2612, 2921, 3186, 5040, 9360, 13080, 16296, 19086, 21514, 23633, 25487, 40320, 75600, 106560, 133800, 157824, 179058, 197864, 214551, 229384
(list; table; graph; listen)
|
|
|
OFFSET
|
1,4
|
|
|
COMMENT
|
Row sums of n are the number of derangements (permutations without fixed point) of n+1.
|
|
FORMULA
|
a(n, m) = n! + Sum[T[n-1, k], {k, 0, m-1}] where T[n_?Negative, _] := 0; T[0, 0] := 0; T[n_, 0] := n n!; T[n_, m_] := T[n, m]=T[n, m-1]-T[n-1, m-1] (see A061312).
|
|
EXAMPLE
|
For n=3, the permutations are (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1); and (x, 2, 3), (x, 3, 2) have a fixed point x in position 1, (x, x, 3), (x, 3, 2), (3, x, 1) have a fixed point x in positions 1 or 2 and (x, x, x), (2, 1, x), (x, 3, 2), (3, x, 1)have a fixed point x in positions 1, 2 or 3, hence {2, 3, 4}
{1}, {1, 1}, {2, 3, 4}, {6, 10, 13, 15}, {24, 42, 56, 67, 76}, {120, 216, 294, 358, 411, 455}, {720, 1320, 1824, 2250, 2612, 2921, 3186}, ...
|
|
MATHEMATICA
|
Table[Count[Permutations[Range[n]], p_/; ( Times@@Take[(p-Range[n]), k]===0)], {n, 7}, {k, n}]
|
|
CROSSREFS
|
Sequence in context: A068499 A137172 A069744 this_sequence A130126 A121152 A089223
Adjacent sequences: A061015 A061016 A061017 this_sequence A061019 A061020 A061021
|
|
KEYWORD
|
nonn,tabl,easy
|
|
AUTHOR
|
Wouter Meeussen (wouter.meeussen(AT)pandora.be), May 23 2001
|
|
|
Search completed in 0.003 seconds
|
