Number of \$n\$-carbon alkanes Given a positive number \$n\$, find the number of alkanes with \$n\$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with \$n\$ nodes, such that every node has degree \$\le 4\$.

This is OEIS sequence A000602. 

See also: Paraffins - Rosetta Code

Example

For \$n = 7\$, the answer is \$9\$, because heptane has nine isomers:


Heptane: \$\mathrm{H_3C-CH_2-CH_2-CH_2-CH_2-CH_2-CH_3}\$





2-Methylhexane: \$\mathrm{H_3C-CH(CH_3)-CH_2-CH_2-CH_2-CH_3}\$





3-Methylhexane: \$\mathrm{H_3C-CH_2-CH(CH_3)-CH_2-CH_2-CH_3}\$





2,2-Dimethylpentane: \$\mathrm{H_3C-C(CH_3)_2-CH_2-CH_2-CH_3}\$





2,3-Dimethylpentane: \$\mathrm{H_3C-CH(CH_3)-CH(CH_3)-CH_2-CH_3}\$





2,4-Dimethylpentane: \$\mathrm{H_3C-CH(CH_3)-CH_2-CH(CH_3)-CH_3}\$





3,3-Dimethylpentane: \$\mathrm{H_3C-CH_2-C(CH_3)_2-CH_2-CH_3}\$





3-Ethylpentane: \$\mathrm{H_3C-CH_2-C(CH_2CH_3)-CH_2-CH_3}\$





2,2,3-Trimethylbutane: \$\mathrm{H_3C-C(CH_3)_2-CH(CH_3)-CH_3}\$




Note that 3-methylhexane and 2,3-dimethylpentane are chiral, but we ignore stereoisomers here.

Test cases

You don't need to handle the case \$n = 0\$.

intput&#9;output
=============
0&#9;1
1&#9;1
2&#9;1
3&#9;1
4&#9;2
5&#9;3
6&#9;5
7&#9;9
8&#9;18
9&#9;35
10&#9;75
11&#9;159
12&#9;355
13&#9;802
14&#9;1858
15&#9;4347
16&#9;10359
17&#9;24894
18&#9;60523
19&#9;148284
20&#9;366319
CJam (100 98 91 89 83 bytes)

1a{_[XX]*\_{_0a*}:E~\{E\_{ff*W%{0@+.+}*}:C~.+2f/}:D~.+C.+3f/1\+}q~:I*DE1$D.-X\+.+I=


Takes input from stdin, outputs to stdout. Note that this exploits the licence to not handle input 0 to save two bytes by inlining the definitions of C and D. Online demo

NB this is very slow and memory-inefficient. By trimming arrays a much faster version is obtained (3 bytes more). Online demo.

Dissection

OEIS gives (modulo an indexing error) the generating function decomposition $$\begin{eqnarray}
A000598(x) &amp;=&amp; 1 + x Z(S_3; A000598(x)) \\
A000678(x) &amp;=&amp; x Z(S_4; A000598(x)) \\
A000599(x) &amp;=&amp; Z(S_2; A000598(x) - 1) \\
A000602(x) &amp;=&amp; A000678(x) - A000599(x) + A000598(x^2) \\
\end{eqnarray}$$ where \$Z(S_n; f(x))\$ denotes the cycle index of the symmetric group \$S_n\$ applied to the function \$f(x)\$.

I manipulated this into a slightly golfier decomposition, and then looked up the intermediate sequences and discovered that they're also in OEIS:

$$\begin{eqnarray}
A000642(x) &amp;=&amp; Z(S_2, A000598(x)) \\
A000631(x) &amp;=&amp; Z(S_2, A000642(x)) \\
A000602(x) &amp;=&amp; A000642(x) + x A000642(x^2) - x A000631(x)
\end{eqnarray}$$

Earlier versions reused block C (convolve two polynomials) from this answer. I've found a much shorter one, but I can't update that answer because it's from a chaining question.

1a            e# Starting from [1]...
{             e# Loop I times (see below) to build A000598 by f -&gt; 1 + Z(S_3; f)
  _[XX]*      e#   Copy and double-inflate to f(x^3)
  \_          e#   Flip and copy: stack is f(x^3) f(x) f(x)
  {_0a*}:E~   e#   Assign copy-and-inflate to E and execute
              e#   Stack: f(x^3) f(x) f(x) f(x^2)
  \           e#   Flip
  {           e#   Define and execute block D, which applies f -&gt; Z(S_2;f)
              e#     Stack: ... f
    E\_       e#     Stack: ... f(x^2) f(x) f(x)
    {         e#     Define and execute block C, which convolves two sequences
      ff*     e#       Multiply copies of the second sequence by each term of the first
      W%      e#       Reverse
      {       e#       Fold
        0@+.+ e#         Prepend a 0 to the first and pointwise sum
      }*
    }:C~      e#     Stack: ... f(x^2) f(x)^2
    .+2f/     e#     Pointwise average
  }:D~        e#   Stack: f(x^3) f(x) f(x^2) Z(S_2;f(x))
  .+C         e#   Stack: f(x^3) f(x)*(f(x^2) + Z(S_2;f(x)))
  .+3f/       e#   Add and divide by 3 to finish computing Z(S_3; f)
  1\+         e#   Prepend a 1
}
q~:I          e# Read input to I
*             e# Loop that many times
              e# Stack: I+1 terms of A000598 followed by junk
D             e# Stack: I+1 terms of A000642 followed by junk
E1$D          e# Stack: A000642 A000642(x^2) A000631
.-X\+.+       e# Stack: A000602
I=            e# Extract term I