A318602 -id:A318602 - cp's OEIS frontend

A318601 Triangle read by rows: T(n,k) is the number of hypertrees on n unlabeled nodes with k edges, (0 <= k < n).

1, 0, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 2, 3, 3, 0, 1, 2, 6, 7, 6, 0, 1, 3, 9, 17, 18, 11, 0, 1, 3, 13, 30, 51, 44, 23, 0, 1, 4, 17, 53, 109, 148, 117, 47, 0, 1, 4, 23, 79, 213, 372, 443, 299, 106, 0, 1, 5, 28, 119, 370, 827, 1276, 1306, 793, 235

Offset: 1

Andrew Howroyd, Aug 29 2018

Equivalently, the number of connected graphs on n unlabeled nodes with k blocks where every block is a complete graph.

Let R(x,y) be the g.f. of A318602 and S(x,y) be the g.f. of A318607. Then the number of hypertrees rooted at a vertex is R(x,y), the number rooted at an edge is y*(S(x,y) - R(x,y)) and the number rooted at a directed edge is y*S(x,y)*R(x,y). The dissymmetry theorem for trees gives that the number of unlabeled objects (this sequence) is the number rooted at a vertex plus the number rooted at an edge minus the number rooted at a directed edge.

			Triangle begins:
  1;
  0, 1;
  0, 1, 1;
  0, 1, 1,  2;
  0, 1, 2,  3,  3;
  0, 1, 2,  6,  7,   6;
  0, 1, 3,  9, 17,  18,  11;
  0, 1, 3, 13, 30,  51,  44,  23;
  0, 1, 4, 17, 53, 109, 148, 117,  47;
  0, 1, 4, 23, 79, 213, 372, 443, 299, 106;
  ...
Case n=4: There are 4 possible graphs which are the complete graph on 4 nodes which has 1 block, a triangle joined to a single vertex which has 2 blocks and two trees which have 3 blocks. Row 4 is then 0, 1, 1, 2.
    o---o       o---o    o---o     o--o--o
    | X |      / \       |            |
    o---o     o---o      o---o        o
.
Case n=5, k=3: The following illustrates how the dissymmetry thereom for each unlabeled hypertree gives 1 = vertex rooted + edge (block) rooted - directed edge (vertex of block) rooted.
      o---o
     / \          1 = 3 + 2 - 4
    o---o---o
.
      o   o
     / \ /        1 = 3 + 2 - 4
    o---o---o
.
      o   o
     / \ / \      1 = 4 + 3 - 6
    o---o   o
.

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Rightmost diagonal is A000055 (unlabeled trees).
Row sums are A035053.
Cf. A304867, A318602, A318607.

\\ here b(n) is A318602 as vector of polynomials.
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
b(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerMT(y*EulerMT(v)))); v}
G(n)={my(u=b(n)); apply(p->Vecrev(p), Vec(y*Ser(EulerMT(u))*(1-x*Ser(u)) + (1 - y)*Ser(u)))}
{ my(T=G(10)); for(n=1, #T, print(T[n])) }

G.f.: R(x,y) + y*(S(x,y) - R(x,y)) - y*S(x,y)*R(x,y) where R(x,y) is the g.f. of A318602 and S(x,y) is the g.f. of A318607.

A318607 Triangle read by rows: T(n,k) is the number of sets of rooted hypertrees on a total of n unlabeled nodes with a total of k edges, (0 <= k < n).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 4, 1, 4, 12, 16, 9, 1, 5, 20, 42, 46, 20, 1, 6, 30, 86, 145, 128, 48, 1, 7, 42, 153, 353, 483, 364, 115, 1, 8, 56, 248, 729, 1369, 1592, 1029, 286, 1, 9, 72, 376, 1345, 3236, 5150, 5151, 2930, 719, 1, 10, 90, 541, 2287, 6728, 13708, 18792, 16513, 8344, 1842

Offset: 1

Andrew Howroyd, Aug 30 2018

Equivalently, the number of sets of rooted connected graphs on a total of n unlabeled nodes with a total of k blocks where every block is a complete graph.

Bivariate Euler transform of triangle A318602.

			Triangle begins:
  1;
  1, 1;
  1, 2, 2;
  1, 3, 6, 4;
  1, 4, 12, 16, 9;
  1, 5, 20, 42, 46, 20;
  1, 6, 30, 86, 145, 128, 48;
  1, 7, 42, 153, 353, 483, 364, 115;
  1, 8, 56, 248, 729, 1369, 1592, 1029, 286;
  ...
Case n=3: There are 5 sets of rooted graph which are illustrated below (an x marks a root node). These have 0, 1, 1, 2, 2 blocks so row 3 is 1, 2, 2.
      x        o        o        o        o
              /        / \        \      /
    x   x    x   x    x---o    x---o    x---o

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Rightmost diagonal is A000081 (rooted trees).
Row sums are A035052.
Cf. A318601, A318602.

\\ here EulerMT is Euler transform (bivariate version).
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
A(n)={my(v=[1]); for(i=2, n, v=concat([1], EulerMT(y*EulerMT(v)))); [Vecrev(p) | p <- EulerMT(v)]}
{ my(T=A(10)); for(n=1, #T, print(T[n])) }

cp's OEIS Frontend

A318601 Triangle read by rows: T(n,k) is the number of hypertrees on n unlabeled nodes with k edges, (0 <= k < n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula