A290689 -id:A290689 - cp's OEIS frontend

A324969 Number of unlabeled rooted identity trees with n vertices whose non-leaf terminal subtrees are all different.

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155

Offset: 1

Gus Wiseman, Mar 21 2019

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root. This sequence counts rooted identity trees satisfying the additional condition that all non-leaf terminal subtrees are different.
Appears to be essentially the same as the Fibonacci sequence A000045. - R. J. Mathar, Mar 28 2019
From Michael Somos, Nov 22 2019: (Start)
A terminal subtree T' of a tree T is a subtree all of whose vertices except one have the same degree in T' as in T itself.
The conjecture of Mathar is true. Proof: Given a rooted identity tree T, a terminal subtree T' with more than one vertex contains at least one edge that is also a terminal subtree of T'. Thus, if T has more than one branch with more than one vertex, then it fails the additional condition since it would have at least two non-leaf terminal subtrees (namely edges) that are the same.  Also, T can't have under its root more than one branch with exactly one vertex because it is an identity tree. Now we know that under the root of T is exactly one branch of the same kind as T or else it has exactly one other branch with exactly one vertex. The leads immediately to the same recurrence as A000045 the Fibonacci sequence except for n=3. (End)

			The a(1) = 1 through a(7) = 8 trees:
  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))))))
G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 5*x^6 + 8*x^7 + 13*x^8 + ... - _Michael Somos_, Nov 22 2019

G. C. Greubel, Table of n, a(n) for n = 1..1000
Joshua P. Bowman, Compositions with an Odd Number of Parts, and Other Congruences, J. Int. Seq (2024) Vol. 27, Art. 24.3.6. See p. 21.
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 11.
Index entries for linear recurrences with constant coefficients, signature (1,1).

The Matula-Goebel numbers of these trees are given by A324968.
Cf. A000045, A000081, A004111, A276625, A290689.
Cf. A317713, A324923, A324936, A324971, A324978.

[1] cat [Fibonacci(n-1): n in [2..50]]; // G. C. Greubel, Oct 24 2023

