Cedric Chauve - cp's OEIS frontend

A307942 Number of evolutionary duplication-loss-histories of the complete binary species tree with 8 leaves.

8, 148, 3376, 89390, 2624872, 82866636, 2755019736, 95135709027, 3380416782760, 122798718575216, 4539685792433848, 170225552910292438, 6458330316575589176, 247456381334355675220, 9561546562984390785960, 372141845574597078971490, 14575950501012888889866120

Offset: 1

Cedric Chauve, May 07 2019

nonn

An evolutionary history of size n is an ordered rooted (incomplete) binary tree with n leaves describing the evolution of a gene family of a species in phylogenomics. The complete binary species tree S of size k is a complete binary tree with k leaves. Any node of the history is associated to a unique node of S, where specifically every leaf is associated to a leaf of S. A history is created by the following process (note that intermediate trees in this process may not be valid histories): Start with a root node associated to the root of S. For a given tree in the growth process, choose a leaf and perform a duplication, speciation, or (speciation-)loss event. A duplication event creates two children both associated to the same node as its parent. A speciation or (speciation-)loss event can only occur if the node is associated to an internal node in S. In that case, a speciation event creates two children associated to the children of the node in S. A (speciation-)loss event creates only a left or right child, associated to the left or right child in S, respectively.

			See A307941 (complete binary species tree with 4 leaves).

Cf. A000108 (caterpillar/complete binary species tree with 1 leaf, ordinary binary trees).

Cf. A307696, A307697, A307698, A307700 (caterpillar species tree with 2, 3, 4, 5 leaves).

z='z+O('z^20); my(t = sqrt(1-4*z), u = sqrt(-5+6*t+4*z), v = sqrt(1+6*u-6*t-4*z)); Vec(1/2-(1/2)*sqrt(-5+6*v-6*u+6*t+4*z)) \\ Jianing Song, Jul 29 2019

G.f.: 1/2-(1/2)*sqrt(-5+6*v-6*u+6*t+4*z) where t = sqrt(1-4*z), u = sqrt(-5+6*t+4*z) and v = sqrt(1+6*u-6*t-4*z).

A307943 Number of evolutionary duplication-loss-histories of the complete binary species tree with 16 leaves.

Original entry on oeis.org

16, 616, 28832, 1556780, 93017264, 5971377672, 403667945712, 28346017000314, 2048467088599520, 151362953286590792, 11383212160213595696, 868385902978402717696, 67032303753464250574432, 5225869642113491897295040, 410865063418648682500317120

Offset: 1

Cedric Chauve, May 07 2019

nonn

An evolutionary history of size n is an ordered rooted (incomplete) binary tree with n leaves describing the evolution of a gene family of a species in phylogenomics. The complete binary species tree S of size k is a complete binary tree with k leaves. Any node of the history is associated to a unique node of S, where specifically every leaf is associated to a leaf of S. A history is created by the following process (note that intermediate trees in this process may not be valid histories): Start with a root node associated to the root of S. For a given tree in the growth process, choose a leaf and perform a duplication, speciation, or (speciation-)loss event. A duplication event creates two children both associated to the same node as its parent. A speciation or (speciation-)loss event can only occur if the node is associated to an internal node in S. In that case, a speciation event creates two children associated to the children of the node in S. A (speciation-)loss event creates only a left or right child, associated to the left or right child in S, respectively.

			See A307941 (complete binary species tree with 4 leaves).

Sean A. Irvine, Java program (github)

Cf. A000108 (caterpillar/complete binary species tree with 1 leaf, ordinary binary trees).

Cf. A307696, A307697, A307698, A307700 (caterpillar species tree with 2, 3, 4, 5 leaves).

G.f.: 1/2-(1/2)*sqrt(1-6*v+6*w+6*u-6*t-4*z) where t = sqrt(1-4*z), u = sqrt(-5+6*t+4*z), v = sqrt(1+6*u-6*t-4*z) and w = sqrt(-5+6*v-6*u+6*t+4*z)

A307941 Number of evolutionary duplication-loss-histories of the complete binary species tree with 4 leaves.

Original entry on oeis.org

4, 34, 368, 4685, 66416, 1013268, 16279788, 271594611, 4660794200, 81747301898, 1458812278424, 26400987754054, 483374731032868, 8936983620559660, 166617056922535080, 3128790129161470470, 59124052722375912960, 1123458655726125274620, 21452847767668402271220

Offset: 1

Cedric Chauve, May 07 2019

nonn

An evolutionary history of size n is an ordered rooted (incomplete) binary tree with n leaves describing the evolution of a gene family of a species in phylogenomics. The complete binary species tree S of size k is a complete binary tree with k leaves. Any node of the history is associated to a unique node of S, where specifically every leaf is associated to a leaf of S. A history is created by the following process (note that intermediate trees in this process may not be valid histories): Start with a root node associated to the root of S. For a given tree in the growth process, choose a leaf and perform a duplication, speciation, or (speciation-)loss event. A duplication event creates two children both associated to the same node as its parent. A speciation or (speciation-)loss event can only occur if the node is associated to an internal node in S. In that case, a speciation event creates two children associated to the children of the node in S. A (speciation-)loss event creates only a left or right child, associated to the left or right child in S, respectively.

			The complete binary species tree with 4 leaves is equal to
     a
   /   \
  b     c
/ \   / \
1   2  3  4
For convenience the internal nodes are labeled by a,b,c and the leaves by 1,2,3,4. The associated nodes in the histories will be denoted by the same labels.
The a(1)=4 histories with n=1 leaf are created by the following growth process:
    a     a     a      a
   /     /       \      \
  b     b         c      c
/       \       /        \
1         2     3          4
after two loss events each.

Cf. A000108 (caterpillar/complete binary species tree with 1 leaf, ordinary binary trees).

Cf. A307696, A307697, A307698, A307700 (caterpillar species tree with 2, 3, 4, 5 leaves).

z='z+O('z^20); Vec(1/2-(1/2)*sqrt(1+6*sqrt(-5+6*sqrt(1-4*z)+4*z)-6*sqrt(1-4*z)-4*z)) \\ Jianing Song, Jul 29 2019

G.f.: 1/2-(1/2)*sqrt(1+6*sqrt(-5+6*sqrt(1-4*z)+4*z)-6*sqrt(1-4*z)-4*z).

A071212 Number of labeled cyclic trees with n nodes such that the root is smaller than all its children.

Original entry on oeis.org

1, 4, 28, 286, 3848, 64198, 1277400, 29507784, 775826832, 22869156168, 746817076080, 26758697374176, 1043610018593088, 44007103062886416, 1994973101346054144, 96747604119630501120, 4997654990315699224320

Offset: 2

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, research report RR-1226-99, LaBRI, Bordeaux I University, 1999.

Cf. A000312.

n -> sum((n! / (n-k)!) * (-1)^(n-1-k) * stirling1(n-1, k), k=0..n) - sum(((n-2)! / (n-1-k)!) * (-1)^(n-k) * stirling1(n, k), k=0..n-1);

A071211 Triangular array T(n,k) read by rows, giving number of labeled free trees such that the root is smaller than all its children, with respect to the number n of vertices and to the label k of the root.

Original entry on oeis.org

1, 3, 1, 16, 8, 3, 125, 75, 40, 16, 1296, 864, 540, 300, 125, 16807, 12005, 8232, 5292, 3024, 1296, 262144, 196608, 143360, 100352, 65856, 38416, 16807, 4782969, 3720087, 2834352, 2099520, 1492992, 995328, 589824, 262144, 100000000

Offset: 1

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.

Cf. A000312, A000272 (first column).

T:= (n, k)-> (n-k)*(n+1)^(n-k-1)*n^(k-1):
seq(seq(T(n, k), k=0..n-1), n=1..10);

tabl(nn) = {for (n=1, nn, for (k=0, n-1, print1((n-k)*(n+1)^(n-k-1)*n^(k-1), ", ");); print(););} \\ Michel Marcus, Jun 27 2013

T(n,k) = (n-k)*(n+1)^(n-k-1)*n^(k-1).

A071210 Triangular array T(n,k) read by rows, giving number of labeled free trees such that the root is smaller than all its children, with respect to the number n of vertices and to the degree k of the root.

Original entry on oeis.org

1, 3, 1, 18, 8, 1, 160, 80, 15, 1, 1875, 1000, 225, 24, 1, 27216, 15120, 3780, 504, 35, 1, 470596, 268912, 72030, 10976, 980, 48, 1, 9437184, 5505024, 1548288, 258048, 26880, 1728, 63, 1, 215233605, 127545840, 37200870, 6613488, 765450, 58320

