A248869 -id:A248869 - cp's OEIS frontend

A318757 Number A(n,k) of rooted trees with n nodes such that no more than k isomorphic subtrees extend from the same node; square array A(n,k), n>=0, k>=0, read by antidiagonals.

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 2, 2, 0, 0, 1, 1, 2, 3, 3, 0, 0, 1, 1, 2, 4, 7, 6, 0, 0, 1, 1, 2, 4, 8, 15, 12, 0, 0, 1, 1, 2, 4, 9, 18, 34, 25, 0, 0, 1, 1, 2, 4, 9, 19, 43, 79, 52, 0, 0, 1, 1, 2, 4, 9, 20, 46, 102, 190, 113, 0, 0, 1, 1, 2, 4, 9, 20, 47, 110, 250, 459, 247, 0

Offset: 0

Alois P. Heinz, Sep 02 2018

			Square array A(n,k) begins:
  0,  0,  0,   0,   0,   0,   0,   0,   0, ...
  1,  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,  2,   2,   2,   2,   2,   2,   2, ...
  0,  2,  3,   4,   4,   4,   4,   4,   4, ...
  0,  3,  7,   8,   9,   9,   9,   9,   9, ...
  0,  6, 15,  18,  19,  20,  20,  20,  20, ...
  0, 12, 34,  43,  46,  47,  48,  48,  48, ...
  0, 25, 79, 102, 110, 113, 114, 115, 115, ...

Alois P. Heinz, Antidiagonals n = 0..200, flattened

Columns k=0-10 give: A063524, A004111, A248869, A318850, A318851, A318852, A318853, A318854, A318855, A318856, A318857.
Main diagonal gives A000081.
Cf. A318753, A318758.

h:= proc(n, m, t, k) option remember; `if`(m=0, binomial(n+t, t),
      `if`(n=0, 0, add(h(n-1, m-j, t+1, k), j=1..min(k, m))))
    end:
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1, k)*h(A(i, k), j, 0, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n, b(n-1$2, k)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

h[n_, m_, t_, k_] := h[n, m, t, k] = If[m == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n - 1, m - j, t + 1, k], {j, 1, Min[k, m]}]]];
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[b[n - i*j, i - 1, k]*h[A[i, k], j, 0, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n, b[n - 1, n - 1, k]];
Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 11 2019, after Alois P. Heinz *)

A(n,k) = Sum_{j=0..k} A318758(n,j) for n > 0.

A(n,n+j) = A000081(n) for j >= -1.

A213920 Number of rooted trees with n nodes such that no more than two subtrees corresponding to children of any node have the same number of nodes.

Original entry on oeis.org

0, 1, 1, 2, 3, 7, 15, 34, 79, 190, 457, 1132, 2823, 7126, 18136, 46541, 120103, 312109, 815012, 2137755, 5632399, 14895684, 39519502, 105198371, 280815067, 751490363, 2016142768, 5420945437, 14604580683, 39425557103, 106618273626, 288792927325, 783516425820

Offset: 0

Alois P. Heinz, Mar 05 2013

nonn

Coincides with A248869 up to a(9) = 190.

a(n+1)/a(n) tends to 2.845331... - Vaclav Kotesovec, Jun 04 2019

			:  o  :  o  :    o   o  :    o     o   o  :
:     :  |  :   / \  |  :    |    / \  |  :
:     :  o  :  o   o o  :    o   o   o o  :
:     :     :        |  :   / \  |     |  :
:     :     :        o  :  o   o o     o  :
:     :     :           :              |  :
: n=1 : n=2 :  n=3      :  n=4         o  :
:.....:.....:...........:.................:
:   o     o       o     o     o     o   o :
:   |     |      / \   / \   / \   /|\  | :
:   o     o     o   o o   o o   o o o o o :
:   |    / \   / \    |     |   | |     | :
:   o   o   o o   o   o     o   o o     o :
:  / \  |             |                 | :
: o   o o             o                 o :
:                                       | :
: n=5                                   o :
:.........................................:

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

Cf. A000081, A032305, A248869.

Column k=2 of A318753.

g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, add(
      binomial(g((i-1)$2)+j-1, j)*g(n-i*j, i-1), j=0..min(2, n/i))))
    end:
a:= n-> g((n-1)$2):
seq(a(n), n=0..40);

