# How many unique ways are there to cut a rod?

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 that actual number of ways to cut a rod are less than $$2^{n-1}$$. What is the actual number and how would you go about calculating it?

• If I understand correctly, you are asking how many partitions are there of an integer. You might want to start with something like en.wikipedia.org/wiki/Partition_(number_theory) – paw88789 Oct 3 '18 at 17:46
• How is the "number of unique ways you can cut the rod" defined? – Christian Blatter Oct 3 '18 at 18:21
• @ChristianBlatter I have updated the question. – mandark Oct 3 '18 at 18:36

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.