A241981 -id:A241981 - cp's OEIS frontend

A246049 Number T(n,k) of endofunctions on [n] where the smallest cycle length equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 3, 1, 0, 19, 6, 2, 0, 175, 51, 24, 6, 0, 2101, 580, 300, 120, 24, 0, 31031, 8265, 4360, 2160, 720, 120, 0, 543607, 141246, 74130, 41160, 17640, 5040, 720, 0, 11012415, 2810437, 1456224, 861420, 430080, 161280, 40320, 5040

Offset: 0

Alois P. Heinz, Aug 11 2014

T(0,0) = 1 by convention.

In general, number of endofunctions on [n] where the smallest cycle length equals k is asymptotic to (exp(-H(k-1)) - exp(-H(k))) * n^n, where H(k) is the harmonic number A001008/A002805, k>=1. - Vaclav Kotesovec, Aug 21 2014

			Triangle T(n,k) begins:
  1;
  0,      1;
  0,      3,      1;
  0,     19,      6,     2;
  0,    175,     51,    24,     6;
  0,   2101,    580,   300,   120,    24;
  0,  31031,   8265,  4360,  2160,   720,  120;
  0, 543607, 141246, 74130, 41160, 17640, 5040, 720;
  ...

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

Columns k=0-10 give: A000007, A045531, A246189, A246190, A246191, A246192, A246193, A246194, A246195, A246196, A246197.
T(2n,n) gives A246050.
Row sums give A000312.
Main diagonal gives A000142(n-1) for n>0.
Cf. A241981, A243098.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i>n, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i+1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, k), j=0..n):
T:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), A(n, k) -A(n, k+1)):
seq(seq(T(n, k), k=0..n), n=0..12);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i>n, 0,
      Sum[(i-1)!^j*multinomial[n, {n-i*j, Sequence @@ Table[i, {j}]}]/j!*
      b[n-i*j, i+1], {j, 0, n/i}]]];
A[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, k], {j, 0, n}];
T[n_, k_] := If[k == 0, If[n == 0, 1, 0], A[n, k] - A[n, k+1]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 06 2015, after Alois P. Heinz *)

A243098 Number T(n,k) of endofunctions on [n] with all cycles of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 3, 1, 0, 16, 6, 2, 0, 125, 51, 24, 6, 0, 1296, 560, 300, 120, 24, 0, 16807, 7575, 4360, 2160, 720, 120, 0, 262144, 122052, 73710, 41160, 17640, 5040, 720, 0, 4782969, 2285353, 1430016, 861420, 430080, 161280, 40320, 5040

Offset: 0

Alois P. Heinz, Aug 18 2014

T(0,0) = 1 by convention.

			Triangle T(n,k) begins:
  1;
  0,      1;
  0,      3,      1;
  0,     16,      6,     2;
  0,    125,     51,    24,     6;
  0,   1296,    560,   300,   120,    24;
  0,  16807,   7575,  4360,  2160,   720,  120;
  0, 262144, 122052, 73710, 41160, 17640, 5040, 720;
  ...

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

Columns k=0-4 give: A000007, A000272(n+1) for n>0, A057817(n+1), 2*A060917, 6*A060918.
Row sums give A241980.
T(2n,n) gives A246050.
Main diagonal gives A000142(n-1) for n>0.
Cf. A241981, A246049.

with(combinat):
T:= (n, k)-> `if`(k*n=0, `if`(k+n=0, 1, 0),
    add(binomial(n-1, j*k-1)*n^(n-j*k)*(k-1)!^j*
    multinomial(j*k, k$j, 0)/j!, j=0..n/k)):
seq(seq(T(n, k), k=0..n), n=0..10);

multinomial[n_, k_] := n!/Times @@ (k!); T[n_, k_] := If[k*n==0, If[k+n == 0, 1, 0], Sum[Binomial[n-1, j*k-1]*n^(n-j*k)*(k-1)!^j*multinomial[j*k, Append[Array[k&, j], 0]]/j!, {j, 0, n/k}]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 19 2017, translated from Maple *)

E.g.f. of column k>0: exp((-LambertW(-x))^k/k), e.g.f. of column k=0: 1.

A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.

Original entry on oeis.org

0, 0, 1, 9, 93, 1155, 17025, 292383, 5752131, 127790505, 3167896005, 86756071545, 2602658092419, 84917405260779, 2994675198208785, 113538315994418175, 4606094297461892895, 199122610252964803857, 9139190793845641425261, 443881600924216704982425

