0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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) $\endgroup$ – paw88789 Oct 3 '18 at 17:46
  • $\begingroup$ How is the "number of unique ways you can cut the rod" defined? $\endgroup$ – Christian Blatter Oct 3 '18 at 18:21
  • $\begingroup$ @ChristianBlatter I have updated the question. $\endgroup$ – mandark Oct 3 '18 at 18:36
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.