A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

1, 1, 1, 2, 3, 2, 5, 17, 12, 5, 12, 73, 95, 44, 12, 33, 369, 721, 512, 168, 33, 90, 1795, 5487, 5480, 2556, 625, 90, 261, 9192, 41945, 58990, 36711, 12306, 2342, 261, 766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766, 2312, 249164, 2483192, 6593103, 7141755, 3965673, 1283624, 258887, 32313, 2312

Offset

1,4

Comments

Only the leaves are colored. Equivalence is up to permutation of the colors.

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

Links

Table of n, a(n) for n=1..55.

Andrew Howroyd, PARI Functions for Combinatorial Species, v2, Dec 2020.

Wikipedia, Combinatorial species

Example

Triangle begins:
    1;
    1,     1;
    2,     3,      2;
    5,    17,     12,      5;
   12,    73,     95,     44,     12;
   33,   369,    721,    512,    168,     33;
   90,  1795,   5487,   5480,   2556,    625,    90;
  261,  9192,  41945,  58990,  36711,  12306,  2342,  261;
  766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766;
  ...
From Gus Wiseman, Jan 02 2021: (Start)
Non-isomorphic representatives of the 39 = 5 + 17 + 12 + 5 trees with four colored leaves:
  (1111)      (1112)      (1123)      (1234)
  (1(111))    (1122)      (1(123))    (1(234))
  (11(11))    (1(112))    (11(23))    (12(34))
  ((11)(11))  (11(12))    (12(13))    ((12)(34))
  (1(1(11)))  (1(122))    (2(113))    (1(2(34)))
              (11(22))    (23(11))
              (12(11))    ((11)(23))
              (12(12))    (1(1(23)))
              (2(111))    ((12)(13))
              ((11)(12))  (1(2(13)))
              (1(1(12)))  (2(1(13)))
              ((11)(22))  (2(3(11)))
              (1(1(22)))
              (1(2(11)))
              ((12)(12))
              (1(2(12)))
              (2(1(11)))
(End)

Prog

(PARI) \\ See link above for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
{my(A=InequivalentColoringsTriangle(cycleIndexSeries(10))); for(n=1, #A~, print(A[n, 1..n]))}

Crossrefs

The case with only one color is A000669.

Counting by nodes gives A318231.

A labeled version is A319376.

Row sums are A330470.

A000311 counts singleton-reduced phylogenetic trees.

A001678 counts unlabeled lone-child-avoiding rooted trees.

A005121 counts chains of set partitions, with maximal case A002846.

A005804 counts phylogenetic rooted trees with n labels.

A060356 counts labeled lone-child-avoiding rooted trees.

A141268 counts lone-child-avoiding rooted trees with leaves summing to n.

A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.

A316651 counts lone-child-avoiding rooted trees with normal leaves.

A316652 counts lone-child-avoiding rooted trees with strongly normal leaves.

A330465 counts inequivalent leaf-colorings of phylogenetic rooted trees.

Cf. A196545, A213427, A281118, A289501, A292504, A318812, A319312, A330627.

Sequence in context: A350177 A162687 A010242 * A318956 A086507 A133568

Adjacent sequences: A339642 A339643 A339644 * A339646 A339647 A339648

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 11 2020

Status

approved