How many partitions to divide a set of n elements into k subsets, mantaining order of the set?

Question

For example I have a string 'bbbbb' (n = 5) and want to divide it in 3 (k = 3) groups. The possibilities are 6:

• b|b|bbb
• b|bb|bb
• b|bbb|b
• bb|b|bb
• bb|bb|b
• bbb|b|b

How can I find the number in advance?

Answer 1

Here we are placing 2 partitions into 2 of 4 places. So it is $ 4 \choose 2 $$= 6 $ ways.

In general for string of length $n$, we have $k-1$ partitions into $n-1$ places. Then we will have $ {n-1} \choose {k-1} $ ways.