cp's OEIS Frontend

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

%I A347289 #22 Sep 30 2021 11:46:10
%S A347289 2,3,8,60,3456,11612160,132090377011200,17175244766164688547348480000,
%T A347289 291347192866832125410134687322211469174161539072000000000,
%U A347289 84034354923469245337680441503007090893711465882978424632224243601869256327175152475648504794972160000000000000000
%N A347289 Number of independent sets in the binomial tree of order n.
%C A347289 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.
%C A347289 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).
%C A347289 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).
%C A347289 Also, a(n-1) is the number of maximum independent sets in binomial tree order n.
%C A347289 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.
%H A347289 Kevin Ryde, <a href="/A347289/b347289.txt">Table of n, a(n) for n = 0..12</a>
%F A347289 a(n) = (n+2) * Product_{k=2..n} k^(2^(n-k)).
%F A347289 a(n) = A052129(n) + A088679(n+1).
%F A347289 a(n) = a(n-1)^2 - A052129(n-1)^2.
%e A347289 For n=5, the product formula is a(5) = 7 * 5 * 4^2 * 3^4 * 2^8 = 11612160.
%o A347289 (PARI) a(n) = my(P=1); for(k=2,n,P=sqr(P)*k); (n+2)*P;
%Y A347289 Cf. A052129, A088679.
%K A347289 nonn
%O A347289 0,1
%A A347289 _Kevin Ryde_, Sep 26 2021