cp's OEIS Frontend

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

%I A339829 #15 Feb 16 2025 08:34:01
%S A339829 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,
%T A339829 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,
%U A339829 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
%N A339829 Triangle read by rows: T(n,k) is the number of unlabeled trees on n vertices with independence number k.
%C A339829 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.
%C A339829 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.
%H A339829 Andrew Howroyd, <a href="/A339829/b339829.txt">Table of n, a(n) for n = 1..1275</a> (rows 1..50)
%H A339829 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependenceNumber.html">Independence Number</a>
%e A339829 Triangle begins:
%e A339829   1;
%e A339829   1, 0;
%e A339829   0, 1, 0;
%e A339829   0, 1, 1, 0;
%e A339829   0, 0, 2, 1,  0;
%e A339829   0, 0, 2, 3,  1,  0;
%e A339829   0, 0, 0, 6,  4,  1,  0;
%e A339829   0, 0, 0, 5, 12,  5,  1, 0;
%e A339829   0, 0, 0, 0, 20, 20,  6, 1, 0;
%e A339829   0, 0, 0, 0, 15, 52, 31, 7, 1, 0;
%e A339829   ...
%e A339829 There are 3 trees with 5 nodes:
%e A339829     x                                     x
%e A339829     |                                     |
%e A339829     o---x---o    x---o---x---o---x    x---o---x
%e A339829     |                                     |
%e A339829     x                                     x
%e A339829 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.
%o A339829 (PARI)
%o A339829 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)}
%o A339829 \\ 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.
%o A339829 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))}
%o A339829 { my(A=T(10)); for(n=1, #A, print(A[n])) }
%Y A339829 Row sums are A000055.
%Y A339829 Cf. A294490 (connected graphs), A339830, A339831, A339833 (domination number).
%K A339829 nonn,tabl
%O A339829 1,13
%A A339829 _Andrew Howroyd_, Dec 18 2020