How many unique ways are there to cut a rod?

Question

This is related to the rod-cutting problem and counting the number of ways that you can cut it. I am interested in counting the total number of unique ways that you can cut the rod.

By unique or distinct, I mean that when you cut a rod, the order of the partitions shouldn't matter e.g. cutting a rod of length 4 and be cut as $1+3$ or $3+1$. These should be considered the same.

I know that the brute force solution is $$2^{n-1}$$ but that has a lot of redundant states. Consider the rod of length 3, $2^{n-1}$ configurations are:

1 + 1 + 1
1 + 2
2 + 1          <- redundant
3

So it seems like the actual number of ways to cut a rod is less than $2^{n-1}$. What is the actual number and how would you go about calculating it?

Answer 1

This is the sequence A00041 in OEIS: the number of partitions of integers. If you don't like wiki, try Wolfram MathWorld.

There's no general formula available (as things often don't), but we have the recurrence relation and the generating function (see e.g. the wiki entry).

Just FYI, the ordered situation is the composition of integers.

Answer 2

A rod of length $n$ can be cut at any of the positions $1$ inch, $2$ inches, up to $n-1$ inches. Therefore for each way of cutting the rod, there is a corresponding sequence of $0$s and $1$s of length $n-1$, with a $1$ in the $i$th place meaning that the rod is cut at this position and a $0$ meaning that it is not cut.

Since there are $2^{n-1}$ such sequences, there must be $2^{n-1}$ ways of cutting the rod.