g[n_, i_] := g[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[g[i-1, i-1]+j-1, j]*g[n-i*j, i-1], {j, 0, Min[2, n/i]}]]]; a[n_] := g[n-1, n-1]; Table[ a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 21 2017, translated from Maple *)

A309352 Number of free trees of n vertices whose automorphisms are a 2-group.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 4, 6, 13, 26, 56, 122, 278, 634, 1494, 3540, 8542, 20774, 51116, 126648, 316452, 795510, 2012476, 5117613, 13079677, 33576706, 86555074, 223965633, 581573118, 1515084771, 3959038337, 10374543765, 27258298145

Offset: 0

Kevin Ryde, Jul 24 2019

nonn

A 2-group is a group with order some power 2^k. In free tree automorphisms, this means at a given vertex an adjacent subtree can appear there twice, but not three or more times.

Free trees are counted from rooted trees in the usual way by rooting at a centroid. This is in the generating function of A000055 (all free) from A000081 (all rooted). From all rooted trees, subtract the unbalanced where root not centroid, and allow bicentroidals with same halves. a(n) follows this way from A248869 rooted 2-groups. With root as centroid, the free automorphisms are all and only the rooted automorphisms, except swap halves of a bi-centroidal. Such a swap can be part of a 2-group, so same halves allowed.

			a(4)=1 is path-4 having automorphism group S2 (reverse the path), and excludes star-4 which is S3 order 6 (permute the leaves).  a(5)=2 excludes star-5 which is S4 on the leaves.

Kevin Ryde, Table of n, a(n) for n = 0..2213

Cf. A000055, A000220, A248869.

h:= proc(n, m, t) option remember; `if`(m=0, binomial(n+t, t),
      `if`(n=0, 0, add(h(n-1, m-j, t+1), j=1..min(2, m))))
    end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(b(n-i*j, i-1)*h(g(i), j, 0), j=0..n/i)))
    end:
g:= n-> `if`(n<2, n, b(n-1$2)):
a:= n-> `if`(n=0, 1, g(n)-add(g(j)*g(n-j), j=0..n/2)+
        `if`(n::even, (t-> t*(t+1)/2)(g(n/2)), 0)):
seq(a(n), n=0..35);  # Alois P. Heinz, Aug 01 2019

h[n_, m_, t_] := h[n, m, t] = If[m == 0, Binomial[n + t, t], If[n == 0, 0, Sum[h[n-1, m-j, t+1], {j, 1, Min[2, m]}]]];
b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[b[n - i j, i-1] h[g[i], j, 0], {j, 0, n/i}]]];
g[n_] := If[n < 2, n, b[n-1, n-1]];
a[n_] := If[n == 0, 1, g[n] - Sum[g[j] g[n-j], {j, 0, n/2}] + If[EvenQ[n], #(#+1)/2&[g[n/2]], 0]];
a /@ Range[0, 35] (* Jean-François Alcover, Nov 14 2020, after Alois P. Heinz *)

a(n) = A248869(n) - (Sum_{i=1..floor(n/2)} A248869(i)*A248869(n-i)) + (binomial(A248869(n/2)+1,2) if n even), for n>=1.

G.f.: g(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + 3*x^4 + ... is the g.f. for A248869.

A248870 Satisfies Sum_{n>=0} a(n)*x^n = x / Product_{n>=0} (1 - x^n/(1 - x^n))^a(n).

Original entry on oeis.org

0, 1, 1, 3, 8, 23, 62, 181, 513, 1513, 4476, 13483, 40933, 125845, 389769, 1217590, 3828775, 12115966, 38546124, 123238296, 395725493, 1275733730, 4127339091, 13396443708, 43610621823, 142354979662, 465838195260, 1527905193504, 5022061115901, 16539625666670, 54571760414658

Offset: 0

Joerg Arndt, Mar 04 2015

nonn

Which kind of trees is counted by this sequence (compare to A000081, A004111, A073075, A248869 and A115593)?

Cf. A248869.

cp's OEIS Frontend

A318757 Number A(n,k) of rooted trees with n nodes such that no more than k isomorphic subtrees extend from the same node; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A213920 Number of rooted trees with n nodes such that no more than two subtrees corresponding to children of any node have the same number of nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A309352 Number of free trees of n vertices whose automorphisms are a 2-group.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A248870 Satisfies Sum_{n>=0} a(n)*x^n = x / Product_{n>=0} (1 - x^n/(1 - x^n))^a(n).

Views

Author

Keywords

Comments

Crossrefs