Offset: 0

Carlos Alves, Aug 06 2009

nonn

The number of functions in a finite set {1,..,n} for which the sequence of composition powers ends in a fixed point gave terms of the sequence A000272(n-1)=(n+1)^(n-1).

This is to be seen as a conjecture, and the sequence ending with a length 2 cycle does not seem to have such an easy expression.

			Any transposition (or disjoint combination) is one element to be counted.
When n=2, there is only one, and a(2)=1. When n=3, there are only 3 transpositions, but there are other 6 elements, for instance
f:{1,2,3}->{2,1,1} gives fof:{1,2,3}->{1,2,2} and fofof=f (cycle 2),
(the others are similar), thus giving a(3)=9.

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

Cf. A163947, A163952, A163859.

Column k=2 of A222029 and of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 2) -A(n, 1):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 19 2014

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[(i - 1)!^j*multinomial[ n, Join[{n - i*j}, Table[i, j]]]/j!*b[n - i*j, i - 1], {j, 0, n/i}]]];
A[n_, k_] :=  Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}];
a[0] = 0; a[n_] := A[n, 2] - A[n, 1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jun 05 2018, after Alois P. Heinz *)

a(n) ~ (2*exp(3/2)-exp(1)) * n^(n-1). - Vaclav Kotesovec, Aug 20 2014

a(0), a(8)-a(19) added and A246212 merged into this sequence by Alois P. Heinz, Aug 14 2017

A241982 Number of endofunctions on [2n] where the largest cycle length equals n.

Original entry on oeis.org

1, 3, 93, 8600, 1719060, 604727424, 331079253120, 260480095349760, 278592031202284800, 388855261570122547200, 686533182382689959116800, 1495779844806108697677004800, 3942052104672989614027181260800, 12360865524060039746012601384960000

Offset: 0

Alois P. Heinz, Aug 10 2014

nonn

			a(1) = 3: (1,1), (1,2), (2,2).

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

Cf. A241981, A246050.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> `if`(n=0, 1, A(2*n, n) -A(2*n, n-1)):
seq(a(n), n=0..15);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = Which[n==0, 1, i<1, 0, True, Sum[(i-1)!^j* multinomial[n, Join[{n-i*j}, Table[i, {j}]]]/j!*b[n-i*j, i-1], {j, 0, n/i} ] ];
A[n_, k_] := Sum[Binomial[n-1, j-1]*n^(n-j)*b[j, Min[j, k]], {j, 0, n}];
a[n_] := If[n == 0, 1, A[2n, n] - A[2n, n-1]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Apr 01 2017, translated from Maple *)

a(n) = A241981(2n,n).

a(n) ~ 2^(3*n+1/2) * n^(2*n-1) / exp(n). - Vaclav Kotesovec, Aug 19 2014

A246213 Number of endofunctions on [n] where the largest cycle length equals 3.

Original entry on oeis.org

2, 32, 500, 8600, 165690, 3568768, 85372280, 2251589600, 65007768650, 2041482333440, 69330316507452, 2533173484572640, 99124829660524850, 4137148176815360000, 183498069976613613680, 8620747043700633797888, 427712115490907106172050, 22350263436559575406220800

Offset: 3

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 3..200

Column k=3 of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 3) -A(n, 2):
seq(a(n), n=3..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[(i - 1)!^j multinomial[n, Join[{n - i*j}, Table[i, {j}]]]/j! b[n - i*j, i - 1], {j, 0, n/i}]]];
A[n_, k_] := Sum[Binomial[n-1, j-1] n^(n-j) b[j, Min[j, k]], {j, 0, n}];
a[n_] := A[n, 3] - A[n, 2];
a /@ Range[3, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ (3*exp(11/6)-2*exp(3/2)) * n^(n-1). - Vaclav Kotesovec, Aug 21 2014

A246214 Number of endofunctions on [n] where the largest cycle length equals 4.

Original entry on oeis.org

6, 150, 3240, 72030, 1719060, 44520840, 1252364400, 38167414560, 1255558958280, 44404434904830, 1681726757430720, 67953913291104750, 2919509551303952880, 132943540577100047760, 6397727538671302783680, 324511272091351156939200, 17306903935107005765263200

Offset: 4

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..200

Column k=4 of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 4) -A(n, 3):
seq(a(n), n=4..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[(i - 1)!^j multinomial[n, Join[{n - i*j}, Table[i, {j}]]]/j! b[n - i*j, i - 1], {j, 0, n/i}]]];
A[n_, k_] := Sum[Binomial[n-1, j-1] n^(n-j) b[j, Min[j, k]], {j, 0, n}];
a[n_] := A[n, 4] - A[n, 3];
a /@ Range[4, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ (4*exp(25/12) - 3*exp(11/6)) * n^(n-1). - Vaclav Kotesovec, Aug 21 2014

A246215 Number of endofunctions on [n] where the largest cycle length equals 5.

Original entry on oeis.org

24, 864, 24696, 688128, 19840464, 604727424, 19632956112, 680195957760, 25130679950376, 988325574652416, 41277744231187464, 1826323584590389248, 85391029667937905184, 4209030460729215184896, 218223423136426488339744, 11875233973816788160610304

Offset: 5

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 5..200

Column k=5 of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 5) -A(n, 4):
seq(a(n), n=5..25);

multinomial[n_, k_List] := n!/Times @@ (k!);
b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[(i - 1)!^j multinomial[n, Join[{n - i*j}, Table[i, {j}]]]/j! b[n - i*j, i - 1], {j, 0, n/i}]]];
A[n_, k_] := Sum[Binomial[n-1, j-1] n^(n-j) b[j, Min[j, k]], {j, 0, n}];
a[n_] := A[n, 5] - A[n, 4];
a /@ Range[5, 25] (* Jean-François Alcover, Dec 28 2020, after Alois P. Heinz *)

a(n) ~ (5*exp(137/60) - 4*exp(25/12)) * n^(n-1). - Vaclav Kotesovec, Aug 21 2014

A246216 Number of endofunctions on [n] where the largest cycle length equals 6.

Original entry on oeis.org

120, 5880, 215040, 7348320, 252000000, 8928667440, 331079253120, 12919902035040, 531665809234560, 23074929870993000, 1055390757120860160, 50802829404718896960, 2569731417499060039680, 136361684705644061566560, 7578327282420081922560000

Offset: 6

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 6..200

Column k=6 of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 6) -A(n, 5):
seq(a(n), n=6..25);

a(n) ~ (6*exp(49/20) - 5*exp(137/60)) * n^(n-1). - Vaclav Kotesovec, Aug 21 2014

A246217 Number of endofunctions on [n] where the largest cycle length equals 7.

Original entry on oeis.org

720, 46080, 2099520, 86400000, 3478701600, 141893959680, 5963619055680, 260480095349760, 11874161338182000, 565994948205772800, 28225084763940704640, 1472185000741804277760, 80257688278285346487360, 4568639693232433397760000, 271256500003796168962953600

Offset: 7

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 7..200

Column k=7 of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 7) -A(n, 6):
seq(a(n), n=7..25);

a(n) ~ (7*exp(363/140) - 6*exp(49/20)) * n^(n-1). - Vaclav Kotesovec, Aug 21 2014

A246218 Number of endofunctions on [n] where the largest cycle length equals 8.

Original entry on oeis.org

5040, 408240, 22680000, 1106859600, 51732172800, 2408384618640, 113960430904320, 5541379593750000, 278592031202284800, 14529619059476320800, 787422201081850414080, 44373594768472437642720, 2600326096882824360960000, 158404803877320370312773600

Offset: 8

Alois P. Heinz, Aug 19 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 8..200

Column k=8 of A241981.

with(combinat):
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add((i-1)!^j*multinomial(n, n-i*j, i$j)/j!*
      b(n-i*j, i-1), j=0..n/i)))
    end:
A:= (n, k)-> add(binomial(n-1, j-1)*n^(n-j)*b(j, min(j, k)), j=0..n):
a:= n-> A(n, 8) -A(n, 7):
seq(a(n), n=8..25);

a(n) ~ (8*exp(761/280) - 7*exp(363/140)) * n^(n-1). - Vaclav Kotesovec, Aug 21 2014

cp's OEIS Frontend

A246049 Number T(n,k) of endofunctions on [n] where the smallest cycle length equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A243098 Number T(n,k) of endofunctions on [n] with all cycles of length k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A163951 The number of functions in a finite set for which the sequence of composition powers ends in a length 2 cycle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A241982 Number of endofunctions on [2n] where the largest cycle length equals n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246213 Number of endofunctions on [n] where the largest cycle length equals 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246214 Number of endofunctions on [n] where the largest cycle length equals 4.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246215 Number of endofunctions on [n] where the largest cycle length equals 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246216 Number of endofunctions on [n] where the largest cycle length equals 6.

Views