|
|
A207819
|
|
Number of permutations of [n] with a fixed point and/or a succession.
|
|
7
|
|
|
0, 1, 1, 6, 20, 106, 618, 4358, 34836, 313592, 3135988, 34498646, 414007634, 5382362086, 75356174332, 1130382058576, 18086649408624, 307480839465174, 5534775895914982, 105162728081809146, 2103289132221173216, 44169707042511725964, 971745847021319655464, 22350404337704558809666
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A succession of a permutation p is the appearance of [k,k+1], e.g. in 23541, 23 is a succession.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
For n=4 the only permutations that do not count are 2143, 2413, 3142 and 4321, so a(4) = 4!-4 = 20.
|
|
MATHEMATICA
|
F[{}] = 1; F[S_] := Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {Length[S]}}];
G[{}, _] = 1; G[S_, t_] := G[S, t] = Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {t, Length[S]}}];
|
|
PROG
|
(PARI) A207819(n)={my(p, c); sum(k=1, n!, p=numtoperm(n, k); (c=(p[1]==1)) || for(j=2, n, p[j]!=j & p[j]-1!=p[j-1] & next; c++; break); c)} \\ M. F. Hasler, Jan 13 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|