|
| |
|
|
A245693
|
|
Number T(n,k) of permutations on [n] that are self-inverse on [k] but not on [k+1]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
2
|
|
|
|
1, 0, 1, 0, 0, 2, 2, 0, 0, 4, 12, 2, 0, 0, 10, 72, 18, 4, 0, 0, 26, 480, 120, 36, 8, 0, 0, 76, 3600, 840, 264, 84, 20, 0, 0, 232, 30240, 6480, 1920, 648, 216, 52, 0, 0, 764, 282240, 55440, 15120, 4920, 1776, 612, 152, 0, 0, 2620, 2903040, 524160, 131040, 39600, 13920, 5232, 1848, 464, 0, 0, 9496
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
T(n,k) counts permutations p:{1,...,n}-> {1,...,n} with p(p(i))=i for all i in {1,...,k} and p(p(k+1))<>k+1 if k<n.
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = H(n,k) - H(n,k+1) with H(n,k) = Sum_{i=0..min(k,n-k)} C(n-k,i) * C(k,i) * i! * A000085(k-i) * (n-k-i)!.
|
|
|
EXAMPLE
|
Triangle T(n,k) begins:
0 : 1;
1 : 0, 1;
2 : 0, 0, 2;
3 : 2, 0, 0, 4;
4 : 12, 2, 0, 0, 10;
5 : 72, 18, 4, 0, 0, 26;
6 : 480, 120, 36, 8, 0, 0, 76;
7 : 3600, 840, 264, 84, 20, 0, 0, 232;
8 : 30240, 6480, 1920, 648, 216, 52, 0, 0, 764;
|
|
|
MAPLE
|
g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:
H:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*
g(k-i)*(n-k-i)!, i=0..min(k, n-k)):
T:= (n, k)-> H(n, k) -H(n, k+1):
seq(seq(T(n, k), k=0..n), n=0..10);
|
|
|
MATHEMATICA
|
g[n_] := g[n] = If[n < 2, 1, g[n - 1] + (n - 1)*g[n - 2]];
H[n_, k_] := Sum[Binomial[n - k, i]*Binomial[k, i]*i!*
g[k - i]*(n - k - i)!, {i, 0, Min[k, n - k]}];
T[n_, k_] := H[n, k] - H[n, k + 1];
|
|
|
CROSSREFS
|
Column k=0 give A062119(n-1) for n>1.
Cf. A245692 (the same for endofunctions).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
