3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Try for $[1],\, [1,\, 2]$ and $[1,\, 2,\, 3,\, 4]$ and see if you notice a pattern. $\endgroup$ – pjs36 Dec 14 '16 at 3:38
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe I'm missing something, but this doesn't seem to answer the question since it was asking for the number of $k$-partitions as opposed to the total. $\endgroup$ – Michael Mior Jan 30 '17 at 20:12
1
$\begingroup$

Looks like you want to count compositions.

$\endgroup$

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.