%I #101 Feb 19 2024 11:18:58
%S 1,3,4,10,18,42,84,192,409,926,2030,4577,10171,22889,51176,115070,
%T 257987,579868,1301664,2925209,6569992,14763529,33166848,74527233,
%U 167446566,376253517,845401158,1899609267,4268309531,9590827171,21550227328,48422972296,108805058758
%N a(n) is the number of different linear hydrocarbon molecules with n carbon atoms.
%C Linear hydrocarbons are molecules made of carbon (C) and hydrogen (H) atoms organized without cycles.
%C a(n) <= A002986(n) because molecules can be acyclic but not linear (i.e., including carbon atoms bonded with more than two other carbons).
%C From _Petros Hadjicostas_, Nov 16 2019: (Start)
%C 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.
%C 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)).
%C 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.
%C 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.
%C 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.
%C 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.
%C 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)
%H Vincent Champain, <a href="/A306334/b306334.txt">Table of n, a(n) for n = 1..1000</a>
%H L. Edson Jeffery, <a href="https://oeis.org/A220555/a220555_2.pdf">Danzer matrices (unit-primitive matrices)</a>. [It contains a discussion of a generalization of the matrix M that appears in the formula for a(n). See basis D_7.]
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem">Cayley-Hamilton theorem</a>.
%H R. Witula, D. Slota, and A. Warzynski, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Slota/slota57.html">Quasi-Fibonacci Numbers of the Seventh Order</a>, 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).]
%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (2, 3, -5, -1, 0, -2, 3, 1, -1).
%F 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]
%F Conjectures from _Vaclav Kotesovec_, Feb 12 2019: (Start)
%F 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.
%F 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]
%F From _Petros Hadjicostas_, Nov 17 2019: (Start)
%F a(2*n) = (1/2)*(A006356(2*n-1) + A006356(n)).
%F a(2*n-1) = (1/2)*(A006356(2*n-2) + A006054(n+1)). (End)
%e For n=1, there is one possibility: CH4.
%e For n=2, there are 3 solutions: CHCH, CH3CH3, CH2CH2.
%e For n=3, there are 4 solutions: CHCCH3, CH2CCH2, CH3CHCH2, CH3CH2CH3.
%e 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.
%p with(LinearAlgebra):
%p M := Matrix([[0, 0, 1], [0, 1, 1], [1, 1, 1]]):
%p X := proc(n) MatrixPower(M, n - 2): end proc:
%p Y := proc(n) MatrixPower(M, floor(1/2*n) - 2): end proc:
%p 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))):
%p end proc:
%p seq(a(n), n=1..40); # _Petros Hadjicostas_, Nov 17 2019
%t M = {{0, 0, 1}, {0, 1, 1}, {1, 1, 1}};
%t X[n_] := MatrixPower[M, n - 2];
%t Y[n_] := MatrixPower[M, Floor[1/2*n] - 2];
%t 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}])];
%t Table[a[n], {n, 1, 40}] (* _Jean-François Alcover_, Aug 16 2023, after _Petros Hadjicostas_ *)
%o (Python)
%o from numpy import array as npa
%o from numpy.linalg import matrix_power as npow
%o def F(n):
%o if n<4: return([0,1,3,4][n])
%o m=npa([[0,0,1],[0,1,1],[1,1,1]],dtype=object)
%o m2=npow(m,n//2-2)
%o return((sum(sum(npow(m,n-2)))+sum(sum(m2[j]*min(j+1,3-(n&1)) for j in range(3))))//2)
%Y Other hydrocarbon related sequences: A002986, A018190, A129012.
%Y Cf. A006054, A006356.
%K nonn
%O 1,2
%A _Vincent Champain_, Feb 08 2019