A060918 -id:A060918

Search: a060918 -id:a060918

Displaying 1-3 of 3 results found.

page 1

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.

+10
8

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

T(0,0) = 1 by convention.

LINKS

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

FORMULA

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

EXAMPLE

Triangle T(n,k) begins:

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;

...

MAPLE

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

MATHEMATICA

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

CROSSREFS

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.

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Aug 18 2014

STATUS

approved

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.

+10
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

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.

REFERENCES

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

LINKS

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

FORMULA

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

EXAMPLE

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.

MAPLE

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:

MATHEMATICA

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

PROG

(PARI) 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))

(PARI) 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)))

(PARI)

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

CROSSREFS

Cf. A053506, A060917, A060918.

Cf. column k=2 of A243098.

KEYWORD

nonn,nice,easy

AUTHOR

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

EXTENSIONS

More terms from James A. 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

STATUS

approved

A060917

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

+10
4

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

3,2

COMMENTS

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

LINKS

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

FORMULA

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

MATHEMATICA

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

PROG

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

CROSSREFS

Cf. A057817, A060918, A243098.

KEYWORD

easy,nonn

AUTHOR

Vladeta Jovovic, Apr 10 2001

STATUS

approved

page 1

Search completed in 0.104 seconds