A358504 Number of genetic relatives of a person M in a genealogical tree extending back n generations and where everyone has 3 children down to the generation of M.
1, 5, 25, 137, 793, 4697, 28057, 168089, 1008025, 6047129, 36280729, 217680281, 1306073497, 7836424601, 47018514841, 282111023513, 1692666010009, 10155995797913, 60935974263193, 365615844530585, 2193695065086361, 13162170386323865, 78973022309554585
Offset: 0
Examples
For n=2, the tree comprises a(2) = 25 people,
G-------G G-------G G = 4 grandparents
/ | \ / | \ P = 2 parents
U U P---P U U S = 2 siblings
/|\ /|\ /|\ /|\ /|\ U = 4 uncles (or aunts)
C C C C C C S M S C C C C C C C = 12 cousins
The spouses of U are not shown and are not genetic relatives of M.
Links
- Paolo Xausa, Table of n, a(n) for n = 0..1000
- Hans Braxmeier, Calculating the number of genetic relative people in a genealogical tree.
- Index entries for linear recurrences with constant coefficients, signature (9,-20,12).
Crossrefs
Programs
-
Mathematica
A358504[n_] := 2^n + 3*(6^n-1)/5; Array[A358504, 25, 0] (* or *) LinearRecurrence[{9, -20, 12}, {1, 5, 25}, 25] (* Paolo Xausa, Feb 09 2024 *)
-
PARI
a(n) = (3^(n+1)+5)<
Kevin Ryde, Nov 23 2022 -
Python
for n in range(0,23): print(2**n+3*(6**n-1)//5)
Formula
a(n) = 2^n + 3*(6^n - 1)/5.
a(n) = 2*(A154407(n) + 1)/5 - 1. - Hugo Pfoertner, Nov 22 2022
Comments