A306334 a(n) is the number of different linear hydrocarbon molecules with n carbon atoms.

1, 3, 4, 10, 18, 42, 84, 192, 409, 926, 2030, 4577, 10171, 22889, 51176, 115070, 257987, 579868, 1301664, 2925209, 6569992, 14763529, 33166848, 74527233, 167446566, 376253517, 845401158, 1899609267, 4268309531, 9590827171, 21550227328, 48422972296, 108805058758

Offset: 1

Author

Vincent Champain, Feb 08 2019

Keywords

• nonn
• easy

Comments

Linear hydrocarbons are molecules made of carbon (C) and hydrogen (H) atoms organized without cycles.

a(n) <= A002986(n) because molecules can be acyclic but not linear (i.e., including carbon atoms bonded with more than two other carbons).

From Petros Hadjicostas, Nov 16 2019: (Start)

We prove Vaclav Kotesovec's conjectures from the Formula section. Let M = [[0,0,1], [0,1,1], [1,1,1]], X(n) = M^(n-2), and Y(n) = M^(floor(n/2)-2) = X(floor(n/2)) (with negative powers indicating matrix inverses). Let also, t_1 = [1,1,1]^T, t_2 = [1,2,2]^T, and t_3 = [1,2,3]^T. In addition, define b(n) = (1/2)*(t_1^T X(n) t_1) and c(n) = (1/2)*(t_3^T Y(n) t_1) if n is even and = (1/2)*(t_2^T Y(n) t_1) if n is odd.

We have a(n) = b(n) + c(n) for n >= 1. Since the characteristic polynomial of Vaclav Kotesovec's recurrence is x^9 - 2*x^8 - 3*x^7 + 5*x^6 + x^5 + 2*x^3 - 3*x^2 - x + 1 = g(x)*g(x^2), where g(x) = x^3 - 2*x^2 - x + 1, to prove his first conjecture, it suffices to show that b(n) - 2*b(n-1) - b(n-2) + b(n-3) = 0 (whose characteristic polynomial is g(x)) and c(n) - 2*c(n-2) - c(n-4) + c(n-6) = 0 (whose characteristic polynomial is g(x^2)).

Note that 2*b(n) = A006356(n-1) for n >= 1. (See the comments by L. Edson Jeffery and R. J. Mathar in the documentation of that sequence.) Also, 2*c(2*n) = A006356(n) and 2*c(2*n-1) = A006054(n+1) for n >= 1.

Properties of the polynomial g(x) = x^3 - 2*x^2 - x + 1 and its roots were studied by Witula et al. (2006) (see Corollary 2.4). This means that a(n) can essentially be expressed in terms of exp(I*2*Pi/7), but we omit the discussion. See also the comments for sequence A006054.

The characteristic polynomial of matrix M is g(x). By the Cayley-Hamilton theorem, 0 = g(M) = M^3 - 2*M^2 - M + I_3, and thus, for n >= 5, X(n) - 2*X(n-1) - X(n-2) + X(n-3) = M^(n-2) - 2*M^(n-3) - M^(n-4) + M^(n-5) = 0. Pre-multiplying by (1/2)*t_1^T and post-multiplying by t_1, we get that b(n) - 2*b(n-1) - b(n-2) + b(n-3) = 0 for n >= 5.

Similarly, for n >= 10, Y(n) - 2*Y(n-2) - Y(n-4) + Y(n-6) = X(floor(n/2)) - 2*X(floor((n-2)/2)) - X(floor((n-4)/2)) + X(floor((n-6)/2)) = X(floor(n/2)) - 2*X(floor(n/2) - 1) - X(floor(n/2) - 2) + X(floor(n/2) - 3) = 0. Pre-multiplying by (1/2)*t_3^T (when n is even) or by (1/2)*t_2^T (when n is odd), and post-multiplying by t_1, we get c(n) - 2*c(n-2) - c(n-4) + c(n-6) = 0 for n >= 10.

Since the characteristic polynomial of Vaclav Kotesovec's recurrence is g(x)*g(x^2), which is a polynomial of degree 9, the denominator of the g.f. of the sequence (a(n): n >= 1) should be x^9*g(1/x)*g(1/x^2) = (1 - 2*x - x^2 + x^3)*(1 - 2*x^2 - x^4 + x^6), as Vaclav Kotesovec conjectured below. The numerator of Vaclav Kotesovec's g.f. can be easily derived using the initial conditions (from a(1) = 1 to a(9) = 409). (End)

Examples

			For n=1, there is one possibility: CH4.
