CombinatorialCase102

From NARS2000
Jump to navigationJump to search

This case produces Partitions of the set {⍳M} into exactly N parts. As such, it produces a subset of 101, limiting the result to just those rows with M subsets.

  • M labeled balls (1), N unlabeled boxes (0), at least one ball per box (2)
  • 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 N where M SN2 N calculates the Stirling numbers of the 2nd kind.

For example:

If we have 4 labeled balls (❶❷❸❹) and 2 unlabeled boxes with at least one ball per box, there are 7 (↔ 4 SN2 2) ways to meet these criteria:



       


       



       


       



       



       



       

The diagram above corresponds to the nested array

      ⍪102 1‼4 2
  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 N parts
      ⍝ Labeled balls, unlabeled boxes, ≥1 # Balls per Box
      ⍝ The number to the right in parens
      ⍝    represent the corresponding row from
      ⍝    the table in case 101.

      ⍪102 1‼4 4
  1  2  3  4		        (15)
      ⍪102 1‼4 3
  1 2  3  4			(5)
  1 3  2  4			(8)
  1  2 3  4			(11)
  1 4  2  3			(12)
  1  2 4  3			(13)
  1  2  3 4			(14)
      ⍪102 1‼4 2
  1 2 3  4			(2)
  1 2 4  3			(3)
  1 2  3 4			(4)
  1 3 4  2			(6)
  1 3  2 4			(7)
  1 4  2 3			(9)
  1  2 3 4			(10)
      ⍪102 1‼4 1
  1 2 3 4			(1)
      ⍪102 1‼4 0

In general, this case is related to 101 through the following identities (after sorting the items):

101 1‼M N ↔ ⊃,/102 1‼¨M,¨0..N
102 1‼M N ↔ R {(⍺=≢¨⍵)/⍵} 101 1‼M N

and is related to 112 through the following identities:

102 1‼M N ↔ {(2≢/¯1,(⊂¨⍋¨⍵)⌷¨⍵)/⍵} 112 1‼M N
a←⊃102 1‼M N
b← 110 1‼M N
112 1‼M N ↔ ,⊂[⎕IO+2] a[;b]