A209319 -id:A209319 - cp's OEIS frontend

A246522 Number A(n,k) of endofunctions on [n] whose cycle lengths are divisors of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 3, 0, 1, 1, 4, 16, 0, 1, 1, 3, 25, 125, 0, 1, 1, 4, 18, 218, 1296, 0, 1, 1, 3, 25, 157, 2451, 16807, 0, 1, 1, 4, 16, 224, 1776, 33832, 262144, 0, 1, 1, 3, 27, 125, 2601, 24687, 554527, 4782969, 0, 1, 1, 4, 16, 250, 1320, 37072, 407464, 10535100, 100000000, 0

Offset: 0

Alois P. Heinz, Aug 28 2014

			Square array A(n,k) begins:
  1,     1,     1,     1,     1,     1,     1, ...
  0,     1,     1,     1,     1,     1,     1, ...
  0,     3,     4,     3,     4,     3,     4, ...
  0,    16,    25,    18,    25,    16,    27, ...
  0,   125,   218,   157,   224,   125,   250, ...
  0,  1296,  2451,  1776,  2601,  1320,  2951, ...
  0, 16807, 33832, 24687, 37072, 17671, 42552, ...

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

Columns k=0-10 give: A000007, A000272(n+1), A209319, A246523, A246524, A246525, A246526, A246527, A246528, A246529, A246530.

Main diagonal gives A246531.

with(numtheory):
egf:= k-> exp(add((-LambertW(-x))^d/d, d=divisors(k))):
A:= (n, k)-> n!*coeff(series(egf(k), x, n+1), x, n):
seq(seq(A(n, d-n), n=0..d), d=0..12);
# second Maple program:
with(combinat):
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(multinomial(n, n-i*j, i$j)/j!*b(n-i*j, i-1, k)*
      (i-1)!^j, j=0..`if`(irem(k, i)=0, n/i, 0))))
    end:
A:=(n, k)->add(b(j, min(k, j), k)*n^(n-j)*binomial(n-1, j-1), j=0..n):
seq(seq(A(n, d-n), n=0..d), d=0..12);

egf[k_] := Exp[Sum[(-ProductLog[-x])^d/d, {d, Divisors[k]}]];
A[1, 0] = 0; A[0, ] = 1; A[1, ] = 1; A[_, 0] = 0;
A[n_, k_] := n!*SeriesCoefficient[egf[k], {x, 0, n}];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 04 2014, translated from first Maple program *)
multinomial[n_, k_List] := n!/Times @@ (k!);
Unprotect[Power]; 0^0 = 1; Protect[Power];
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[multinomial[n, Join[{n - i*j}, Table[i, {j}]]]/j!*b[n - i*j, i-1, k]*(i-1)!^j, {j, 0, If[Mod[k, i] == 0, n/i, 0]}]]];
A[n_, k_] := Sum[b[j, Min[k, j], k]*n^(n-j)*Binomial[n-1, j-1], {j, 0, n}];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Nov 22 2023, from 2nd Maple program *)

E.g.f. of column k: exp(Sum_{d|k} (-LambertW(-x))^d/d).

A208240 Number of functions f:{1,2,...,n}->{1,2,...,n} with at least one cycle of length >= 3.

Original entry on oeis.org

0, 0, 0, 2, 38, 674, 12824, 269016, 6242116, 159629984, 4474156304, 136638234842, 4521281961800, 161263788956178, 6171136558989856, 252297980348513264, 10978226724737842928, 506678120536777708544, 24726830423666093964224, 1272394054736096884141554

Offset: 0

Geoffrey Critzer, Jan 11 2013

nonn

a(n) = n^n - A209319(n). - Vaclav Kotesovec, Oct 09 2013

Alois P. Heinz, Table of n, a(n) for n = 0..150

Cf. A101334.

T:= -LambertW(-x):
egf:= 1/(1-T) -exp(T +T^2/2):
a:= n-> n! *coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..20);  # Alois P. Heinz, Jan 11 2013

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[Series[1/(1-t)-Exp[Sum[t^i/i,{i,1,2}]],{x,0,nn}],x]

E.g.f.: 1/(1-T(x)) - exp(T(x) + T(x)^2/2) where T(x) is the e.g.f. for A000169.

cp's OEIS Frontend

A246522 Number A(n,k) of endofunctions on [n] whose cycle lengths are divisors of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula