An interesting way of partitioning with inner ordered combinations

38 Views Asked by At

Assume $ K $ labeled blocks $ s_1, s_2, \dots, s_K $ ($ s_1 < s_2 < \dots < s_K $) that arrive sequentially and need to be accomodated as they arrive in $ N $ containers (partitions with empty containers also matter as shown in the picture. The capacity of the containers is unlimited.). I need to find an expression that gives all the possible combinations of partitions where the order of the elements matters.

enter image description here

Some examples:
$$ \begin{align} K = 2, N = 1 \rightarrow & [1 ~ 2] \\ K = 2, N = 2 \rightarrow & [-],[1 ~ 2] \\ & [1 ~ 2],[-] \\ & [1],[2] \\ & [2],[1] \\ K = 2, N = 3 \rightarrow & [-],[-],[1 ~ 2] \\ & [-],[1 ~ 2],[-] \\ & [1 ~ 2],[-],[-] \\ & [-],[2],[1] \\ & [2],[-],[1] \\ & [-],[1],[2] \\ & [2],[1],[-] \\ & [1],[2],[-] \\ & [2],[-],[1] \end{align} $$