Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #23 Dec 22 2024 09:08:05
%S 0,0,0,0,1,0,0,1,2,0,0,1,2,6,0,0,1,2,9,24,0,0,1,2,9,60,120,0,0,1,2,9,
%T 64,540,720,0,0,1,2,9,64,620,6120,5040,0,0,1,2,9,64,625,7620,83790,
%U 40320,0,0,1,2,9,64,625,7770,113610,1345680,362880,0,0,1,2,9,64,625,7776,117390,1992480,24811920,3628800,0
%N Square array whose entry A(n,k) is the number of labeled rooted trees on a set of size n where each node has at most k neighbors that are further away from the root than the node itself, for n >= 0, k >= 0, read by descending antidiagonals.
%C A preimage constraint on a function is a set of nonnegative integers such that the size of the inverse image of any element is one of the values in that set. View a labeled rooted tree as an endofunction on the set {1,2,...,n} by sending every non-root node to its neighbor that is closer to the root and sending the root to itself.
%C Thus, A(n,k) is the number of endofunctions on a set of size n with exactly one cyclic point and such that each preimage has at most k entries.
%H B. Otto, <a href="https://arxiv.org/abs/1903.00542">Coalescence under Preimage Constraints</a>, arXiv:1903.00542 [math.CO], 2019, Corollaries 5.3 and 7.8.
%F A(n,k) = (n-1)! * [x^(n-1)] e_k(x)^n, where e_k(x) is the truncated exponential 1 + x + x^2/2! + ... + x^k/k!. When k>1, the link above yields explicit constants c_k, r_k so that the columns are asymptotically c_k * n^(-3/2) * r_k^-n. Stirling's approximation gives column k=1, and column k=0 is 0.
%e Array begins:
%e 0 0 0 0 0 ...
%e 0 1 1 1 1 ...
%e 0 2 2 2 2 ...
%e 0 6 9 9 9 ...
%e 0 24 60 64 64 ...
%e 0 120 540 620 625 ...
%e 0 720 6120 7620 7770 ...
%e 0 5040 83790 113610 117390 ...
%e 0 40320 1345680 1992480 2088520 ...
%e 0 362880 24811920 40194000 42771960 ...
%e 0 3628800 516650400 916927200 991090800 ...
%e 0 39916800 11992503600 23341071600 25635767850 ...
%e ...
%t e[k_][x_] := Sum[x^j/j!, {j, 0, k}];
%t A[0, _] = A[_, 0] = 0; A[n_, k_] := (n-1)! Coefficient[e[k][x]^n, x, n-1];
%t Table[A[n-k, k], {n, 0, 11}, {k, n, 0, -1}] (* _Jean-François Alcover_, Jul 06 2019 *)
%o (Python)
%o # print first num_entries entries in column k
%o import math, sympy; x=sympy.symbols('x')
%o k=5; num_entries = 64
%o P=range(k+1); eP=sum([x**d/math.factorial(d) for d in P]); r = [0,1]; curr_pow = eP
%o for term in range(1, num_entries-1):
%o curr_pow=(curr_pow*eP).expand()
%o r.append(curr_pow.coeff(x**term)*math.factorial(term))
%o print(r)
%Y Column 0: A000004.
%Y Column 1 is A000142, except at n=0 term.
%Y Columns 2-9: A036774, A036775, A036776, A036777, A325205, A325206, A325207, A325208.
%Y A(n,n) gives A152917.
%Y Similar array for arbitrary endofunctions (without limitation on the number of cyclic points) with the same preimage condition {i>=0 | i<=k}: A306800.
%K easy,nonn,tabl
%O 1,9
%A _Benjamin Otto_, Apr 08 2019