Offset: 1

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.

Cf. A000312, A052182 (first column).

Maple
```
(n,k) -> binomial(n+1,k+1)*k*n^(n-k-1)
```

tabl(nn) = for (n=1, nn, for (k=1, n, print1(binomial(n+1, k+1)*k*n^(n-k-1), ", ");); print) \\ Michel Marcus, Jun 27 2013

T(n,k) = binomial(n+1, k+1)*k*n^(n-k-1).

A071209 Triangular array T(n,k) read by rows, giving number of labeled free trees such that the root is smaller than all its children, with respect to the number n of vertices and to the size k of the subtree rooted at the vertex labeled by 1.

Original entry on oeis.org

0, 1, 1, 0, 3, 8, 3, 0, 16, 81, 32, 18, 0, 125, 1024, 405, 240, 160, 0, 1296, 15625, 6144, 3645, 2560, 1875, 0, 16807, 279936, 109375, 64512, 45360, 35000, 27216, 0, 262144, 5764801, 2239488, 1312500, 917504, 708750, 580608, 470596, 0, 4782969

Offset: 1

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees

Cf. A000312.

(n,k) -> binomial(n,k-1)*k^(k-2)*(n-k)^(n+1-k);

tabl(nn) = {for (n=1, nn, for (k=1, n, print1(binomial(n, k-1)*k^(k-2)*(n-k)^(n+1-k), ", ");); print(););} \\ Michel Marcus, Jun 27 2013

binomial(n, k-1)*k^(k-2)*(n-k)^(n+1-k)

A071213 Number of labeled planar trees with n nodes such that the root is smaller than all its children.

Original entry on oeis.org

1, 4, 34, 436, 7428, 157368, 3980688, 116949600, 3911421600, 146673662400, 6093249563520, 277729608280320, 13778539159795200, 739059210587980800, 42615627311477606400, 2628646012982829772800, 172704619437756321484800

Offset: 2

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, research report RR-1226-99, LaBRI, Bordeaux I University, 1999.

Cf. A000108, A000312, A033184.

n -> 2 * sum((n-1) * (n-2+k)! / (k! * (n-1-k)), k=0 .. n-2) - ((2*n-3)! / (n-2)!);

C(x):=(1-sqrt(1-4*x))/(2);
F(x):=1+log(1-x)/x-log(1-x);
makelist(n!*coeff(taylor(F(C(x))+x*diff(F(C(x)),x),x,0,15),x,n),n,1,15); /*Vladimir Kruchinin, Mar 23 2016 */

E.g.f.: F(C(x))+x*[F(C(x))]', where C(x)/x is g.f. of Catalan numbers (A000108), F(x)=1+log(1-x)/x-log(1-x). - Vladimir Kruchinin, Mar 23 2016

A071214 Number of labeled ordered trees with n nodes such that the root is smaller than all its children.

Original entry on oeis.org

1, 5, 46, 614, 10716, 230712, 5903472, 174942000, 5890370400, 222069752640, 9265980286080, 423888544154880, 21094789126924800, 1134492559101619200, 65567415318776985600, 4052502049455940147200, 266725354163752808755200, 18624661769541550593024000

Offset: 2

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, research report RR-1226-99, LaBRI, Bordeaux I University, 1999.

C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labelled trees, FPSAC 2000, pp. 146-157. 2000.

Cf. A000312, A000108.

a:= n -> ((2*n-2)! / (n-1)!) - sum((n+k-1)! / ((n-k-1)*k!), k=0 .. n-2):
seq(a(n), n=2..22);

From Vladimir Kruchinin, Jun 02 2016: (Start)
E.g.f.: -[(log(1-x*C(x)))/C(x)]', where C(x) is g.f. of Catalan numbers (A000108).
a(n) = ((n+1)!*Sum_{k=1..n} ((k*binomial(2*n-k-1,n-k))/(k+1)))/n. (End)

A071207 Triangular array T(n,k) read by rows, giving number of rooted trees on the vertex set {1..n+1} where k children of the root have a label smaller than the label of the root.

Original entry on oeis.org

1, 1, 1, 4, 4, 1, 27, 27, 9, 1, 256, 256, 96, 16, 1, 3125, 3125, 1250, 250, 25, 1, 46656, 46656, 19440, 4320, 540, 36, 1, 823543, 823543, 352947, 84035, 12005, 1029, 49, 1, 16777216, 16777216, 7340032, 1835008, 286720, 28672, 1792, 64, 1, 387420489

