login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 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 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, ...]. 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 k-j-1 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 = 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).

T(n, k) = Sum_{i=0..k} T(n-1, 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) (n-k)*n^(k-1) end; seq(print(seq(T(n, k), k=0..n-1)), n=1..9); # Peter Luschny, Jan 14 2009

MATHEMATICA

t[n_, k_] := (n-k)*n^(k-1); Table[t[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-Fran├žois Alcover, Dec 03 2013 *)

PROG

(MAGMA) /* As triangle */ [[(n-k)*n^(k-1): k in [0..n-1]]: n in [1.. 10]]; // Vincenzo Librandi, Aug 11 2017

(PARI) {T(n, k) = if( k<0 || k>n, 0, n==0, 1, (n-k) * n^(k-1))}; /* Michael Somos, Sep 20 2017 */

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.

The sequence c(n) = T(n, n-2) for n >= 2 is A007334(n). The sequence d(n) = T(n, n-3) for n >= 3 is A089463(n-3,0). - Peter Luschny, Apr 22 2009

Sequence in context: A300866 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 14:25 EDT 2018. Contains 316281 sequences. (Running on oeis4.)