# Straight Chain Alk*nes without Order

This is much like my earlier challenge, except, this time, order doesn't matter.

A straight-chain alk*ne is defined as a sequence of carbon atoms connected by single (alkane), double (alkene), or triple bonds (alkyne), (implicit hydrogens are used.) Carbon atoms can only form 4 bonds, so no carbon atom may be forced to have more than four bonds. A straight-chain alk*ne can be represented as a list of its carbon-carbon bonds.

These are some examples of valid (not necessarily distinct) straight-chain alk*nes:

[]       CH4              Methane
[1]      CH3-CH3          Ethane
[2]      CH2=CH2          Ethene
[3]      CH≡CH            Ethyne
[1,1]    CH3-CH2-CH3      Propane
[1,2]    CH3-CH=CH2       Propene
[1,3]    CH3-C≡CH         Propyne
[2,1]    CH2=CH-CH3       Propene
[2,2]    CH2=C=CH2        Allene (Propadiene)
[3,1]    CH≡C-CH3         Propyne
[1,1,1]  CH3-CH2-CH2-CH3  Butane
...


While these are not, as at least one carbon atom would have more than 4 bonds:

[2,3]
[3,2]
[3,3]
...


Two straight-chain alk*nes, p and q are considered equivalent if p is q reversed, or p is q.

[1] = [1]
[1,2] = [2,1]
[1,3] = [3,1]
[1,1,2] = [2,1,1]
[1,2,2] = [2,2,1]


Your task is to create a program/function that, given a positive integer n, outputs/returns the number of valid straight-chain alk*nes of exactly n carbon atoms in length.

# Specifications/Clarifications

• You must handle 1 correctly by returning 1.
• Alk*nes like [1,2] and [2,1] are NOT considered distinct.
• Output is the length of a list of all the possible alk*nes of a given length.
• You do not have to handle 0 correctly.

# Test Cases:

1 => 1
2 => 3
3 => 4
4 => 10
5 => 18
6 => 42


This is code golf, so the lowest byte count wins!

• Are we supposed to guess what the correct number is? If not, can you specify how we figure it out? Specifically: Is every sequence (of the given length) that doesn't contain two adjacent numbers that sum to more than 4 valid? If so, can you edit that info in the question post? – msh210 Dec 18 '16 at 21:32
• Too much similar to Number of Straight-Chain Alk*nes of given length – JungHwan Min Dec 18 '16 at 21:32
• That help at all? – Zacharý Dec 18 '16 at 21:40
• @JungHwanMin Why do you think so? I'm not seeing an obvious way to reuse any of the non-brute force answers from that challenge. – Martin Ender Dec 18 '16 at 22:19
• @MartinEnder The answer is simply (# of straight-chain alk*nes)/2 + (# of symmetrical straight-chain alk*nes)/2 – JungHwan Min Dec 18 '16 at 23:30

A=n=>n>9?2*A(n-1)+3*A(n-2)+3*A(n-7)+A(n-8)-5*A(n-3)-A(n-4)-2*A(n-6)-A(n-9):[0,1,3,4,10,18,42,84,192,409][n]

Recursive solution, using the recurrence relation that was pointed out in the comments of the question. Execution time rises much quicker than the input (complexity of O(9^N) if I'm not mistaken), so be careful with values higher than 20.