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


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?

  • $\begingroup$ 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. $\endgroup$ – Masacroso Oct 14 '14 at 4:18
  • $\begingroup$ 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. $\endgroup$ – Marc van Leeuwen Oct 14 '14 at 6:17

There are two ways of thinking about this (that I can come up with off the top of my head).

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.

  • $\begingroup$ 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$. $\endgroup$ – Marc van Leeuwen Oct 14 '14 at 6:22

You have 8 places for your comma. And think of the comma as being either on or off. so your idea is close...


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.