login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060281 Triangle T(n,k) read by rows giving number of labeled mappings (or functional digraphs) from n points to themselves (endofunctions) with k cycles, k=1..n. 20
1, 3, 1, 17, 9, 1, 142, 95, 18, 1, 1569, 1220, 305, 30, 1, 21576, 18694, 5595, 745, 45, 1, 355081, 334369, 113974, 18515, 1540, 63, 1, 6805296, 6852460, 2581964, 484729, 49840, 2842, 84, 1, 148869153, 158479488, 64727522, 13591116, 1632099, 116172, 4830, 108, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Also called sagittal graphs.

T(n,k)=1 iff n=k (counts the identity mapping of [n]). - Len Smiley, Apr 03 2006

Also the coefficients of the tree polynomials t_{n}(y) defined by (1-T(z))^(-y) = Sum_{n>=0} t_{n}(y) (z^n/n!) where T(z) is Cayley's tree function T(z) = Sum_{n>=1} n^(n-1) (z^n/n!) giving the number of labeled trees A000169. - Peter Luschny, Mar 03 2009

REFERENCES

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

W. Szpankowski. Average case analysis of algorithms on sequences. John Wiley & Sons, 2001. - Peter Luschny, Mar 03 2009

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

Julia Handl and Joshua Knowles, An Investigation of Representations and Operators for Evolutionary Data Clustering with a Variable Number of Clusters, in Parallel Problem Solving from Nature-PPSN IX, Lecture Notes in Computer Science, Volume 4193/2006, Springer-Verlag. [From N. J. A. Sloane, Jul 09 2009]

D. E. Knuth, Convolution polynomials, The Mathematica J., 2 (1992), 67-78.

D. E. Knuth and B. Pittel, A recurrence related to trees, Proceedings of the American Mathematical Society, 105(2):335-349, 1989. [From Peter Luschny, Mar 03 2009]

J. Riordan, Enumeration of Linear Graphs for Mappings of Finite Sets, Ann. Math. Stat., 33, No. 1, Mar. 1962, pp. 178-185.

David M. Smith, Geoffrey Smith, Tight Bounds on Information Leakage from Repeated Independent Runs, 2017 IEEE 30th Computer Security Foundations Symposium (CSF).

FORMULA

E.g.f.: 1/(1 + LambertW(-x))^y.

T(n,k) = Sum_{j=0..n-1} C(n-1,j)*n^(n-1-j)*(-1)^(k+j+1)*A008275(j+1,k) = Sum_{j=0..n-1} binomial(n-1,j)*n^(n-1-j)*s(j+1,k). [Riordan] (Note: s(m,p) denotes signless Stirling cycle number (first kind), A008275 is the signed triangle.) - Len Smiley, Apr 03 2006

EXAMPLE

Triangle T(n,k) begins:

:       1;

:       3,       1;

:      17,       9,       1;

:     142,      95,      18,      1;

:    1569,    1220,     305,     30,     1;

:   21576,   18694,    5595,    745,    45,    1;

:  355081,  334369,  113974,  18515,  1540,   63,  1;

: 6805296, 6852460, 2581964, 484729, 49840, 2842, 84, 1;

: ...

T(3,2)=9: (1,2,3)--> [(2,1,3),(3,2,1),(1,3,2),(1,1,3),(1,2,1), (1,2,2),(2,2,3),(3,2,3),(1,3,3)].

From Peter Luschny, Mar 03 2009: (Start)

Tree polynomials (with offset 0):

t_0(y) = 1;

t_1(y) = y;

t_2(y) = 3y + y^2;

t_3(y) = 17y + 9y^2 + y^3; (End)

MAPLE

with(combinat):T:=array(1..8, 1..8):for m from 1 to 8 do for p from 1 to m do T[m, p]:=sum(binomial(m-1, k)*m^(m-1-k)*(-1)^(p+k+1)*stirling1(k+1, p), k=0..m-1); print(T[m, p]) od od; # Len Smiley, Apr 03 2006

From Peter Luschny, Mar 03 2009: (Start)

T := z -> sum(n^(n-1)*z^n/n!, n=1..16):

p := convert(simplify(series((1-T(z))^(-y), z, 12)), 'polynom'):

seq(print(coeff(p, z, i)*i!), i=0..8); (End)

MATHEMATICA

t=Sum[n^(n-1) x^n/n!, {n, 1, 10}];

Transpose[Table[Rest[Range[0, 10]! CoefficientList[Series[Log[1/(1 - t)]^n/n!, {x, 0, 10}], x]], {n, 1, 10}]]//Grid (* Geoffrey Critzer, Mar 13 2011*)

Table[k! SeriesCoefficient[1/(1 + ProductLog[-t])^x, {t, 0, k}, {x, 0, j}], {k, 10}, {j, k}] (* Jan Mangaldan, Mar 02 2013 *)

CROSSREFS

Row sums: A000312.

Columns k=1-10 give: A001865, A065456, A273434, A273435, A273436, A273437, A273438, A273439, A273440, A273441.

Main diagonal and first lower diagonal give: A000012, A045943.

T(2n,n) gives A273442.

Cf. A242027.

Sequence in context: A259686 A162313 A188645 * A151918 A089974 A143849

Adjacent sequences:  A060278 A060279 A060280 * A060282 A060283 A060284

KEYWORD

easy,nonn,tabl

AUTHOR

Vladeta Jovovic, Apr 09 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 08:23 EDT 2018. Contains 315270 sequences. (Running on oeis4.)