A063895 - OEIS

A063895

Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

1, 1, 1, 1, 2, 3, 6, 11, 22, 43, 88, 179, 372, 774, 1631, 3448, 7347, 15713, 33791, 72923, 158021, 343495, 749102, 1638103, 3591724, 7893802, 17387931, 38379200, 84875596, 188036830, 417284181, 927469845, 2064465341, 4601670625, 10270463565, 22950838755

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

Also binary rooted identity trees (those with no symmetries, cf. A004111).

From Gus Wiseman, May 04 2021: (Start)

Also the number of unlabeled binary rooted semi-identity trees with 2*n - 1 nodes. In a semi-identity tree, only the non-leaf branches directly under any given vertex are required to be distinct. Alternatively, an unlabeled rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees. For example, the a(3) = 1 through a(6) = 6 trees are:

(o(oo)) (o(o(oo))) ((oo)(o(oo))) ((oo)(o(o(oo)))) ((o(oo))(o(o(oo))))

(o(o(o(oo)))) (o((oo)(o(oo)))) ((oo)((oo)(o(oo))))

(o(o(o(o(oo))))) ((oo)(o(o(o(oo)))))

(o((oo)(o(o(oo)))))

(o(o((oo)(o(oo)))))

(o(o(o(o(o(oo))))))

The a(8) = 11 trees with 15 nodes:

((o(oo))((oo)(o(oo))))

((o(oo))(o(o(o(oo)))))

((oo)((oo)(o(o(oo)))))

((oo)(o((oo)(o(oo)))))

((oo)(o(o(o(o(oo))))))

(o((o(oo))(o(o(oo)))))

(o((oo)((oo)(o(oo)))))

(o((oo)(o(o(o(oo))))))

(o(o((oo)(o(o(oo))))))

(o(o(o((oo)(o(oo))))))

(o(o(o(o(o(o(oo)))))))

(End)

LINKS

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

Index entries for sequences related to rooted trees

FORMULA

a(n) = (sum a(i)*a(j), i+j=n, i<j)+(if n=2k, (a(k)-1)*a(k)/2), n>2. a(1)=a(2)=1.

G.f. A(x) = 1-sqrt(1-2x-2x^2+A(x^2)) satisfies x+x^2-A(x)+(A(x)^2-A(x^2))/2=0, A(0)=0. - Michael Somos, Sep 06 2003

a(n) ~ c * d^n / n^(3/2), where d = 2.33141659246516873904600076533362924695..., c = 0.2873051160895040470174351963... . - Vaclav Kotesovec, Sep 11 2014

MAPLE

a:= proc(n) option remember; `if`(n<3, n*(3-n)/2, add(a(i)*a(n-i),

i=1..(n-1)/2)+`if`(irem(n, 2, 'r')=0, (p->(p-1)*p/2)(a(r)), 0))

end:

seq(a(n), n=1..50); # Alois P. Heinz, Aug 02 2013

MATHEMATICA

a[n_] := a[n] = If[n<3, n*(3-n)/2, Sum[a[i]*a[n-i], {i, 1, (n-1)/2}]+If[{q, r} = QuotientRemainder[n, 2]; r == 0, (a[q]-1)*a[q]/2, 0]]; Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)

ursiq[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursiq/@ptn]], #=={}||#=={{}, {}}||Length[#]==2&&(UnsameQ@@DeleteCases[#, {}])&], {ptn, IntegerPartitions[n-1]}]; Table[Length[ursiq[n]], {n, 1, 15, 2}] (* Gus Wiseman, May 04 2021 *)

PROG

(PARI) {a(n)=local(A, m); if(n<1, 0, m=1; A=O(x); while( m<=n, m*=2; A=1-sqrt(1-2*x-2*x^2+subst(A, x, x^2))); polcoeff(A, n))}

CROSSREFS

Cf. A063894, A036774.

The non-semi-identity version is 2*A001190(n)-1, ranked by A111299.

Semi-binary trees are also counted by A001190, but ranked by A292050.

The not necessarily binary version is A306200, ranked A306202.

The Matula-Goebel numbers of these trees are A339193.

The plane tree version is A343663.

A000081 counts unlabeled rooted trees with n nodes.

A004111 counts identity trees, ranked by A276625.

A306201 counts balanced semi-identity trees, ranked by A306203.