A347289 Number of independent sets in the binomial tree of order n.

2, 3, 8, 60, 3456, 11612160, 132090377011200, 17175244766164688547348480000, 291347192866832125410134687322211469174161539072000000000, 84034354923469245337680441503007090893711465882978424632224243601869256327175152475648504794972160000000000000000

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

Kevin Ryde, Table of n, a(n) for n = 0..12

Formula

a(n) = (n+2) * Product_{k=2..n} k^(2^(n-k)).

a(n) = A052129(n) + A088679(n+1).

a(n) = a(n-1)^2 - A052129(n-1)^2.

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

Cf. A052129, A088679.

Sequence in context: A329496 A160634 A072043 * A095203 A351658 A003096

Adjacent sequences: A347286 A347287 A347288 * A347290 A347291 A347292

Keyword

nonn

Author

Kevin Ryde, Sep 26 2021

Status

approved