login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)))... 11
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.

A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.

Cf. A001678, A331934, A331963, A331964.

Sequence in context: A005578 A058050 A026418 * A337090 A331993 A027214

Adjacent sequences:  A063892 A063893 A063894 * A063896 A063897 A063898

KEYWORD

easy,nonn,nice,eigen,changed

AUTHOR

Claude Lenormand (claude.lenormand(AT)free.fr), Aug 29 2001

EXTENSIONS

Additional comments and g.f. from Christian G. Bower, Nov 29 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 14 07:13 EDT 2021. Contains 343879 sequences. (Running on oeis4.)