# Probability - number of combinations of an ordered list, elements can be removed

Given the ordered list of elements, e.g. [1,2,3,4,5] I would like to get the number of possible combinations given that elements can be removed from the list, but their order doesn't change.

[1,2,3,4,5] could have at least those combinations [1,2,3,4], [1,2,3], [1,2,4], [2,3,4,5], [4,5], [1], [2] etc.

Ideally I would get the formula allowing me to get the total value for any size list.

Where to start?

• Is $[2,5]$ allowed? $[1,2,3,4,5]$? $[\,]$? Commented May 29, 2019 at 20:47
• Thanks for the precision. It is allowed. Commented May 29, 2019 at 20:48
• Then $2^n$ looks sensible. Or $2^n-2$ if you exclude my second and third questions Commented May 29, 2019 at 20:49
• If @Henry is correct and [2,5] is allowed, then there is a 1-1 bijection between ordered subsets of the ordering [1,2,3,4,5] and subsets of the set $\{1,2,3,4,5\}$. Since there are $2^5$ subsets of a 5-element set, there are $2^5$ of your orderings (or $2^5-2$ proper non-empty subsets). Commented May 29, 2019 at 20:49

If you think about it, either you remove $$1$$ or you don't. Thus there are $$2$$ options here. Similarly, either you remove $$2$$ or you don't, and this is independent of whether we remove $$1$$ or not. Thus there are $$2\times2=4$$ ways to do $$1$$ and $$2$$. Similarly, for $$1,2,3$$ there are $$2^3$$ ways, etc. so for $$1,2,3,4,5$$ there are $$32$$ ways overall.
If you don't allow the empty list, then decrease this value by $$1$$, and if you have to remove at least one element, then decrease by $$1$$ (perhaps again).