cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-4 of 4 results.

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

Original entry on oeis.org

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

Views

Author

Andrew Howroyd, Dec 19 2020

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

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

Programs

  • PARI
    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)}

A339831 Number of rooted bicolored trees on n nodes such that black nodes are not adjacent to each other.

Original entry on oeis.org

2, 3, 9, 28, 97, 346, 1302, 5014, 19830, 79813, 326344, 1350918, 5652334, 23861787, 101519790, 434827232, 1873491739, 8114411769, 35309142309, 154288183928, 676730773252, 2978405318453, 13149337960554, 58218455727085, 258435947527696, 1149982662789042
Offset: 1

Views

Author

Andrew Howroyd, Dec 19 2020

Keywords

Examples

			a(1) = 2: B, W.
a(2) = 3: B(W), W(B), W(W).
a(3) = 9: B(WW), W(BB), W(BW), W(WW), B(W(B)), B(W(W)), W(B(W)), W(W(B)), W(W(W)).

Links

Crossrefs

Cf. A038055 (rooted bicolored trees), A339830 (unrooted case), A339835, A339838.

Programs

  • PARI
    EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=v=[]); for(n=1, n, my(t=concat([1], EulerT(v))); v=concat([1], EulerT(u + v)); u=t); u + v}

A339838 Number of rooted bicolored trees on n unlabeled nodes such that black nodes are not adjacent to each other and every white node is adjacent to a black node.

Original entry on oeis.org

1, 2, 4, 10, 27, 75, 221, 662, 2042, 6402, 20407, 65828, 214720, 706600, 2343767, 7826752, 26293468, 88796471, 301290197, 1026595232, 3511246069, 12050780294, 41488523002, 143246116231, 495881545520, 1720771421470, 5984652387281, 20857113949868, 72829214554641, 254762923125929
Offset: 1

Views

Author

Andrew Howroyd, Dec 20 2020

Keywords

Links

Crossrefs

Cf. A038055 (rooted bicolored trees), A339831, A339835, A339837.

Programs

  • PARI
    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(v+w)); v=concat([0], t2-t1); w=concat([1], t1)); u+v}

A339833 Irregular triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with domination number k, n >= 1, 1 <= k <= A065033(n+1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 4, 1, 1, 5, 5, 1, 7, 13, 2, 1, 8, 27, 11, 1, 10, 47, 45, 3, 1, 11, 72, 124, 27, 1, 13, 103, 287, 141, 6, 1, 14, 140, 553, 528, 65, 1, 16, 182, 966, 1537, 446, 11, 1, 17, 230, 1538, 3712, 2080, 163, 1, 19, 284, 2323, 7788, 7516, 1366, 23
Offset: 1

Views

Author

Andrew Howroyd, Dec 19 2020

Keywords

Comments

A star graph has a domination number of 1 and for n > 1 a path on n nodes has domination number floor(n/2) which is the maximum possible for a connected graph.
A minimum dominating 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. Exclude all leaves from the dominating set (except possibly the root) and also greedily exclude any other node if all children are either in the dominating set or dominated by one of their children. This method can be converted into an algorithm to compute the number of trees by domination number. See the PARI program for technical details.

Examples

			Triangle begins:
  1;
  1;
  1;
  1,  1;
  1,  2;
  1,  4,  1;
  1,  5,  5;
  1,  7, 13,  2;
  1,  8, 27, 11;
  1, 10, 47, 45, 3;
  ...
There are 3 trees with 5 nodes:
    o                                     o
    |                                     |
    x---x---o    o---x---o---x---o    o---x---o
    |                                     |
    o                                     o
The first 2 of these have a minimum dominating set of 2 nodes and the last has a minimum dominating set of 1 node, so T(5,2)=2 and T(5,1)=1.

Links

Crossrefs

Row sums are A000055.
Cf. A065033, A332401 (connected graphs), A339829 (independence number), A339834, A339835.

Programs

  • PARI
    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,w count rooted trees weighted by domination number: u is root in set, v is root not in the set but dominatated by a child, w is root in set and not yet dominated.
T(n)={my(u=[0], v=[0], w=[1]); for(n=2, n, my(t1=EulerMT(v), t2=EulerMT(u+v)); u=y*concat([0], EulerMT(u+v+w)-t2); v=concat([0], t2-t1); w=concat([1], t1)); w*=y; my(g=x*Ser(u+v+w), gu=x*Ser(u), gw=x*Ser(w), r=Vec(g + (substvec(g, [x,y],[x^2,y^2]) - (1-1/y)*substvec(gw, [x,y], [x^2,y^2]) - g^2 + (1-1/y)*gw*(gw+2*gu) )/2)); vector(#r, n, Vecrev(r[n]/y))}
Showing 1-4 of 4 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.