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!

Zacharý

Posted 2016-12-18T21:26:08.563

Reputation: 5 710

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 – 2016-12-18T21:32:18.690

– JungHwan Min – 2016-12-18T21:32:27.467

That help at all? – Zacharý – 2016-12-18T21:40:26.290

5@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 – 2016-12-18T22:19:54.907

@MartinEnder The answer is simply (# of straight-chain alk*nes)/2 + (# of symmetrical straight-chain alk*nes)/2 – JungHwan Min – 2016-12-18T23:30:38.007

Oh, and # of symmetrical straight-chain alk*nes is 3^floor(n/2), right (where n is the length)? – Zacharý – 2016-12-18T23:45:45.497

@MartinEnder (# of symmetrical straight-chain alk*nes) has the recurrence relation a(n) = 2*a(n-2) + a(n-4) - a(n-6) with initial conditions a(0) = 1, a(1) = 3, a(2) = 2, a(3) = 6, a(4) = 5, and a(5) = 14. That's really similar to a(n) = 2*a(n-1) + a(n-2) - a(n-3) from the other question. – JungHwan Min – 2016-12-19T00:00:30.720

The recurrence equation for this problem is a(n) = 2*a(n-1) + 3*a(n-2) - 5*a(n-3) - a(n-4) - 2a(n-6) + 3*a(n-7) + a(n-8) - a(n-9) with a(0) = 1, a(1) = 3, a(2) = 4, a(3) = 10, a(4) = 18, a(5) = 42, a(6) = 84, a(7) = 192, a(8) = 409 – JungHwan Min – 2016-12-19T00:11:58.530

The only problem with that is a(1) should be 1, a(2) should be 3, etc. as noted in the test cases. – Zacharý – 2016-12-19T00:15:46.673

@ZacharyT My bad... but still, my point is that this challenge is too similar to the other one. – JungHwan Min – 2016-12-19T00:19:25.217

@JungHwanMin I think that's sufficiently different for it not to be a duplicate (otherwise the original would have been a duplicate of Fibonacci). Whether it adds something interesting over the previous challenge I don't know, but I wouldn't close it. – Martin Ender – 2016-12-19T08:17:09.970

Deriving an answer to this question from an answer to the previous one without exploiting any structure to the answer (e.g. filtering a list of constructed chains) requires case splitting: if the previous answer's sequence is a(n) and this one is b(n) then a bit of work with @JungHwanMin's recurrences shows that 2 b(2n) = a(2n) + a(n+1) - a(n-1) and 2 b(2n+1) = a(2n+1) + a(n+2). – Peter Taylor – 2016-12-19T09:27:06.353

Straight Chain Alk*nes without Order

Specifications/Clarifications

Test Cases:

Answers

JavaScript (ES6), 107 bytes