How did I get total number of outcomes as 2^(n-1) if I cut a rod at different lengths ? where n is the lenght of the rod

Question

In Cormen, Under Dynamic programming section, Rod cutting problem is discussed. I am not able to understand how we got 2^(n-1) as the total number of different ways in which we can cut a rod of n length.

Hope someone can throw some light on it.

Answer 1

Consider rod is of 'n' meters. At each meter, you have two possibilities, either you cut it or not. So, multiplying possibilities at each meter you get 2^(n-1) as there are n-1 internal cut points.