# CombinatorialCase101

Jump to navigationJump to search

This case produces Partitions of the set {⍳M} into at most N parts. Partitioning a set is different from partitioning a number in that the former subdivides the set into non-empty disjoint subsets.

• M labeled balls (1), N unlabeled boxes (0), any # balls per box (1)
• Sensitive to ⎕IO
• Counted result is an integer scalar
• Generated result is a nested vector of nested integer vectors.

The count for this function is +/M SN2¨0..N where M SN2 N returns the Stirling numbers of the 2nd kind.

For example:

If we have 4 labeled balls (❶❷❸❹) and 2 unlabeled boxes with any # of balls per box, there are 8 (↔ +/4 SN2¨0..2 ↔ +/0 1 7) ways to meet these criteria:

 ❶❷❸❹
 ❶❷❸ ❹
 ❶❷❹ ❸
 ❶❷ ❸❹
 ❶❸❹ ❷
 ❶❸ ❷❹
 ❶❹ ❷❸
 ❶ ❷❸❹

The diagram above corresponds to the nested array

```      ⍪101 1‼4 2
1 2 3 4
1 2 3  4
1 2 4  3
1 2  3 4
1 3 4  2
1 3  2 4
1 4  2 3
1  2 3 4
⍝ Partitions of {⍳M} into at most N parts
⍝ Labeled balls, unlabeled boxes, any # Balls per Box
101 0‼4 4
15
101 0‼4 3
14
101 0‼4 2
8
101 0‼4 1
1
101 0‼4 0
0
```

The first column in the following table serves to number the rows and is referenced in 102. The second column illustrates the result of 101 1‼4 4 as a nested array with 15 elements. The third column includes visual separators to make it clearer where one subset stops and another begins:

 1 1 2 3 4 1 2 3 4 2 1 2 3  4 1 2 3|4 3 1 2 4  3 1 2 4|3 4 1 2  3 4 1 2|3 4 5 1 2  3  4 1 2|3|4 6 1 3 4  2 1 3 4|2 7 1 3  2 4 1 3|2 4 8 1 3  2  4 1 3|2|4 9 1 4  2 3 1 4|2 3 10 1  2 3 4 1|2 3 4 11 1  2 3  4 1|2 3|4 12 1 4  2  3 1 4|2|3 13 1  2 4  3 1|2 4|3 14 1  2  3 4 1|2|3 4 15 1  2  3  4 1|2|3|4

See case 102 for identities that relate this case and 102.