Number of ways to split binary string?

Question

Not answered, see my comments.

Given a binary string like this: 1101 What's the number of possible ways to split it (where splitting the string doesn't necessary means having only 2 parts)

For example:

1,101
11,01
1,1,0,1
1,1,01
1,10,1
110,1
1,101
1101

are all valid splits.

Instead of exact number for string of length n I'm interested in knowing whether the result if some polynomial function of n or not.

Answer 1

Hint. Every subset of the set of spaces between digits corresponds to a splitting. How may subsets does an $n-1$ element set have?

If necessary, work out the answer for $n = 1,2,2,3,5$ to see the pattern.

Answer 2

As the other poster has noted, this is equivalent to asking how many subsets of $\{1, \ldots, n-1\}$ there are, and the answer is (exactly) $2^{n-1}$. So, not polynomial, but exponential.

Here is a way to see this result directly. For each digit of the string except the last, you can either put a split after this digit, or not. That is, between any 2 digits, either you split or you don't. There are $n-1$ places where you need to choose whether to split or not split, and since each choice doubles the number of possible ways to split the string, there are $2^{n-1}$ in total.