CombinatorialCase112

From NARS2000
Revision as of 01:42, 30 April 2017 by WikiSysop (talk | contribs) (Created page with "This case produces '''Partitions of the set <apll>{⍳L}</apll> into <apll>R</apll> ordered parts'''. Essentially, this case is the same as CombinatorialCase102|<apll>102</...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

This case produces Partitions of the set {⍳L} into R ordered parts. Essentially, this case is the same as 102, except that the order of the elements is important so that there are more results by a factor of !R. For example, the 3-subset result of 1 2|3|4 for 102 is expanded to !4 (↔ 24) 3-subsets by permuting the values 1 2 3 4 in 24 ways.

  • L labeled balls (1), R labeled boxes (1), 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 (!R)×L SN2 R where L SN2 R calculates the Stirling numbers of the 2nd kind..

For example:

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



       


       


       


       



       



       


       


       



       



       



       



       


       


       

The diagram above corresponds to the nested array

      ⍪112 1‼4 2
  1 2 3  4
  4  1 2 3
  1 2 4  3
  3  1 2 4
  1 2  3 4
  3 4  1 2
  1 3 4  2
  2  1 3 4
  1 3  2 4
  2 4  1 3
  1 4  2 3
  2 3  1 4
  1  2 3 4
  2 3 4  1
      ⍝ Partitions of the set {⍳L} into
      ⍝   R ordered parts
      ⍝ Labeled balls & boxes, any # Balls per Box
      ⍪112 1‼3 3
  1  2  3
  2  1  3
  2  3  1
  1  3  2
  3  1  2
  3  2  1
      ⍪112 1‼3 2
  1 2  3
  3  1 2
  1 3  2
  2  1 3
  1  2 3
  2 3  1
      ⍪112 1‼3 1
  1 2 3

In general, this case is equivalent to calculating the unlabeled boxes (102) and then permuting the items from that result as in

a←⊃102 1‼L R
b← 110 1‼R R
112 1‼L R ↔ ,⊂[⎕IO+2] a[;b]

or vice-versa

102 1‼L R ↔ {(2≢/¯1,(⊂¨⍋¨⍵)⌷¨⍵)/⍵} 112 1‼R R