(* First program *)
durtid[n_]:= Join@@Table[Select[Union[Sort/@Tuples[durtid/@ptn]], UnsameQ@@#&&UnsameQ@@Cases[#, {}, {0,Infinity}]&],{ptn, IntegerPartitions[n-1]}];
Table[Length[durtid[n]],{n,15}]
(* Second program *)
Join[{1}, Fibonacci[Range[50]]] (* G. C. Greubel, Oct 24 2023 *)

{a(n) = if( n<=1, n==1, fibonacci(n-1))}; /* Michael Somos, Nov 22 2019 */

[int(n==1) +fibonacci(n-1) for n in range(1,51)] # G. C. Greubel, Oct 24 2023

From Michael Somos, Nov 22 2019: (Start)
G.f.: x*(1 - x^2) / (1 - x - x^2) = x*(1 + x/(1 - x/(1 - x/(1 + x)))).
a(n) = A000045(n-1) if n>=2. (End)
E.g.f.: -1 + x + exp(x/2)*(cosh(sqrt(5)*x/2) - (1/sqrt(5))*sinh(sqrt(5)*x/2)). - G. C. Greubel, Oct 24 2023

More terms from Jinyuan Wang, Jun 27 2020

A324768 Number of fully anti-transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 27, 60, 152, 376, 968, 2492, 6549, 17259, 46000, 123214, 332304, 900406, 2451999, 6703925

Offset: 1

Gus Wiseman, Mar 17 2019

An unlabeled rooted tree is fully anti-transitive if no proper terminal subtree of any branch of the root is a branch of the root.

			The a(1) = 1 through a(6) = 11 rooted trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (((o)))  (((oo)))   (((ooo)))
                          ((o)(o))   ((o)(oo))
                          ((o(o)))   ((o(oo)))
                          ((((o))))  ((oo(o)))
                                     ((((oo))))
                                     (((o)(o)))
                                     (((o(o))))
                                     ((o((o))))
                                     (((((o)))))

Cf. A000081, A279861, A290689, A304360, A306844, A318185.
Cf. A324695, A324751, A324756, A324758, A324763, A324765, A324769, A324770.
Cf. A324838, A324840, A324844, A324846.

rtall[n_]:=Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])];
Table[Length[Select[rtall[n],Intersection[Union@@Rest[FixedPointList[Union@@#&,#]],#]=={}&]],{n,10}]

a(17)-a(20) from Jinyuan Wang, Jun 20 2020

A325705 Number of integer partitions of n containing all of their distinct multiplicities.

Original entry on oeis.org

1, 1, 0, 1, 3, 2, 4, 3, 7, 8, 16, 15, 24, 28, 39, 44, 68, 80, 98, 130, 167, 200, 259, 320, 396, 497, 601, 737, 910, 1107, 1335, 1631, 1983, 2372, 2887, 3439, 4166, 4949, 5940, 7043, 8450, 9980, 11884, 13984, 16679, 19493, 23162, 27050, 31937, 37334, 43926

Offset: 0

Gus Wiseman, May 18 2019

nonn

The Heinz numbers of these partitions are given by A325706.

			The partition (4,2,1,1,1,1) has distinct multiplicities {1,4}, both of which belong to the partition, so it is counted under a(10).
The a(0) = 1 through a(10) = 16 partitions:
  ()  (1)  (21)  (22)   (41)   (51)    (61)    (71)     (81)     (91)
                 (31)   (221)  (321)   (421)   (431)    (333)    (541)
                 (211)         (2211)  (3211)  (521)    (531)    (631)
                               (3111)          (3221)   (621)    (721)
                                               (4211)   (3321)   (3322)
                                               (32111)  (4221)   (3331)
                                               (41111)  (5211)   (4321)
                                                        (32211)  (5221)
                                                                 (6211)
                                                                 (32221)
                                                                 (33211)
                                                                 (42211)
                                                                 (43111)
                                                                 (322111)
                                                                 (421111)
                                                                 (511111)

Cf. A109297, A114639, A114640, A181819, A225486, A290689, A324753, A324843, A325702, A325706, A325707, A325755.

Table[Length[Select[IntegerPartitions[n],SubsetQ[Sort[#],Sort[Length/@Split[#]]]&]],{n,0,30}]

A124343 Number of rooted trees on n nodes with thinning limbs.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 21, 38, 78, 153, 314, 632, 1313, 2700, 5646, 11786, 24831, 52348, 111027, 235834, 502986, 1074739, 2303146, 4944507, 10639201, 22930493, 49511948, 107065966, 231874164, 502834328, 1091842824, 2373565195, 5165713137, 11254029616, 24542260010

Offset: 1

Christian G. Bower, Oct 30 2006, suggested by Franklin T. Adams-Watters

nonn

A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.

			The a(5) = 6 trees are ((((o)))), (o((o))), (o(oo)), ((o)(o)), (oo(o)), (oooo). - _Gus Wiseman_, Jan 25 2018

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

Cf. A000081, A032305, A124344-A124348, A290689, A298303, A298304, A298305, A298422.

Row sums of A244657.

b:= proc(n, i, h, v) option remember; `if`(n=0,
      `if`(v=0, 1, 0), `if`(i<1 or v<1 or n A(n$2):
seq(a(n), n=1..35);  # Alois P. Heinz, Jul 08 2014

b[n_, i_, h_, v_] := b[n, i, h, v] = If[n==0, If[v==0, 1, 0], If[i<1 || v<1 || nJean-François Alcover, Mar 01 2016, after Alois P. Heinz *)

More terms from Alois P. Heinz, Jul 04 2014

A301342 Regular triangle where T(n,k) is the number of rooted identity trees with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 0, 0, 0, 1, 4, 1, 0, 0, 0, 1, 6, 5, 0, 0, 0, 0, 1, 9, 13, 2, 0, 0, 0, 0, 1, 12, 28, 11, 0, 0, 0, 0, 0, 1, 16, 53, 40, 3, 0, 0, 0, 0, 0, 1, 20, 91, 109, 26, 0, 0, 0, 0, 0, 0, 1, 25, 146, 254, 116, 6, 0, 0, 0, 0, 0, 0, 1, 30, 223, 524, 387, 61, 0, 0, 0, 0, 0, 0, 0, 1, 36

Offset: 1

Gus Wiseman, Mar 19 2018

			Triangle begins:
1
1   0
1   0   0
1   1   0   0
1   2   0   0   0
1   4   1   0   0   0
1   6   5   0   0   0   0
1   9  13   2   0   0   0   0
1  12  28  11   0   0   0   0   0
1  16  53  40   3   0   0   0   0   0
1  20  91 109  26   0   0   0   0   0   0
1  25 146 254 116   6   0   0   0   0   0   0
1  30 223 524 387  61   0   0   0   0   0   0   0
The T(6,2) = 4 rooted identity trees: (((o(o)))), ((o((o)))), (o(((o)))), ((o)((o))).

A version with the zeroes removed is A055327.

Cf. A000081, A001190, A003238, A004111, A032305, A055277, A273873, A276625, A277098, A290689, A298118, A298422, A298426, A301343, A301344, A301345.

irut[n_]:=irut[n]=If[n===1,{{}},Join@@Function[c,Select[Union[Sort/@Tuples[irut/@c]],UnsameQ@@#&]]/@IntegerPartitions[n-1]];
Table[Length[Select[irut[n],Count[#,{},{-2}]===k&]],{n,8},{k,n}]

A324738 Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 26, 42, 72, 120, 232, 376, 752, 1128, 2256, 4512, 8256, 13632, 27264, 42048, 82944, 158976, 313344, 497664, 995328, 1700352, 3350016, 5815296, 11630592, 17491968, 34983936, 56954880, 108933120, 210788352, 418258944, 804667392, 1609334784

Offset: 0

Gus Wiseman, Mar 13 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(0) = 1 through a(6) = 26 subsets:
  {}  {}   {}   {}     {}     {}       {}
      {1}  {1}  {1}    {1}    {1}      {1}
           {2}  {2}    {2}    {2}      {2}
                {3}    {3}    {3}      {3}
                {1,3}  {4}    {4}      {4}
                       {1,3}  {5}      {5}
                       {2,4}  {1,3}    {6}
                       {3,4}  {1,5}    {1,3}
                              {2,4}    {1,5}
                              {2,5}    {1,6}
                              {3,4}    {2,4}
                              {4,5}    {2,5}
                              {2,4,5}  {2,6}
                                       {3,4}
                                       {3,6}
                                       {4,5}
                                       {4,6}
                                       {5,6}
                                       {1,3,6}
                                       {1,5,6}
                                       {2,4,5}
                                       {2,4,6}
                                       {2,5,6}
                                       {3,4,6}
                                       {4,5,6}
                                       {2,4,5,6}

Andrew Howroyd, Table of n, a(n) for n = 0..100

The maximal case is A324744. The case of subsets of {2...n} is A324739. The strict integer partition version is A324749. The integer partition version is A324754. The Heinz number version is A324759. An infinite version is A324694.
Cf. A000720, A001221, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A279861, A290689, A290822, A304360, A306844.
Cf. A324695, A324736, A324741, A324750, A324755, A324760.

Table[Length[Select[Subsets[Range[n]],!MemberQ[#,k_/;SubsetQ[#,PrimePi/@First/@FactorInteger[k]]]&]],{n,0,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n,k,if(k==1, 1, pset(k))), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(bitnegimply(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 16 2019

A324742 Number of subsets of {2...n} containing no prime indices of the elements.

Original entry on oeis.org

1, 2, 3, 6, 10, 16, 24, 48, 84, 144, 228, 420, 648, 1080, 1800, 3600, 5760, 11136, 16704, 31104, 53568, 90624, 136896, 269952, 515712, 862080, 1708800, 3171840, 4832640, 9325440, 14890752, 29781504, 52245504, 88418304, 166017024, 331628544, 497645568, 829409280

Offset: 1

Gus Wiseman, Mar 15 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(1) = 1 through a(6) = 16 subsets:
  {}  {}   {}   {}     {}       {}
      {2}  {2}  {2}    {2}      {2}
           {3}  {3}    {3}      {3}
                {4}    {4}      {4}
                {2,4}  {5}      {5}
                {3,4}  {2,4}    {6}
                       {2,5}    {2,4}
                       {3,4}    {2,5}
                       {4,5}    {3,4}
                       {2,4,5}  {3,6}
                                {4,5}
                                {4,6}
                                {5,6}
                                {2,4,5}
                                {3,4,6}
                                {4,5,6}
An example for n = 20 is {4,5,6,12,17,18,19}, with prime indices:
   4: {1,1}
   5: {3}
   6: {1,2}
  12: {1,1,2}
  17: {7}
  18: {1,2,2}
  19: {8}
None of these prime indices {1,2,3,7,8} belong to the set, as required.

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

The maximal case is A324763. The version for subsets of {1...n} is A324741. The strict integer partition version is A324752. The integer partition version is A324757. The Heinz number version is A324761. An infinite version is A304360.
Cf. A000720, A001462, A007097, A076078, A084422, A085945, A112798, A276625, A290689, A290822, A306844, A324764.
Cf. A324695, A324737, A324743, A324751, A324756, A324758.

Table[Length[Select[Subsets[Range[2,n]],Intersection[#,PrimePi/@First/@Join@@FactorInteger/@#]=={}&]],{n,10}]

pset(n)={my(b=0,f=factor(n)[,1]); sum(i=1, #f, 1<<(primepi(f[i])))}
a(n)={my(p=vector(n-1,k,pset(k+1)>>1), d=0); for(i=1, #p, d=bitor(d, p[i]));
((k,b)->if(k>#p, 1, my(t=self()(k+1,b)); if(!bitand(p[k], b), t+=if(bittest(d,k), self()(k+1, b+(1<Andrew Howroyd, Aug 16 2019

Terms a(21) and beyond from Andrew Howroyd, Aug 16 2019

A324838 Number of unlabeled rooted trees with n nodes where the branches of no branch of the root form a submultiset of the branches of the root.

Original entry on oeis.org

1, 0, 1, 2, 5, 10, 28, 64, 169, 422, 1108, 2872, 7627, 20202, 54216, 145867, 395288

Offset: 1

Gus Wiseman, Mar 18 2019

			The a(1) = 1 through a(6) = 10 rooted trees:
  o  ((o))  ((oo))   ((ooo))    ((oooo))
            (((o)))  (((oo)))   (((ooo)))
                     ((o)(o))   ((o)(oo))
                     ((o(o)))   ((o(oo)))
                     ((((o))))  ((oo(o)))
                                ((((oo))))
                                (((o)(o)))
                                (((o(o))))
                                ((o((o))))
                                (((((o)))))

Cf. A000081, A290689, A304360, A306844, A317787, A318185.

Cf. A324694, A324696, A324704, A324738, A324744, A324758, A324759, A324765, A324768, A324771, A324839, A324840, A324844, A324846.

submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap];
rtall[n_]:=Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])];
Table[Length[Select[rtall[n],And@@Table[!submultQ[b,#],{b,#}]&]],{n,10}]

A318231 Number of inequivalent leaf-colorings of series-reduced rooted trees with n nodes.

Original entry on oeis.org

1, 0, 2, 3, 9, 23, 73, 229, 796, 2891, 11118, 44695, 187825, 820320, 3716501, 17413308, 84209071, 419461933, 2148673503, 11301526295, 60956491070, 336744177291, 1903317319015, 10995856040076, 64873456288903, 390544727861462, 2397255454976268, 14993279955728851

Offset: 1

Gus Wiseman, Aug 21 2018

nonn

In a series-reduced rooted tree, every non-leaf node has at least two branches.

			Inequivalent representatives of the a(6) = 23 leaf-colorings:
  (11(11))  (1(111))  (11111)
  (11(12))  (1(112))  (11112)
  (11(22))  (1(122))  (11122)
  (11(23))  (1(123))  (11123)
  (12(11))  (1(222))  (11223)
  (12(12))  (1(223))  (11234)
  (12(13))  (1(234))  (12345)
  (12(33))
  (12(34))

Cf. A000081, A001190, A001678, A003238, A004111, A290689, A291636, A304486.

Cf. A318226, A318227, A318228, A318229, A318230, A318234, A339645, A339648.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sEulerT(x*Ser(concat(v[1..n-2], [0]))), n-1 )); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(15)) \\ Andrew Howroyd, Dec 11 2020

Terms a(8) and beyond from Andrew Howroyd, Dec 11 2020

A324843 Number of unlabeled rooted trees with n nodes where the branches of any branch of any terminal subtree form a submultiset of the branches of the same subtree.

Original entry on oeis.org

1, 1, 1, 2, 2, 4, 4, 8, 9, 15, 17, 31, 35, 57, 70, 111, 136, 213, 265, 405, 517, 763, 987, 1458, 1893, 2736, 3611, 5161, 6836, 9702

Offset: 1

Gus Wiseman, Mar 18 2019

A subset of totally transitive rooted trees (A318185).

			The a(1) = 1 through a(8) = 8 rooted trees:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)    (oooooo)    (ooooooo)
                (o(o))  (oo(o))  (oo(oo))   (ooo(oo))   (ooo(ooo))
                                 (ooo(o))   (oooo(o))   (oooo(oo))
                                 (o(o)(o))  (oo(o)(o))  (ooooo(o))
                                                        (oo(o)(oo))
                                                        (ooo(o)(o))
                                                        (o(o)(o)(o))
                                                        (o(o)(o(o)))

The Matula-Goebel numbers of these trees are given by A324842.
Cf. A000081, A279861, A290689, A290822, A318185.
Cf. A324704, A324736, A324748, A324753, A324847, A324848, A324854.

submultQ[cap_,fat_]:=And@@Function[i,Count[fat,i]>=Count[cap,i]]/@Union[List@@cap];
rallt[n_]:=Select[Union[Sort/@Join@@(Tuples[rallt/@#]&/@IntegerPartitions[n-1])],And@@Table[submultQ[b,#],{b,#}]&];
Table[Length[rallt[n]],{n,10}]

cp's OEIS Frontend

A324969 Number of unlabeled rooted identity trees with n vertices whose non-leaf terminal subtrees are all different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A324768 Number of fully anti-transitive rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A325705 Number of integer partitions of n containing all of their distinct multiplicities.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A124343 Number of rooted trees on n nodes with thinning limbs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A301342 Regular triangle where T(n,k) is the number of rooted identity trees with n nodes and k leaves.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A324738 Number of subsets of {1...n} containing no element > 1 whose prime indices all belong to the subset.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324742 Number of subsets of {2...n} containing no prime indices of the elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A324838 Number of unlabeled rooted trees with n nodes where the branches of no branch of the root form a submultiset of the branches of the root.