|
Search: id:A155521
|
|
|
| A155521 |
|
Smallest fixed point summed over all non-derangement permutations of {1,2,...,n}. |
|
+0
3
|
|
| 0, 1, 1, 7, 31, 191, 1331, 10655, 95887, 958879, 10547659, 126571919, 1645434935, 23036089103, 345541336531, 5528661384511, 93987243536671, 1691770383660095, 32143637289541787, 642872745790835759, 13500327661607550919
(list; graph; listen)
|
|
|
OFFSET
|
0,4
|
|
|
COMMENT
|
a(n) is also the number of permutations of {1,2,...,n,n+1} having at least 2 fixed points. Example: a(3)=7 because we have 1234, 1243, 1324, 1432, 2134, 4231, and 3214.
|
|
REFERENCES
|
E. Deutsch and S. Elizalde, The largest and the smallest fixed points of permutations, arXiv:0904.2792v1, 2009.
|
|
FORMULA
|
Rec. rel: a(n) = (n+1)*a(n-1) +n*(-1)^(n+1); a(0)=0.
Egf = [1-(1+x^2)*exp(-x)]/(1-x)^2.
a(n)=(n+1)!+(-1)^n-2(n+1)d(n),
a(n)=(n+1)!-(n+1)d(n)-d(n+1), where d(n)=A000166(n) are the derangement numbers. a(n)=(n+1)!+(-1)^n -2(n+1)d(n)
|
|
EXAMPLE
|
a(n)=7 because the non-derangements of {1,2,3} are 123, 132, 213, 321 with smallest fixed points 1, 1, 3, 2.
|
|
MAPLE
|
a[0] := 0: for n to 25 do a[n] := (n+1)*a[n-1]+n*(-1)^(n+1) end do: seq(a[n], n = 0 .. 21);
|
|
CROSSREFS
|
Cf. A000166, A047920
Sequence in context: A102239 A139151 A139060 this_sequence A060015 A094711 A143564
Adjacent sequences: A155518 A155519 A155520 this_sequence A155522 A155523 A155524
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Emeric Deutsch (deutsch(AT)duke.poly.edu), Apr 21 2009
|
|
|
Search completed in 0.002 seconds
|
