Ordered partitions of an ordered list

268 Views Asked by At

In how many ways we can make an ordered partition of an ordered list?

For example, if list is: $[1,2,3]$

Its partitions are:

$[1][2][3]$

$[1][2,3]$

$[1,2][3]$

$[1,2,3]$

Asking for another related information:

Say list size is $n$ and we are interested in only $k-$partition (where $n>k$)

How many $k-$partitions will be there for the list?

2

There are 2 best solutions below

1
On BEST ANSWER

If you have $n$ items in the list, you have $n-1$ places you can put a break or not, so $2^{n-1}$ ways to break it up. Your example has $n=3$ and there are $2^{3-1}=4$ ways.

0
On

Looks like you want to count compositions.