login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; table; graph; refs; listen; history; text; internal format)
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

Alois P. Heinz, Rows n = 0..140, flattened

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.

Cf. A239771, A245692.

Sequence in context: A293211 A061312 A019130 * A174551 A239799 A305235

Adjacent sequences:  A245345 A245346 A245347 * A245349 A245350 A245351

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jul 18 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 18 22:08 EDT 2019. Contains 322237 sequences. (Running on oeis4.)