For n=2, there are 3 solutions: CHCH, CH3CH3, CH2CH2.
For n=3, there are 4 solutions: CHCCH3, CH2CCH2, CH3CHCH2, CH3CH2CH3.
For n=6, there are 42 solutions: CH3CH2CHCHCCH, CH3CH2CHCHCH2CH3, CH2CHCCCHCH2, CH2CHCHCHCH2CH3, CH2CHCHCHCCH, CH2CCCCHCH3, CHCCCCHCH2, CH3CHCHCHCHCH3, CHCCHCHCCH, CH2CCCCCH2, CH3CCCH2CH2CH3, CH3CCCCCH3, CH3CH2CH2CH2CH2CH3, CH2CHCHCHCHCH2, CH2CCHCH2CHCH2, CH3CHCCCHCH3, CHCCH2CH2CH2CH3, CHCCH2CH2CCH, CH3CCCH2CHCH2, CH2CCCHCH2CH3, CH2CCCHCCH, CHCCH2CCCH3, CHCCH2CHCCH2, CH3CH2CH2CH2CHCH2, CH2CHCHCCHCH3, CH3CH2CCCH2CH3, CH2CHCH2CH2CHCH2, CH2CHCHCCCH2, CH3CHCCHCH2CH3, CH3CH2CH2CHCHCH3, CH3CHCCHCCH, CHCCH2CH2CHCH2, CH3CHCHCCCH3, CH2CCHCCCH3, CH3CHCHCHCCH2, CHCCCCH2CH3, CH2CHCH2CHCHCH3, CH2CCHCHCCH2, CHCCCCCH, CH2CCHCH2CH2CH3, CH3CH2CCCHCH2, CHCCH2CHCHCH3.
		

Links

• Vincent Champain, Table of n, a(n) for n = 1..1000
• L. Edson Jeffery, Danzer matrices (unit-primitive matrices). [It contains a discussion of a generalization of the matrix M that appears in the formula for a(n). See basis D_7.]
• Wikipedia, Cayley-Hamilton theorem.
• R. Witula, D. Slota, and A. Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq. 9 (2006), Article 06.4.3. [See Corollary 2.4 and the discussion about the polynomial p_7(x) and its roots. This essentially proves that a(n) can be expressed in terms of exp(I*2*Pi/7).]
• Index entries for linear recurrences with constant coefficients, signature (2,3,-5,-1,0,-2,3,1,-1).

Crossrefs

Other hydrocarbon related sequences: A002986, A018190, A129012.

Cf. A006054, A006356.

Programs

Maple

with(LinearAlgebra):
M := Matrix([[0, 0, 1], [0, 1, 1], [1, 1, 1]]):
X := proc(n) MatrixPower(M, n - 2): end proc:
Y := proc(n) MatrixPower(M, floor(1/2*n) - 2): end proc:
a := proc(n) `if`(n < 4, [1,3,4][n], 1/2*(add(add(X(n)[i, j], i = 1..3), j = 1..3) + add(add(Y(n)[i, j]*min(j, 3 - (n mod 2)), i = 1..3), j = 1..3))):
     end proc:
seq(a(n), n=1..40); # Petros Hadjicostas, Nov 17 2019

Mathematica

M = {{0, 0, 1}, {0, 1, 1}, {1, 1, 1}};
X[n_] := MatrixPower[M, n - 2];
Y[n_] := MatrixPower[M, Floor[1/2*n] - 2];
a[n_] := If[n < 4, {1, 3, 4}[[n]], 1/2*(Sum[Sum[X[n][[i, j]], {i, 1, 3}], {j, 1, 3}] + Sum[Sum[Y[n][[i, j]]*Min[j, 3 - Mod[n, 2]], {i, 1, 3}], {j, 1, 3}])];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Aug 16 2023, after Petros Hadjicostas *)

Python

from numpy import array as npa
from numpy.linalg import matrix_power as npow
def F(n):
     if n<4: return([0,1,3,4][n])
     m=npa([[0,0,1],[0,1,1],[1,1,1]],dtype=object)
     m2=npow(m,n//2-2)
     return((sum(sum(npow(m,n-2)))+sum(sum(m2[j]*min(j+1,3-(n&1)) for j in range(3))))//2)

Formula

a(n) = (1/2) * (Sum_{i,j = 1..3} X_{ij} + Sum_{i,j = 1..3} Y_{ij} * min(j, 3 - (n&1))), where M = [[0,0,1], [0,1,1], [1,1,1]], X = [X_{ij}: i,j = 1..3] = M^(n-2), and Y = [Y_{ij}: i,j = 1..3] = M^(floor(n/2)-2)) for n >= 1 (with negative powers indicating matrix inverses). [Edited by Petros Hadjicostas, Nov 16 2019]

Conjectures from Vaclav Kotesovec, Feb 12 2019: (Start)

a(n) = 2*a(n-1) + 3*a(n-2) - 5*a(n-3) - a(n-4) - 2*a(n-6) + 3*a(n-7) + a(n-8) - a(n-9), for n >= 10.

G.f.: (1 - x - 2*x^2 - x^4 + 2*x^5 + x^6 - x^7) / ((1 - 2*x - x^2 + x^3)*(1 - 2*x^2 - x^4 + x^6)) - 1. (End) [These conjectures are true. See my comments above. - Petros Hadjicostas, Nov 17 2019]

From Petros Hadjicostas, Nov 17 2019: (Start)

a(2*n) = (1/2)*(A006356(2*n-1) + A006356(n)).

a(2*n-1) = (1/2)*(A006356(2*n-2) + A006054(n+1)). (End)