CombinatorialCase101

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 2^nd 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.