A060281 Triangle T(n,k) read by rows giving number of labeled mappings (or functional digraphs) from n points to themselves (endofunctions) with exactly k cycles, k=1..n.
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
Offset: 1
Examples
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) = 3*y + y^2;
t_3(y) = 17*y + 9*y^2 + y^3; (End)
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 and Geoffrey Smith, Tight Bounds on Information Leakage from Repeated Independent Runs, 2017 IEEE 30th Computer Security Foundations Symposium (CSF).
Crossrefs
Programs
-
Magma
A060281:= func< n,k | (&+[Binomial(n-1,j)*n^(n-1-j)*(-1)^(k+j+1)*StirlingFirst(j+1,k): j in [0..n-1]]) >; [A060281(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Nov 06 2024
-
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 *) -
SageMath
@CachedFunction def A060281(n,k): return sum(binomial(n-1,j)*n^(n-1-j)*stirling_number1(j+1,k) for j in range(n)) flatten([[A060281(n,k) for k in range(1,n+1)] for n in range(1,13)]) # G. C. Greubel, Nov 06 2024
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
T(2*n, n) = A273442(n), n >= 1. - Alois P. Heinz, May 22 2016
From Alois P. Heinz, Dec 17 2021: (Start)
Sum_{k=1..n} k * T(n,k) = A190314(n).
Sum_{k=1..n} (-1)^(k+1) * T(n,k) = A000169(n) for n>=1. (End)
Comments