Recurrences which involve polynomials with discriminant $d=11,19,43,67,163$

117 Views Asked by At

Q: Which of these sequences, if any, can be grouped as similar or generalizations of each other?

Update 1: Since a ternary word or string of length n is "a string of n characters where the characters are either 0, 1 or 2", then $\color{red}{\text{A119826}}\,$ and $\color{red}{\text{A255115}}\,$ are similar. That takes care of $d=67$ and $d=43$.

Update 2: For $d=19$, we have A061279 for a binary word. Can we come up with a ternary version?


I. $d = 163:\,$ Recurrence $a_n -6a_{n-1} + 4a_{n-2} - 2a_{n-3}=0$

A003731 The number of Hamiltonian cycles in $C_5 \times P_n$

II. $d = 67:\,$ Recurrence $a_n -2a_{n-1} -2a_{n-2} - 2a_{n-3}=0$

$\color{red}{\text{A119826}}\,$ Number of ternary words of length n with no 000's

A181137 The number of ways to color n balls in a row with 3 colors with no color runs having lengths greater than 3

III. $d = 43:\,$ Recurrence $a_n -2a_{n-1} - 2a_{n-3}=0$

A077999 Number of permutations on [n] that avoid nonconsecutive instances of the patterns 321 and 312

$\color{red}{\text{A255115}}\,$ Number of n - length words on {0, 1, 2} in which 0 appears only in runs of length 2

IV. $d = 19:\,$ Recurrence $a_n - 2a_{n-2} - 2a_{n-3}=0$

A061279 Counts (binary) bit strings of length n in which no odd length block of 0's is followed by an odd length block of 1's

A052907 Counts ordered walks of weight n on a single vertex graph containing 4 distinctly labelled loops of weights 2, 2, 3 and 3

A107383 The number of maximal independent vertex sets (and minimal vertex covers) in the 2 X (n - 2) king graph

V. $d = 11:\,$ Recurrence $a_n -2a_{n-1} + 2a_{n-2} - 2a_{n-3}=0$

A104767 Number of terms in the expansion of (x - 1)(x - 1)(x^2 - 1)(x^3 - 1) ...(x^F_n - 1), where F_n is the nth Fibonacci number

A122788 (1, 3) - entry of the 3 X 3 matrix M^n, where M = {{0, -1, 1}, {1, 1, 0}, {0, 1, 1}}


P.S. To elaborate, from the recurrence,

$$a_n -6a_{n-1} + 4a_{n-2} - 2a_{n-3}=0$$

we get the cubic characteristic equation,

$$x^3-6x^2+4x-2=0$$

the real root $x = 5.318628\dots$ of which is the limiting ratio. Incidentally,

$$e^{\pi\sqrt{163}} \approx x^{24}-24.00000000000000105\dots$$