

A058127


Triangle read by rows: T(j,k) = number of acyclic functions from {1,...,j} to {1,...,k}. For n >= 1, a(n) = (kj)*k^(j1), where k is such that C(k,2) < n <= C(k+1,2) and j = (n1) mod C(k,2). Alternatively, table T(k,j) read by antidiagonals with k >= 1, 0 <= j <= k: T(k,j) = number of acyclicfunction digraphs on k vertices with j vertices of outdegree 1 and (kj) vertices of outdegree 0; T(k,j) = (kj)*k^(j1).


7



1, 1, 1, 1, 2, 3, 1, 3, 8, 16, 1, 4, 15, 50, 125, 1, 5, 24, 108, 432, 1296, 1, 6, 35, 196, 1029, 4802, 16807, 1, 7, 48, 320, 2048, 12288, 65536, 262144, 1, 8, 63, 486, 3645, 26244, 177147, 1062882, 4782969, 1, 9, 80, 700, 6000, 50000, 400000, 3000000, 20000000, 100000000
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

An acyclic function f from domain D={1,...,j} to codomain C={1,...,k} is a function such that, for every subset A of D, f(A) does not equal A. Equivalently, an acyclic function f "eventually sends" under successive composition all elements of D to {j+1,...,k}. An acyclicfunction digraph G is a labeled directed graph that satisfies (i) all vertices have outdegree 0 or 1; (ii) if vertex x has outdegree 0 and vertex y has outdegree 1, then x > y; (iii) G has no cycles and no loops. There is a onetoone correspondence between acyclic functions from D to C and acyclicfunction digraphs with j vertices of outdegree 1 and jk vertices of outdegree 0.
nth row of the triangle is the nth iterate of "perform binomial transform operation" (bto) on current row to get next row, extracting the leftmost n terms for nth row. (i.e., all terms left of the zero). First row is (bto): [1, 1, 0, 0, 0, ...]. 5th row is 1, 4, 15, 50, 125, since (bto) performed 5 times iteratively on [1, 1, 0, 0, 0 ...] = 1, 4, 15, 50, 125, 0, 31, ...  Gary W. Adamson, Apr 30 2005
T(k,j) can be shown to be equal to the number of spanning trees of the complete graph on k vertices that contain a specific subtree with kj1 edges.  John L. Chiarelli, Oct 04 2016


LINKS

T. D. Noe, Rows n=1..50 of triangle, flattened
D. P. Walsh, Notes on acyclic functions and their directed graphs


FORMULA

For fixed m = kj, a(n) = T(k, j) = T(m+j, j) = m*(m+j)^(j1). Exponential generating function g for T(m+j, j) = m*(m+j)^(j1) is given by g(t) = exp(m*W(t)), where W denotes the principal branch of Lambert's W function. Lambert's W function satisfies W(t)*exp(W(t)) = t for t >= exp(1).
T(n, k) = Sum_{i=0..k} T(n1, i) * binomial(k, i) if k<n.  Michael Somos, Sep 20 2017


EXAMPLE

a(6) = T(3,2) = 3 because there are 3 acyclic functions from {1,2} to {1,2,3}: {(1,2),(2,3)}, {(1,3),(2,3)} and {(1,3),(2,1)}.
Triangle begins:
1,
1, 1,
1, 2, 3,
1, 3, 8, 16,
1, 4, 15, 50, 125,
1, 5, 24, 108, 432, 1296,
1, 6, 35, 196, 1029, 4802, 16807,
1, 7, 48, 320, 2048, 12288, 65536, 262144,
...


MAPLE

T := proc(n, k) (nk)*n^(k1) end; seq(print(seq(T(n, k), k=0..n1)), n=1..9); # Peter Luschny, Jan 14 2009


MATHEMATICA

t[n_, k_] := (nk)*n^(k1); Table[t[n, k], {n, 1, 10}, {k, 0, n1}] // Flatten (* JeanFrançois Alcover, Dec 03 2013 *)


PROG

(MAGMA) /* As triangle */ [[(nk)*n^(k1): k in [0..n1]]: n in [1.. 10]]; // Vincenzo Librandi, Aug 11 2017
(PARI) {T(n, k) = if( k<0  k>n, 0, n==0, 1, (nk) * n^(k1))}; /* Michael Somos, Sep 20 2017 */


CROSSREFS

The sum of antidiagonals is A058128. The sequence b(n) = T(n, n1) for n >= 1 is A000272, labeled trees on n nodes.
The sequence c(n) = T(n, n2) for n >= 2 is A007334(n). The sequence d(n) = T(n, n3) for n >= 3 is A089463(n3,0).  Peter Luschny, Apr 22 2009
Sequence in context: A119011 A130477 A226513 * A244490 A133935 A139633
Adjacent sequences: A058124 A058125 A058126 * A058128 A058129 A058130


KEYWORD

nice,nonn,tabl


AUTHOR

Dennis P. Walsh, Nov 14 2000


EXTENSIONS

a(32) corrected by T. D. Noe, Jan 25 2008


STATUS

approved



