|
Search: id:A058127
|
|
|
| A058127 |
|
Triangle read by rows: T(j,k) = number of acyclic functions from {1,...,j} to {1,...,k}. For n >= 1, a(n)=(k-j)*k^(j-1), where k is such that C(k,2) < n <= C(k+1,2) and j=(n-1)mod[C(k,2)]. Alternatively, table T(k,j) read by antidiagonals with k >= 1, 0<=j<=k: T(k,j)=number of acyclic-function digraphs on k vertices with j vertices of outdegree 1 and (k-j) vertices of outdegree 0; T(k,j)=(k-j)*k^(j-1). |
|
+0
4
|
|
| 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
(list; table; graph; listen)
|
|
|
OFFSET
|
1,5
|
|
|
COMMENT
|
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 acyclic-function 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 one-to-one correspondence between acyclic functions from D to C and acyclic-function digraphs with j vertices of outdegree 1 and j-k vertices of outdegree 0.
n-th row of the triangle is the n-th iterate of "perform binomial transform operation" (bto) on current row to get next row, extracting the leftmost n terms for n-th row. (i.e. all terms left of the zero). First row is (bto): [1, -1, 0, 0, 0...]. 5-th 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 (qntmpkt(AT)yahoo.com), Apr 30 2005
|
|
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=k-j, a(n)=T(k, j)=T(m+j, j)=m*(m+j)^(j-1). Exponential generating function g for T(m+j, j)=m*(m+j)^(j-1) 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).
|
|
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)}.
|
|
CROSSREFS
|
The sum of antidiagonals is A058128. The sequence b(n)=T(n, n-1) for n >= 1 is A000272, labeled trees on n nodes.
Adjacent sequences: A058124 A058125 A058126 this_sequence A058128 A058129 A058130
Sequence in context: A093768 A119011 A130477 this_sequence A133935 A139633 A134319
|
|
KEYWORD
|
nice,nonn,tabl
|
|
AUTHOR
|
Dennis P. Walsh (dwalsh(AT)mtsu.edu), Nov 14 2000
|
|
EXTENSIONS
|
a(32) corrected by T. D. Noe, Jan 25 2008
|
|
|
Search completed in 0.002 seconds
|
