2
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ Is $[2,5]$ allowed? $[1,2,3,4,5]$? $[\,]$? $\endgroup$
    – Henry
    Commented May 29, 2019 at 20:47
  • $\begingroup$ Thanks for the precision. It is allowed. $\endgroup$ Commented May 29, 2019 at 20:48
  • 3
    $\begingroup$ Then $2^n$ looks sensible. Or $2^n-2$ if you exclude my second and third questions $\endgroup$
    – Henry
    Commented May 29, 2019 at 20:49
  • 3
    $\begingroup$ 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). $\endgroup$ Commented May 29, 2019 at 20:49

1 Answer 1

2
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .