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.

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

Original entry on oeis.org

1, 2, 2, 4, 10, 26, 75, 234, 768, 2647, 9466, 34818, 131149, 503640, 1965552, 7777081, 31138051, 125961762, 514189976, 2115922969, 8769932062, 36584593158, 153510347137, 647564907923, 2744951303121, 11687358605310, 49965976656637, 214423520420723, 923399052307921
Offset: 0

Views

Author

Andrew Howroyd, Dec 19 2020

Keywords

Comments

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

Examples

			a(2) = 2 because at most one node can be colored black.
a(3) = 4 because the only tree is the path graph P_3. If the center node is colored black then neither of the ends can be colored black; otherwise zero, one or both of the ends can be colored black. In total there are 4 possibilities.
There are 3 trees with 5 nodes:
    o                                     o
    |                                     |
    o---o---o    o---o---o---o---o    o---o---o
    |                                     |
    o                                     o
These correspond respectively to 11, 9 and 6 bicolored trees (with black nodes not adjacent), so a(5) = 11 + 9 + 6 = 26.

Links

Crossrefs

Cf. A038056 (bicolored trees), A339829, A339831, A339832, A339834, A339837.

Programs

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

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

Original entry on oeis.org

1, 3, 9, 30, 111, 424, 1705, 7024, 29692, 127748, 558219, 2469403, 11039992, 49796803, 226348740, 1035750855, 4767429667, 22058219466, 102534463563, 478602668159, 2242383155726, 10541976883286, 49714185649417, 235109360767014, 1114782699692044, 5298494249055391
Offset: 1

Views

Author

Andrew Howroyd, Dec 19 2020

Keywords

Examples

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

Links

Crossrefs

Cf. A038055 (rooted bicolored trees), A339831, A339834 (unrooted), A339838.

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)); 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}

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

Views

Author

Andrew Howroyd, Dec 18 2020

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

Row sums are A000055.
Cf. A294490 (connected graphs), A339830, A339831, A339833 (domination number).

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 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])) }
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.