A243098 -id:A243098 - 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 *)

A241981 Number T(n,k) of endofunctions on [n] where the largest cycle length equals 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, 9, 2, 0, 125, 93, 32, 6, 0, 1296, 1155, 500, 150, 24, 0, 16807, 17025, 8600, 3240, 864, 120, 0, 262144, 292383, 165690, 72030, 24696, 5880, 720, 0, 4782969, 5752131, 3568768, 1719060, 688128, 215040, 46080, 5040

Offset: 0

Alois P. Heinz, Aug 10 2014

T(0,0) = 1 by convention.

In general, number of endofunctions on [n] where the largest cycle length equals k is asymptotic to (k*exp(H(k)) - (k-1)*exp(H(k-1))) * n^(n-1), where H(k) is the harmonic number A001008/A002805, k>=1. The multiplicative constant is (for big k) asymptotic to 2*k*exp(gamma), where gamma is the Euler-Mascheroni constant (see A001620 and A073004). - Vaclav Kotesovec, Aug 21 2014

			Triangle T(n,k) begins:
  1;
  0,      1;
  0,      3,      1;
  0,     16,      9,      2;
  0,    125,     93,     32,     6;
  0,   1296,   1155,    500,   150,    24;
  0,  16807,  17025,   8600,  3240,   864,  120;
  0, 262144, 292383, 165690, 72030, 24696, 5880, 720;
  ...

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

Columns k=0-10 give: A000007, A000272(n+1) for n>0, A163951, A246213, A246214, A246215, A246216, A246217, A246218, A246219, A246220.
T(2n,n) gives A241982.
Row sums give A000312.
Main diagonal gives A000142(n-1) for n>0.
Cf. A246049, A243098.

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):
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..10);

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, {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, Min[j, k]], {j, 0, n}]; T[0, 0] = 1; T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 06 2015, after Alois P. Heinz *)

A057817 Moebius invariant of cographic hyperplane arrangement for complete graph K_n. Also value of Tutte dichromatic polynomial T_G(0,1) for G=K_n. Also alternating sum F_{n,1} - F_{n,2} + F_{n,3} - ..., where F_{n,k} is the number of labeled forests on n nodes with k connected components.

Original entry on oeis.org

1, 0, 1, 6, 51, 560, 7575, 122052, 2285353, 48803904, 1171278945, 31220505800, 915350812299, 29281681800384, 1015074250155511, 37909738774479600, 1517587042234033425, 64830903253553212928, 2944016994706445303937

Offset: 1

Alex Postnikov (apost(AT)math.mit.edu), Nov 06 2000

The rank of reduced homology groups for the matroid complex of acyclic subgraphs in complete graph K_n (n>1). It is also the number of labeled edge-rooted forests on n-1 nodes where each connected component contains at least one edge.

The description of this sequence as the number of labeled edge-rooted forests on n-1 nodes appeared in W. Kook's Ph.D. thesis (G. Carlsson, advisor), Categories of acyclic graphs and automorphisms of free groups, Stanford University, 1996.

			For n=4, the number of labeled edge-rooted forests on three (= n-1) nodes is 6: There are 3 labeled trees on three nodes. These are the only forests with at least one edge in each connected component. Each tree has 2 edges and each of the two may be marked as the root.

W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford University, 1996

Vincenzo Librandi, Table of n, a(n) for n = 1..200
I. Novik, A. Postnikov and B. Sturmfels, Syzygies of oriented matroids, arXiv:math/0009241 [math.CO], 2000.
A. Postnikov, Papers

Cf. A053506, A060917, A060918.

Cf. column k=2 of A243098.

for n from 1 to 50 do printf(`%d,`, (n-1)*sum((n-2)!/(2^k*k!*(n-2-2*k)!)*n^(n-2-2*k), k=0..floor((n-2)/2))) od:

s=20;(*generates first s terms starting from n=2*) K := Exp[Sum[(m-1)*(m^(m-2))*(x^m)/m!, {m, 2, 2s}]]; S := Series[K, {x, 0, s}]; h[i_] := SeriesCoefficient[S, i-1]*(i-1)!; Table[h[n+1], {n, s}]
a[n_] := (n-2)*Sum[ (n-1)^(n-2k-3)*(n-3)! / (2^k*k!*(n-2k-3)!), {k, 0, Floor[ (n-3)/ 2 ]}]; a[1] = 1; Table[a[n], {n, 1, 19}] (* Jean-François Alcover, Dec 11 2012, after Maple *)

a(n)=if(n<1,0,(n-1)!*polcoeff(exp(sum(k=1,n-1,k^(k-1)*x^k/k!,O(x^n))^2/2),n-1))

a(n)=if(n<2,n==1,sum(k=0,(n-3)\2,(n-1)!/(2^k*k!*(n-3-2*k)!)*(n-1)^(n-4-2*k)))

df(n)=(2*n)!/(n!*2^n);  \\ A001147
he(n,x)=x^n+sum(k=1, n\2, binomial(n,2*k) * df(k) * x^(n-2*k) );
a(n)=if( n<3, n==1, (n-2)*he(n-3, n-1) );
/* Joerg Arndt, May 06 2013 */

E.g.f.: exp(1/2*LambertW(-x)^2). - Vladeta Jovovic, Apr 10 2001
E.g.f.: integral exp( Sum_{m>1}(m-1)*m^{m-2}*x^{m}/m!) dx (n-1) Sum_{k=0}^{[(n-2)/2]} binomial((n-2)! , 2^k k! (n-2-2k)!) n^{n-2-2k}.
E.g.f.: exp( Sum_{m>1}(m-1)*m^{m-2}*x^{m}/m!).
E.g.f.: integral(exp(1/2*LambertW(-x)^2)dx). - Vladeta Jovovic, Apr 10 2001
a(n) ~ exp(-1/2)*n^(n-2). - Vaclav Kotesovec, Dec 12 2012
a(n) = n^(n-2) - Sum_{k=1..n-1} binomial(n-1,k-1) * k^(k-2) * a(n-k). - Ilya Gutkovskiy, Feb 07 2020

More terms from James Sellers, Nov 08 2000
Additional comments from Woong Kook (andrewk(AT)math.uri.edu), Feb 12 2002
Further comments from Michael Somos, Sep 18 2002
Updated author's URL and e-mail address R. J. Mathar, May 23 2010

A060917 Expansion of e.g.f.: exp((-1)^k/k*LambertW(-x)^k)/(k-1)!, k=3.

Original entry on oeis.org

1, 12, 150, 2180, 36855, 715008, 15697948, 385300800, 10463945085, 311697869120, 10108450408914, 354630018043392, 13384651003544275, 540860323696035840, 23300648262667635960, 1066165291831917811712

Offset: 3

Vladeta Jovovic, Apr 10 2001

a(n) = A243098(n,3)/2. - Alois P. Heinz, Aug 19 2014

Vincenzo Librandi, Table of n, a(n) for n = 3..200

Cf. A057817, A060918, A243098.

nn = 20; CoefficientList[Series[E^(-1/3*LambertW[-x]^3)/2, {x, 0, nn}], x]* Range[0, nn]! (* Vaclav Kotesovec, Nov 27 2012 *)

x='x+O('x^30); Vec(serlaplace(exp(-lambertw(-x)^3/3)/2 - 1/2)) \\ G. C. Greubel, Feb 19 2018

a(n) = (n-1)!/(k-1)!*Sum_{i=0..floor((n-k)/k)} 1/(i!*k^i)*n^(n-(i+1)*k)/(n-(i+1)*k)!, k=3.

a(n) ~ 1/2*exp(1/3)*n^(n-1). - Vaclav Kotesovec, Nov 27 2012

A060918 Expansion of e.g.f.: exp((-1)^k/k*LambertW(-x)^k)/(k-1)!, k=4.

Original entry on oeis.org

1, 20, 360, 6860, 143570, 3321864, 84756000, 2372001720, 72384192540, 2394775746220, 85443353291296, 3271908306712500, 133893717061821080, 5832748749666611920, 269542701201588099840, 13172225935626444660144, 678788199609330554538000, 36790272488566573278647940

Offset: 4

Vladeta Jovovic, Apr 10 2001

a(n) = A243098(n,4)/6. - Alois P. Heinz, Aug 19 2014

Vincenzo Librandi, Table of n, a(n) for n = 4..200

Cf. A057817, A060917, A243098.

CoefficientList[Series[E^(1/4*LambertW[-x]^4)/6, {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *)

x='x+O('x^30); Vec(serlaplace(exp(lambertw(-x)^4/4)/3! - 1/3!)) \\ G. C. Greubel, Feb 19 2018

a(n) = (n-1)!/(k-1)!*Sum_{i=0..floor((n-k)/k)} 1/(i!*k^i)*n^(n-(i+1)*k)/(n-(i+1)*k)!, k=4.

a(n) ~ 1/6*exp(1/4)*n^(n-1). - Vaclav Kotesovec, Nov 27 2012

A241980 Number of endofunctions on [n] where all cycle lengths are equal.

Original entry on oeis.org

1, 1, 4, 24, 206, 2300, 31742, 522466, 9996478, 218088504, 5344652492, 145386399554, 4347272984936, 141737636485588, 5004538251283846, 190247639729155110, 7747479351505166738, 336492490519027631984, 15526758954835131888980, 758548951300064645742034

Offset: 0

Alois P. Heinz, Aug 10 2014

nonn

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

Cf. A005225, A061356, A212789, A242027 (column k=1).

Row sums of A243098.

with(numtheory):
b:= n-> `if`(n=0, 1, n!*add((d!*(n/d)^d)^(-1), d=divisors(n))):
a:= n-> add(binomial(n-1, j-1)*n^(n-j)*b(j), j=0..n):
seq(a(n), n=0..25);

nn=20;t[x_]:=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[Series[1+Sum[Exp[t[x]^i/i]-1,{i,1,nn}],{x,0,nn}],x] (* Geoffrey Critzer, Aug 11 2014 *)

a(n) = Sum_{j=0..n} C(n-1,j-1) * n^(n-j) * A005225(j).

a(n) = Sum_{k=0..n} A243098(n,k).

A246050 Number of endofunctions on [2n] where the smallest cycle length equals n.

Original entry on oeis.org

1, 3, 51, 4360, 861420, 302472576, 165549605760, 130241382036480, 139296260790086400, 194427690066299289600, 343266609438110040883200, 747889929370001008617062400, 1971026055567996899374212710400, 6180432763819774878006029844480000

Offset: 0

Alois P. Heinz, Aug 11 2014

nonn

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

Cf. A241982, A246049, 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):
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] = If[n == 0, 1, If[i>n, 0, Sum[(i-1)!^j*multinomial[n, Join[{n-i*j}, Array[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}]; a[n_] := If[n == 0, 1, A[2*n, n] - A[2*n, n+1]]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Feb 11 2015, after Alois P. Heinz *)

a(n) = A246049(2n,n) = A243098(2n,n).

a(n) ~ 2^(3*n-1/2) * n^(2*n-1) / exp(n). - Vaclav Kotesovec, Aug 19 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

A241981 Number T(n,k) of endofunctions on [n] where the largest 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

A057817 Moebius invariant of cographic hyperplane arrangement for complete graph K_n. Also value of Tutte dichromatic polynomial T_G(0,1) for G=K_n. Also alternating sum F_{n,1} - F_{n,2} + F_{n,3} - ..., where F_{n,k} is the number of labeled forests on n nodes with k connected components.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A060917 Expansion of e.g.f.: exp((-1)^k/k*LambertW(-x)^k)/(k-1)!, k=3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A060918 Expansion of e.g.f.: exp((-1)^k/k*LambertW(-x)^k)/(k-1)!, k=4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A241980 Number of endofunctions on [n] where all cycle lengths are equal.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A246050 Number of endofunctions on [2n] where the smallest cycle length equals n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple