I am trying to find a way to find (if it is possible) how many ways there are to split a number of n digits considering that the "splits" can occur everywhere and the subsets don't have to be the same length. So for example, if I have a 5 digits number "12345" I can split it into 16(?) ways:
1)12345
2)1-2-3-4-5
3)1-2345
4)12-345
5)123-45
6)1-23-45 etc.
So I am looking for all possible strategies to split the number. I am looking for both a formula and an algorithm. I am guessing that it is 2^(n-1) but I am not sure and I'd like to know why, if this is the case
Best Answer
When you have a sequence of $n$ numbers, you can $n-1$ slots to make cuts. So we need to know all the ways we can choose $0$ cuts out if it, then $1$ cut, $2$ cuts, etc
The total number of ways to choose the cuts is $$\sum_{k=0}^{n-1} { {n-1}\choose{k}} =2^{n-1} $$
To prove this equality, use a subtle trick: Set $2^{n-1} = (1+1)^{n-1}$ and use the Binomial Theorem.