# Number of ways to group digits in {1,2,3,4,5,6,7,8,9} into numbers, while maintaining order

I have a set of integers from 1 to 9, call it A:

$$A=[1,2,3,4,5,6,7,8,9]$$

How could I find the total number of possible combination of numbers within that set, while maintaining order? For example, a few possibilities would be:

$$[12,34,56,78,9]$$ $$[1,23,45,67,89]$$ $$[123,456,789]$$ $$[12,3456,78,9]$$

I was thinking that each comma (,) could be thought of as either being TRUE or FALSE, and would be $\require{cancel} \cancel{2^9} 2^8$ total possibilities?

• Order, in the sense of sets, can be anything that is less than (or just something that is less or equal than for partial order) not just the contiguous, so you can have sequences as $1356$ or $256$ by example. – Masacroso Oct 14 '14 at 4:18
• I've edited the title, since these things are not permutations in any plausible interpretation of that term. In fact "permuting while preserving the order" is more or less a contradiction in terms. – Marc van Leeuwen Oct 14 '14 at 6:17

First is what you suggested, except there are $8$ commas to choose from, so you have $2^8$ total possibilities.
Second, the more brute force, way is to sum over the number of commas you use. Once you decide on $i$ commas, you can choose $i$ spots out of $8$ for your commas. So you have $$\sum_{i=0}^8 \binom{8}{i} = 2^8$$ total possibilities.
• The second way is just a rather roundabout way to do the first, i.e., you distinguish first on the number of commas, which is irrelevant to the question. One could complicate matters even more by also distinguishing on say the position of the first comma (if there is one); that would give $1+\sum_{p=1}^8\sum_{i=0}^{8-p}\binom{8-p}i=1+\sum_{p=1}^82^{8-p}=2^8$. – Marc van Leeuwen Oct 14 '14 at 6:22