cp's OEIS Frontend

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.

%I A060281 #59 Nov 06 2024 04:30:48
%S A060281 1,3,1,17,9,1,142,95,18,1,1569,1220,305,30,1,21576,18694,5595,745,45,
%T A060281 1,355081,334369,113974,18515,1540,63,1,6805296,6852460,2581964,
%U A060281 484729,49840,2842,84,1,148869153,158479488,64727522,13591116,1632099,116172,4830,108,1
%N 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.
%C A060281 Also called sagittal graphs.
%C A060281 T(n,k)=1 iff n=k (counts the identity mapping of [n]). - _Len Smiley_, Apr 03 2006
%C A060281 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
%D A060281 I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.
%D A060281 W. Szpankowski. Average case analysis of algorithms on sequences. John Wiley & Sons, 2001. - _Peter Luschny_, Mar 03 2009
%H A060281 Alois P. Heinz, <a href="/A060281/b060281.txt">Rows n = 1..141, flattened</a>
%H A060281 Julia Handl and Joshua Knowles, <a href="http://dx.doi.org/10.1007/11844297_85">An Investigation of Representations and Operators for Evolutionary Data Clustering with a Variable Number of Clusters</a>, 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]
%H A060281 D. E. Knuth, <a href="http://arxiv.org/abs/math/9207221">Convolution polynomials</a>, The Mathematica J., 2 (1992), 67-78.
%H A060281 D. E. Knuth and B. Pittel, <a href="http://www.jstor.org/stable/2046947">A recurrence related to trees</a>, Proceedings of the American Mathematical Society, 105(2):335-349, 1989. [From _Peter Luschny_, Mar 03 2009]
%H A060281 J. Riordan, <a href="http://dx.doi.org/10.1214/aoms/1177704722">Enumeration of Linear Graphs for Mappings of Finite Sets</a>, Ann. Math. Stat., 33, No. 1, Mar. 1962, pp. 178-185.
%H A060281 David M. Smith and Geoffrey Smith, <a href="https://doi.org/10.1109/CSF.2017.18">Tight Bounds on Information Leakage from Repeated Independent Runs</a>, 2017 IEEE 30th Computer Security Foundations Symposium (CSF).
%F A060281 E.g.f.: 1/(1 + LambertW(-x))^y.
%F A060281 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
%F A060281 T(2*n, n) = A273442(n), n >= 1. -  _Alois P. Heinz_, May 22 2016
%F A060281 From _Alois P. Heinz_, Dec 17 2021: (Start)
%F A060281 Sum_{k=1..n} k * T(n,k) = A190314(n).
%F A060281 Sum_{k=1..n} (-1)^(k+1) * T(n,k) = A000169(n) for n>=1. (End)
%e A060281 Triangle T(n,k) begins:
%e A060281         1;
%e A060281         3,       1;
%e A060281        17,       9,       1;
%e A060281       142,      95,      18,      1;
%e A060281      1569,    1220,     305,     30,     1;
%e A060281     21576,   18694,    5595,    745,    45,    1;
%e A060281    355081,  334369,  113974,  18515,  1540,   63,  1;
%e A060281   6805296, 6852460, 2581964, 484729, 49840, 2842, 84, 1;
%e A060281   ...
%e A060281 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)].
%e A060281 From _Peter Luschny_, Mar 03 2009: (Start)
%e A060281   Tree polynomials (with offset 0):
%e A060281   t_0(y) = 1;
%e A060281   t_1(y) = y;
%e A060281   t_2(y) = 3*y + y^2;
%e A060281   t_3(y) = 17*y + 9*y^2 + y^3; (End)
%p A060281 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
%p A060281 From _Peter Luschny_, Mar 03 2009: (Start)
%p A060281 T := z -> sum(n^(n-1)*z^n/n!,n=1..16):
%p A060281 p := convert(simplify(series((1-T(z))^(-y),z,12)),'polynom'):
%p A060281 seq(print(coeff(p,z,i)*i!),i=0..8); (End)
%t A060281 t=Sum[n^(n-1) x^n/n!,{n,1,10}];
%t A060281 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*)
%t A060281 Table[k! SeriesCoefficient[1/(1 + ProductLog[-t])^x, {t, 0, k}, {x, 0, j}], {k, 10}, {j, k}] (* _Jan Mangaldan_, Mar 02 2013 *)
%o A060281 (Magma)
%o A060281 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]]) >;
%o A060281 [A060281(n,k): k in [1..n], n in [1..12]]; // _G. C. Greubel_, Nov 06 2024
%o A060281 (SageMath)
%o A060281 @CachedFunction
%o A060281 def A060281(n,k): return sum(binomial(n-1,j)*n^(n-1-j)*stirling_number1(j+1,k) for j in range(n))
%o A060281 flatten([[A060281(n,k) for k in range(1,n+1)] for n in range(1,13)]) # _G. C. Greubel_, Nov 06 2024
%Y A060281 Columns k=1-10 give: A001865, A065456, A273434, A273435, A273436, A273437, A273438, A273439, A273440, A273441.
%Y A060281 Row sums: A000312.
%Y A060281 Main diagonal and first lower diagonal give: A000012, A045943.
%Y A060281 Cf. A000169, A190314, A242027, A209324, A273442, A347999.
%K A060281 easy,nonn,tabl
%O A060281 1,2
%A A060281 _Vladeta Jovovic_, Apr 09 2001