# 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
[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? Dec 18, 2016 at 21:32
• Too much similar to Number of Straight-Chain Alk*nes of given length Dec 18, 2016 at 21:32
• That help at all? Dec 18, 2016 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. Dec 18, 2016 at 22:19
• @MartinEnder The answer is simply (# of straight-chain alk*nes)/2 + (# of symmetrical straight-chain alk*nes)/2 Dec 18, 2016 at 23:30

# JavaScript (ES6), 107 bytes

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.

• Winner by default. Apr 16, 2017 at 19:42

# MMIX, 108 92 bytes (27 23 instrs)

Works mod $$\2^{63}\$$, because it uses the two-part recurrence instead of the one-part, due to the two-part recurrence being much easier to compute.

(jxd)

00000000: e3010001 e3020001 e3030003 e3040001  ẉ¢¡¢ẉ£¡¢ẉ¤¡¤ẉ¥¡¢
00000020: 27000001 28ff0302 26ffff01 c1010200  '¡¡¢(”¤£&””¢Ḋ¢£¡
00000030: c1020300 c103ff00 28ff0605 26ffff04  Ḋ£¤¡Ḋ¤”¡(”©¦&””¥
00000050: 22000104 3f000001 f8010000           "¡¢¥?¡¡¢ẏ¢¡¡


Disassembly and explanation:

alkns   SET   $1,1 // a(0) SET$2,1          // a(1)
SET   $3,3 // a(2) SET$4,1          // b(0)/b(1)
SET   $5,3 // b(2) SET$6,6          // b(4)
CSOD  $5,$0,2       // b(3), use if n is odd
CSOD  $6,$0,5       // b(5), use if n is odd
0H      SUBU  $0,$0,1       // loop: n--
2ADDU $255,$3,$2 // a(n+1) = 2a(n) + a(n-1) SUBU$255,$255,$1  // - a(n-2)
SET   $1,$2         // and shift
SET   $2,$3         // values of a
SET   $3,$255       // down
2ADDU $255,$6,$5 // b(n+2) = 2b(n) + b(n-2) SUBU$255,$255,$4  // - b(n-4)
CSOD  $4,$0,$5 // shift values of b down CSOD$5,$0,$6      // if n is odd
CSOD  $6,$0,$255 // (happens once if n started at 2 or 3) PBNZ$0,0B         // if(n) goto loop
ADDU  $0,$1,$4 // r(n) = (a(n) + b(n)) SRU$0,\$0,1       // ÷ 2
POP   1,0           // return r(n)