A089463 -id:A089463 - cp's OEIS frontend

A089464 Hyperbinomial transform of A089461. Also the row sums of triangle A089463, which lists the coefficients for the third hyperbinomial transform.

1, 4, 22, 163, 1564, 18679, 268714, 4538209, 88188280, 1940666635, 47744244286, 1299383450941, 38777402351476, 1259552677645903, 44247546748659130, 1671904534990870369, 67624237153933934704, 2915628368081840175379, 133499617770334938670198

Offset: 0

Paul D. Hanna, Nov 05 2003

nonn

a(n) is also the number of subtrees of the complete graph K_{n+2} which contain 2 fixed adjacent edges (i.e. a fixed K_{1,2}). For n=2, the a(2)=4 solutions are the 4 subtrees of K_4 which contain 2 fixed adjacent edges (i.e. those 2 edges, 1 copy of K_{1,3}, and 2 copies of P_4). - Kellie J. MacPhee, Jul 25 2013

Alois P. Heinz, Table of n, a(n) for n = 0..150

Cf. A089461, A089463 (triangle).

Column k=3 of A144303.

a:= n-> add(3*(n-j+3)^(n-j-1)*binomial(n,j), j=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Oct 30 2012

Table[Sum[3(n-k+3)^(n-k-1) Binomial[n,k],{k,0,n}],{n,0,20}] (* Harvey P. Dale, Dec 04 2011 *)
CoefficientList[Series[E^x*(-LambertW[-x]/x)^3, {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Jul 08 2013 *)

x='x+O('x^50); Vec(serlaplace(exp(x)*(-lambertw(-x)/x)^3)) \\ G. C. Greubel, Nov 16 2017

a(n) = Sum_{k=0..n} 3*(n-k+3)^(n-k-1)*C(n, k).
E.g.f.: exp(x)*(-LambertW(-x)/x)^3.
a(n) ~ 3*exp(3+exp(-1))*n^(n-1). - Vaclav Kotesovec, Jul 08 2013

A058127 Triangle read by rows: T(j,k) is the 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).

Original entry on oeis.org

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

Offset: 1

Dennis P. Walsh, Nov 14 2000

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
T(k-1, j-1) is also the number of parking functions with j cars and k spots (see Theorem 2.2 in Kenyon and Yin). - Stefano Spezia, Apr 09 2021

			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;
  ...

T. D. Noe, Rows n = 1..50 of triangle, flattened
Richard Kenyon and Mei Yin, Parking functions: From combinatorics to probability, arXiv:2103.17180 [math.CO] (2021).
Henri Mühle, Ballot-Noncrossing Partitions, Proceedings of the 31st Conference on Formal Power Series and Algebraic Combinatorics (Ljubljana), Séminaire Lotharingien de Combinatoire (2019) Vol. 82B, Article #7.
Jim Pitman and Richard P. Stanley, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom. 27: 603-634 (2002).
D. P. Walsh, Notes on acyclic functions and their directed graphs

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

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

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

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 *)

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

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

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

A089460 Triangle, read by rows, of coefficients for the second iteration of the hyperbinomial transform.

Original entry on oeis.org

1, 2, 1, 8, 4, 1, 50, 24, 6, 1, 432, 200, 48, 8, 1, 4802, 2160, 500, 80, 10, 1, 65536, 28812, 6480, 1000, 120, 12, 1, 1062882, 458752, 100842, 15120, 1750, 168, 14, 1, 20000000, 8503056, 1835008, 268912, 30240, 2800, 224, 16, 1, 428717762, 180000000, 38263752, 5505024, 605052, 54432, 4200, 288, 18, 1

Offset: 0

Paul D. Hanna, Nov 05 2003

Equals the matrix square of A088956 when treated as a lower triangular matrix. The 2nd hyperbinomial transform of a sequence {b} is defined to be the sequence {d} given by d(n) = Sum_{k=0..n} T(n,k)*b(k), where T(n,k) = 2*(n-k+2)^(n-k-1)*C(n,k). Given a table in which the n-th row is the n-th binomial transform of the first row, then the 2nd hyperbinomial transform of any diagonal results in the diagonal located 2 diagonals lower in the table.

			Rows begin:
  {1},
  {2,1},
  {8,4,1},
  {50,24,6,1},
  {432,200,48,8,1},
  {4802,2160,500,80,10,1},
  {65536,28812,6480,1000,120,12,1},
  {1062882,458752,100842,15120,1750,168,14,1},..

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Cf. A089461(row sums), A089462(diagonal), A089463, A088956.

Join[{1}, Table[Binomial[n, k]*2*(n - k + 2)^(n - k - 1), {n, 1, 49}, {k, 0, n}]] // Flatten (* G. C. Greubel, Nov 18 2017 *)

for(n=0,10, for(k=0,n, print1(2*(n-k+2)^(n-k-1)*binomial(n,k), ", "))) \\ G. C. Greubel, Nov 18 2017

T(n, k) = 2*(n-k+2)^(n-k-1)*C(n, k).
E.g.f.: exp(x*y)*(-LambertW(-y)/y)^2.
Note: (-LambertW(-y)/y)^2 = Sum_{n>=0} 2*(n+2)^(n-1)*y^n/n!.

A089465 3rd hyperbinomial transform of A001858; also the hyperbinomial transform of A089462.

Original entry on oeis.org

1, 4, 23, 178, 1763, 21504, 313585, 5342068, 104376201, 2304582544, 56807530871, 1547599725720, 46202052688603, 1500629138909632, 52697989385197137, 1990117967149595824, 80440669725095395025, 3465573101368534916928

Offset: 0

Paul D. Hanna, Nov 05 2003

nonn

A001858 enumerates forests of labeled trees with n nodes and shifts 1 place left under the hyperbinomial transform.

G. C. Greubel, Table of n, a(n) for n = 0..385

Cf. A001858, A089462, A089463.

Table[Sum[Sum[Binomial[m, j]*Binomial[n, n - m - j + 1]*(n + 3)^(n - m - j + 1)*(m + j)!/(-2)^j, {j, 0, m}]/m!, {m, 0, n + 1}], {n, 0, 50}] (* G. C. Greubel, Nov 18 2017 *)

a(n)=if(n<0,0,sum(m=0,n+1,sum(j=0,m,binomial(m,j)*binomial(n,n-m-j+1)*(n+3)^(n-m-j+1)*(m+j)!/(-2)^j)/m!))

a(n) = Sum_{k=0..n} 3*(n-k+3)^(n-k-1)*C(n, k)*A001858(k).
a(n) = Sum_{m=0..(n+1)} ( Sum_{j=0..m} C(m, j)*C(n, n-m-j+1)*(n+3)^(n-m-j+1)*(m+j)!/(-2)^j )/m!.
a(n) ~ 3 * exp(7/2) * n^(n-1). - Vaclav Kotesovec, Oct 11 2020

cp's OEIS Frontend

A089464 Hyperbinomial transform of A089461. Also the row sums of triangle A089463, which lists the coefficients for the third hyperbinomial transform.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A089460 Triangle, read by rows, of coefficients for the second iteration of the hyperbinomial transform.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A089465 3rd hyperbinomial transform of A001858; also the hyperbinomial transform of A089462.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula