login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A242117 The number of independent sets in a complete binary tree with n levels (i.e., with 2^n-1 vertices) in which every vertex has degree 3. 0
0, 0, 3, 24, 1680, 5317635, 66314914699608, 8947678119828215014722891024, 178098260698995011212395018312912894502905113202338936835 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

For example, when n=3, there are two degree 3 vertices which do not share an edge. There are then three degree 3 (regular) independent subsets so a(3)=3. a(10) has 113 digits and is too large to include. The sequence is related to A076725, the number of independent sets in a complete binary tree.

The independent sets sought are those in the subgraph induced by the degree-3 vertices.  This subgraph is a forest comprising two complete binary trees with n-2 levels each.  These trees have A076725(n-2+1) independent sets each and the empty set (empty in both) is excluded here so a(n) = A076725(n-1)^2 - 1. - Kevin Ryde, Mar 10 2020

LINKS

Table of n, a(n) for n=1..9.

FORMULA

a(n) = (a(n-2) + 1)^4 + 2(a(n-1)+1)(a(n-2) + 1)^2 + (a(n-1) + 1)^2 - 1, with a(1) = a(2) = 0.

EXAMPLE

a(3) = (a(1) + 1)^4 + 2(a(2)+1)(a(1) + 1)^2 + (a(2) + 1)^2 - 1 = (0+1)^4+2(0+1)(0+1)^2+(0+1)^2-1 = 3.

a(4) = (a(2) + 1)^4 + 2(a(3)+1)(a(2) + 1)^2 + (a(3) + 1)^2 - 1 = (0+1)^4+2(3+1)(0+1)^2+(3+1)^2-1 = 24.

a(5) = (a(3) + 1)^4 + 2(a(4)+1)(a(3) + 1)^2 + (a(4) + 1)^2 - 1 = (3+1)^4+2(24+1)(3+1)^2+(24+1)^2-1 = 1680.

PROG

(PARI) a(n) = my(x=1, y=1); for(i=3, n, [x, y] = [(x + y^2)^2, x]); x-1; \\ Kevin Ryde, Mar 10 2020

CROSSREFS

Cf. A076725.

Sequence in context: A075655 A300551 A000856 * A047678 A047938 A297481

Adjacent sequences:  A242114 A242115 A242116 * A242118 A242119 A242120

KEYWORD

nonn

AUTHOR

Steven Kuipers and Bradford M. Morris, May 04 2014

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 4 13:35 EDT 2020. Contains 335448 sequences. (Running on oeis4.)