|
|
A347289
|
|
Number of independent sets in the binomial tree of order n.
|
|
1
|
|
|
2, 3, 8, 60, 3456, 11612160, 132090377011200, 17175244766164688547348480000, 291347192866832125410134687322211469174161539072000000000, 84034354923469245337680441503007090893711465882978424632224243601869256327175152475648504794972160000000000000000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,1
|
|
COMMENTS
|
The binomial tree of order 0 is a single root vertex and order n>=1 is an order n-1 with another order n-1 joined as a subtree of the root.
Going by induction with this construction shows the number of sets where the root is in the set is with(n) = A052129(n), and the number where the root is not in the set is without(n) = A088679(n+1).
Among the total a(n), the respective proportions are without(n)/a(n) = (n+1)/(n+2) and with(n)/a(n) = 1/(n+2).
Also, a(n-1) is the number of maximum independent sets in binomial tree order n.
Tree n can be constructed from tree n-1 by adding a new child under each vertex. Each independent set in tree n-1 corresponds one-to-one with a maximum independent set in tree n by putting each new child in or out of the set opposite to its parent.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (n+2) * Product_{k=2..n} k^(2^(n-k)).
|
|
EXAMPLE
|
For n=5, the product formula is a(5) = 7 * 5 * 4^2 * 3^4 * 2^8 = 11612160.
|
|
PROG
|
(PARI) a(n) = my(P=1); for(k=2, n, P=sqr(P)*k); (n+2)*P;
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|