Offset: 0

Cedric Chauve (chauve(AT)lacim.uqam.ca), May 16 2002

The n-th term of the n-th binomial transform of a sequence {b} is given by {d} where d(n) = sum(k=0,n,T(n,k)*b(k)) and T(n,k)=binomial(n,k)*n^(n-k); such diagonals are related to the hyperbinomial transform (A088956). - Paul D. Hanna, Nov 04 2003
T(n,k) gives the number of divisors of A181555(n) with (n-k) distinct prime factors. See also A001221, A146289, A146290, A181567. - Matthew Vandermast, Oct 31 2010
T(n,k) is the number of partial functions on {1,2,...,n} leaving exactly k elements undefined.  Row sums = A000169. - Geoffrey Critzer, Jan 08 2012
As a triangular matrix, transforms rows into diagonals in the table of coefficients of successive iterations of x/(1-x). - Paul D. Hanna, Jan 19 2014
Also the number of rooted trees on n+1 labeled vertices in which some specified vertex (say, vertex 1) has k children. - Alan Sokal, Jul 22 2022

			1
1     1
4     4     1
27    27    9     1
256   256   96    16    1
3125  3125  1250  250   25    1
46656 46656 19440 4320  540   36    1

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
C. Chauve, S. Dulucq and O. Guibert, Enumeration of some labeled trees, Proceedings of FPSAC/SFCA 2000 (Moscow), Springer, pp. 146-157.
Alan D. Sokal, A remark on the enumeration of rooted labeled trees, arXiv:1910.14519 [math.CO], 2019 and Discrete Math. 343, 111865 (2020).

Cf. A000169, A000312, A089466, A088956, A166900.

T:= (n, k)-> binomial(n, k)*n^(n-k): seq(seq(T(n, k), k=0..n), n=0..10);

Prepend[Flatten[ Table[Table[Binomial[n, k] n^(n - k), {k, 0, n}], {n, 1, 8}]], 1]  (* Geoffrey Critzer, Jan 08 2012 *)

T(n,k)=if(k<0 || k>n,0,binomial(n,k)*n^(n-k))

/* Transforms rows into diagonals in the iterations of x/(1-x): */
{T(n, k)=local(F=x, M, N, P, m=n); M=matrix(m+2, m+2, r, c, F=x; for(i=1, r+c-2, F=subst(F, x, x/(1-x+x*O(x^(m+2))))); polcoeff(F, c)); N=matrix(m+1, m+1, r, c, F=x; for(i=1, r, F=subst(F, x, x/(1-x+x*O(x^(m+2))))); polcoeff(F, c)); P=matrix(m+1, m+1, r, c, M[r+1, c]); (P~*N~^-1)[n+1, k+1]}
for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print("")) \\ Paul D. Hanna, Jan 19 2014

T(n,k) = binomial(n, k)*n^(n-k).

E.g.f.: (-LambertW(-y)/y)^x/(1+LambertW(-y)). - Vladeta Jovovic

Name edited by Alan Sokal, Jul 22 2022

cp's OEIS Frontend

User: Cedric Chauve

A307942 Number of evolutionary duplication-loss-histories of the complete binary species tree with 8 leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A307943 Number of evolutionary duplication-loss-histories of the complete binary species tree with 16 leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A307941 Number of evolutionary duplication-loss-histories of the complete binary species tree with 4 leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A071212 Number of labeled cyclic trees with n nodes such that the root is smaller than all its children.

Views

Author

Keywords

References

Crossrefs

Programs

Maple

A071211 Triangular array T(n,k) read by rows, giving number of labeled free trees such that the root is smaller than all its children, with respect to the number n of vertices and to the label k of the root.

Views

Author

Keywords

References

Crossrefs

Programs

Maple

PARI

Formula

A071210 Triangular array T(n,k) read by rows, giving number of labeled free trees such that the root is smaller than all its children, with respect to the number n of vertices and to the degree k of the root.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A071209 Triangular array T(n,k) read by rows, giving number of labeled free trees such that the root is smaller than all its children, with respect to the number n of vertices and to the size k of the subtree rooted at the vertex labeled by 1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

PARI

Formula

A071213 Number of labeled planar trees with n nodes such that the root is smaller than all its children.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Maxima

Formula