A127119 Triangle read by rows: T(n,k) = number of endofunctions on a set with n elements, where the maximum indegree is k.

1, 2, 1, 3, 3, 1, 5, 10, 3, 1, 7, 24, 12, 3, 1, 11, 64, 39, 12, 3, 1, 15, 149, 122, 41, 12, 3, 1, 22, 366, 368, 138, 41, 12, 3, 1, 30, 857, 1092, 439, 140, 41, 12, 3, 1, 42, 2050, 3179, 1395, 455, 140, 41, 12, 3, 1, 56, 4828, 9160, 4326, 1467, 457, 140, 41, 12, 3, 1

Offset

1,2

Comments

The number of endofunctions with indegree <= k is given by the Euler transform of the number of connected endofunctions with indegree <= k. - Andrew Howroyd, Feb 21 2020

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Example

For n = 3, the 7 endofunctions are (1,2,3) -> (1,1,1), (1,1,2), (1,2,1), (2,1,1), (1,2,3), (1,3,2) and (2,3,1). In the first, node 1 has indegree 3, the next 3 have node 1 with indegree 2 and the final 3 are permutations, each node having indegree 1. So row 3 of the triangle is 3,3,1.
The triangle starts:
1
2 1
3 3 1
5 10 3 1
7 24 12 3 1

Prog

(PARI) \\ Here R(n, k) gives column k of A299038 as series.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
MSetUptoK(g, k)={my(n=serprec(g, x)); polcoef(if(k==0, 1, exp( sum(i=1, k, (y^i + O(y*y^k))*subst(g + O(x*x^(n\i)), x, x^i)/i )))/(1 - y) + O(y*y^k), k, y) + O(x^n)}
CIK(p, n)={sum(d=1, n, eulerphi(d)/d*log(subst(1/(1+O(x*x^(n\d))-p), x, x^d)))}
R(n, k)={my(p=O(x)); for(n=1, n, p=x*MSetUptoK(p, k)); p}
F(n)={my(M=Mat(vector(n, k, EulerT(Vec(CIK(x*MSetUptoK(R(n, k), k-1), n)))~))); M-matconcat([vectorv(#M), M[, 1..n-1]])}
{ my(A=F(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Feb 21 2020

Crossrefs

Cf. A127120, A299038.

Sequence in context: A122075 A185675 A153341 * A322265 A066704 A262917

Adjacent sequences: A127116 A127117 A127118 * A127120 A127121 A127122

Keyword

nonn,tabl

Author

Franklin T. Adams-Watters, Jan 05 2007

Extensions

Terms a(46) and beyond from Andrew Howroyd, Feb 21 2020

Status

approved