A339833 -id:A339833 - cp's OEIS frontend

A339834 Number of bicolored trees on n unlabeled nodes such that every white node is adjacent to a black node.

1, 1, 2, 4, 11, 29, 91, 299, 1057, 3884, 14883, 58508, 235771, 967790, 4037807, 17074475, 73058753, 315803342, 1377445726, 6056134719, 26817483095, 119516734167, 535751271345, 2414304071965, 10932421750492, 49723583969029, 227079111492652, 1040939109111200, 4788357522831785

Offset: 0

Andrew Howroyd, Dec 19 2020

nonn

The black nodes form a dominating set. For n > 0, a(n) is then the total number of indistinguishable dominating sets summed over distinct unlabeled trees with n nodes.

			a(2) = 2 because at most one node can be colored white.
a(3) = 4 because the only tree is the path graph P_3. If the center node is colored white then both of the ends must be colored black; otherwise zero, one or both of the ends can be colored black. In total there are 4 possibilities.

Andrew Howroyd, Table of n, a(n) for n = 0..500
Eric Weisstein's World of Mathematics, Dominating Set

Cf. A038056 (bicolored trees), A339830, A339833, A339835 (rooted), A339836, A339837.

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=w=[]); for(n=1, n, my(t1=EulerT(v), t2=EulerT(u+v)); u=concat([1], EulerT(u+v+w)); v=concat([0], t2-t1); w=concat([1], t1)); my(g=x*Ser(u+v), guw=x^2*Ser(u)*Ser(w)); Vec(1 + g + (subst(g,x,x^2) - g^2 - 2*guw)/2)}

A339829 Triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with independence number k.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 3, 1, 0, 0, 0, 0, 6, 4, 1, 0, 0, 0, 0, 5, 12, 5, 1, 0, 0, 0, 0, 0, 20, 20, 6, 1, 0, 0, 0, 0, 0, 15, 52, 31, 7, 1, 0, 0, 0, 0, 0, 0, 76, 107, 43, 8, 1, 0, 0, 0, 0, 0, 0, 49, 242, 192, 58, 9, 1, 0, 0, 0, 0, 0, 0, 0, 313, 589, 313, 75, 10, 1, 0

Offset: 1

Andrew Howroyd, Dec 18 2020

For n > 1, a star graph on n nodes has independence number n-1 and a path graph has independence number ceiling(n/2) which is the least possible in a tree.

A maximum independent set can be found in a tree using a greedy algorithm. First choose any node to be the root and perform a depth first search from the root. Include all leaves in the independent set (except possibly the root) and also greedily include any other node if no children are in the set. This method can be converted into an algorithm to compute the number of trees by independence number. See the PARI program for technical details.

			Triangle begins:
  1;
  1, 0;
  0, 1, 0;
  0, 1, 1, 0;
  0, 0, 2, 1,  0;
  0, 0, 2, 3,  1,  0;
  0, 0, 0, 6,  4,  1,  0;
  0, 0, 0, 5, 12,  5,  1, 0;
  0, 0, 0, 0, 20, 20,  6, 1, 0;
  0, 0, 0, 0, 15, 52, 31, 7, 1, 0;
  ...
There are 3 trees with 5 nodes:
    x                                     x
    |                                     |
    o---x---o    x---o---x---o---x    x---o---x
    |                                     |
    x                                     x
The first 2 of these have a maximum independent set of 3 nodes and the last has a maximum independent set of 4 nodes, so T(5,3)=2 and T(5,4)=1.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
Eric Weisstein's World of Mathematics, Independence Number

Row sums are A000055.

Cf. A294490 (connected graphs), A339830, A339831, A339833 (domination number).

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1, -n)}
\\ In the following, u,v count rooted trees weighted by independence number: u is root in the set and v is root not in the set.
T(n)={my(u=[y], v=[0]); for(n=2, n, my(t=EulerMT(v)); v=concat([0], EulerMT(u+v)-t); u=y*concat([1], t)); my(g=x*Ser(u+v), gu=x*Ser(u), r=Vec(g + (substvec(g, [x,y], [x^2,y^2]) - (1-1/y)*substvec(gu, [x,y], [x^2,y^2]) - g^2 + (1-1/y)*gu^2 )/2)); vector(#r, n, Vecrev(r[n]/y, n))}
{ my(A=T(10)); for(n=1, #A, print(A[n])) }

cp's OEIS Frontend

A339834 Number of bicolored trees on n unlabeled nodes such that every white node is adjacent to a black node.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI