A213683 Number of rooted trees with n nodes having some subtrees replaced by cycles.

0, 0, 0, 1, 2, 4, 9, 23, 61, 168, 469, 1326, 3776, 10833, 31228, 90438, 262860, 766497, 2241194, 6569206, 19296214, 56789286, 167419568, 494337282, 1461690270, 4327638394, 12828158828, 38067670764, 113081627856, 336233591365, 1000636296475, 2980391776958

Offset

0,5

Links

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

Formula

a(n) = A213674(n) - A000081(n).

Example

:   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=3   . n=4         : n=5      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   o---o o   o     o   o   o---o   :
:  \ /  |   |  / \   / \      |            / \     \ /            :
:   o   o---o o   o o---o     o           o---o     o             :
:              \ /           / \                                  :
: n=6           o           o---o                                 :
:.................................................................:

Maple

b:= proc(n, i) option remember; `if`(n=0, [1$2], `if`(i<1, [0$2],
      add(((x, y)-> map(p->binomial(p[1]+j-1, j)*p[2], [[x[1], y[1]],
      [x[2], y[2]]]))(g(i), b(n-i*j, i-1)), j=0..n/i)))
    end:
g:= n-> (l-> l+ [0, `if`(n>2, 1, 0)])(b(n-1, n-1)):
a:= n-> (l->l[2]-l[1])(g(n)):
seq(a(n), n=0..40);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A213674[i] + j - 1, j]*b[n - i*j, i - 1], {j, 0, n/i}]] // FullSimplify];
A213674[n_] := b[n - 1, n - 1] + If[n > 2, 1, 0];
A81[n_] := A81[n] = If[n <= 1, n, Sum[Sum[d*A81[d], {d, Divisors[j]}]*A81[n - j], {j, 1, n - 1}]/(n - 1)];
a[n_] := A213674[n] - A81[n];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Jun 26 2022, after Alois P. Heinz in A213674 *)

Crossrefs

Cf. A000081, A213674, A213682.

Sequence in context: A364485 A027133 A339296 * A032010 A032028 A190277

Adjacent sequences: A213680 A213681 A213682 * A213684 A213685 A213686

Keyword

nonn

Author

Alois P. Heinz, Mar 04 2013

Status

approved