login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A339829 Triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with independence number k. 3
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,13

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.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)

Eric Weisstein's World of Mathematics, Independence Number

EXAMPLE

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.

PROG

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

CROSSREFS

Row sums are A000055.

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

Sequence in context: A116402 A093323 A106278 * A177517 A227819 A064287

Adjacent sequences:  A339826 A339827 A339828 * A339830 A339831 A339832

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Dec 18 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 28 04:02 EDT 2022. Contains 354112 sequences. (Running on oeis4.)