What is the number of ways to choose x groups from y items? (partitions with x cells of a multiset)

445 Views Asked by At

Where a group can consist of 1 or more items, groups don't have to be equally sized and items can be duplicates. Example - Choose 3 groups:

Items: 1 2 2 3

Groups:

(1) (2 2) (3)

(1 2) (2) (3)

(3 1) (2) (2)

(3 2) (2) (1)

Update Following Rasmus' comment, I see that this is more technically described as finding the possible partitions of a multiset where the number of cells is x.

1

There are 1 best solutions below

1
On

Note that this corresponds to the partition of $4$ into $3$ nonzero parts (or $2+1+1 = 4$).