A245141 -id:A245141 - cp's OEIS frontend

A246070 Number A(n,k) of endofunctions f on [2n] satisfying f^k(i) = i for all i in [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 4, 1, 2, 256, 1, 3, 16, 46656, 1, 2, 50, 216, 16777216, 1, 3, 36, 1626, 4096, 10000000000, 1, 2, 56, 1440, 83736, 100000, 8916100448256, 1, 3, 16, 2688, 84624, 6026120, 2985984, 11112006825558016, 1, 2, 70, 720, 215760, 7675200, 571350096, 105413504, 18446744073709551616

Offset: 0

Alois P. Heinz, Aug 12 2014

			Square array A(n,k) begins:
0 :            1,      1,       1,       1,        1,        1, ...
1 :            4,      2,       3,       2,        3,        2, ...
2 :          256,     16,      50,      36,       56,       16, ...
3 :        46656,    216,    1626,    1440,     2688,      720, ...
4 :     16777216,   4096,   83736,   84624,   215760,    94816, ...
5 :  10000000000, 100000, 6026120, 7675200, 24899120, 11218000, ...

Alois P. Heinz, Antidiagonals n = 0..70, flattened

Columns k=0-3 give: A085534, A062971, A245141, A245959.
Main diagonal gives A246071.
Cf. A246072 (the same for permutations).

with(numtheory): with(combinat): M:=multinomial:
b:= proc(n, k, p) local l, g; l, g:= sort([divisors(p)[]]),
      proc(k, m, i, t) option remember; local d, j; d:= l[i];
        `if`(i=1, n^m, add(M(k, k-(d-t)*j, (d-t)$j)/j!*
         (d-1)!^j *M(m, m-t*j, t$j) *g(k-(d-t)*j, m-t*j,
        `if`(d-t=1, [i-1, 0], [i, t+1])[]), j=0..min(k/(d-t),
        `if`(t=0, [][], m/t))))
      end; g(k, n-k, nops(l), 0)
    end:
A:= (n, k)-> `if`(k=0, (2*n)^(2*n), b(2*n, n, k)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

multinomial[n_, k_List] := n!/Times @@ (k!); M = multinomial;
b[n_, k0_, p_] := Module[{l, g}, l = Divisors[p];
g[k_, m_, i_, t_] := g[k, m, i, t] = Module[{d, j}, d = l[[i]];
    If[i == 1, If[m == 0, 1, n^m], Sum[M[k, Join[{k - (d - t)*j},
    Table[d - t, {j}]]]/j!*If[j == 0, 1, (d - 1)!^j]*M[m, Join[{m - t*j},
    Array[t&, j]]]*g[k - (d - t)*j, m - t*j, Sequence @@
    If[d - t == 1, {i - 1, 0}, {i, t + 1}]], {j, 0, Min[k/(d - t),
    If[t == 0, {}, m/t]]}]]];
g[k0, n - k0, Length[l], 0]];
A[n_, k_] := If[k == 0, If[n == 0, 1, (2n)^(2n)], b[2*n, n, k]];
Table[A[n, d - n], {d, 0, 10}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 27 2016, after Alois P. Heinz, updated Jan 01 2021 *)

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.

Original entry on oeis.org

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

Alois P. Heinz, Jul 18 2014

T(n,k) counts endofunctions f:{1,...,n}-> {1,...,n} with f(f(i))=i for all i in {1,...,k}.

			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;
     ...

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

Columns k=0-1 give: A000312, A089945(n-1) for n>0.
Main diagonal gives A000085.
T(2n,n) gives A245141.
Cf. A239771, A245692.

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);

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 *)

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).

cp's OEIS Frontend

A246070 Number A(n,k) of endofunctions f on [2n] satisfying f^k(i) = i for all i in [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica