login
A245348
Number T(n,k) of endofunctions f on [n] that are self-inverse on [k]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
5
1, 1, 1, 4, 3, 2, 27, 15, 8, 4, 256, 112, 50, 22, 10, 3125, 1125, 430, 166, 66, 26, 46656, 14256, 4752, 1626, 576, 206, 76, 823543, 218491, 64484, 19768, 6310, 2054, 688, 232, 16777216, 3932160, 1040384, 288512, 83736, 24952, 7660, 2388, 764
OFFSET
0,4
COMMENTS
T(n,k) counts endofunctions f:{1,...,n}-> {1,...,n} with f(f(i))=i for all i in {1,...,k}.
LINKS
FORMULA
T(n,k) = Sum_{i=0..min(k,n-k)} C(n-k,i)*C(k,i)*i!*A000085(k-i)*n^(n-k-i).
EXAMPLE
T(3,1) = 15: (1,1,1), (2,1,1), (3,1,1), (1,2,1), (3,2,1), (1,3,1), (3,3,1), (1,1,2), (2,1,2), (1,2,2), (1,3,2), (1,1,3), (2,1,3), (1,2,3), (1,3,3).
T(3,2) = 8: (2,1,1), (1,2,1), (3,2,1), (2,1,2), (1,2,2), (1,3,2), (2,1,3), (1,2,3).
T(3,3) = 4: (3,2,1), (1,3,2), (2,1,3), (1,2,3).
Triangle T(n,k) begins:
0 : 1;
1 : 1, 1;
2 : 4, 3, 2;
3 : 27, 15, 8, 4;
4 : 256, 112, 50, 22, 10;
5 : 3125, 1125, 430, 166, 66, 26;
6 : 46656, 14256, 4752, 1626, 576, 206, 76;
7 : 823543, 218491, 64484, 19768, 6310, 2054, 688, 232;
...
MAPLE
g:= proc(n) g(n):= `if`(n<2, 1, g(n-1)+(n-1)*g(n-2)) end:
T:= (n, k)-> add(binomial(n-k, i)*binomial(k, i)*i!*
g(k-i)*n^(n-k-i), i=0..min(k, n-k)):
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]]; T[0, 0] = 1; T[n_, k_] := Sum[Binomial[n-k, i]*Binomial[k, i]*i!*g[k-i]*n^(n-k-i), {i, 0, Min[k, n-k]}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *)
CROSSREFS
Columns k=0-1 give: A000312, A089945(n-1) for n>0.
Main diagonal gives A000085.
T(2n,n) gives A245141.
Sequence in context: A330778 A061312 A019130 * A174551 A349811 A239799
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jul 18 2014
STATUS
approved