CombinatorialCase102: Difference between revisions

From NARS2000
Jump to navigationJump to search
No edit summary
mNo edit summary
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
This case produces '''Partitions of the set''' <apll>{⍳L}</apll> into exactly <apll>R</apll> parts.  As such, it produces a subset of [[CombinatorialCase101|<apll>101</apll>]], limiting the result to just those rows with <apll>L</apll> subsets.
This case produces '''Partitions of the set <apll>{⍳M}</apll> into exactly <apll>N</apll> parts'''.  As such, it produces a subset of [[CombinatorialCase101|<apll>101</apll>]], limiting the result to just those rows with <apll>M</apll> subsets.


* <apll>L</apll> labeled balls (1), <apll>R</apll> unlabeled boxes (0), at least one ball per box (2)
* <apll>M</apll> labeled balls (1), <apll>N</apll> unlabeled boxes (0), at least one ball per box (2)
* Sensitive to <apll>⎕IO</apll>
* Sensitive to <apll>⎕IO</apll>
* Counted result is an integer scalar
* Counted result is an integer scalar
* Generated result is a nested vector of nested integer vectors.
* Generated result is a nested vector of nested integer vectors.


The count for this function is <apll>L SN2 R</apll> where <apll>L SN2 R</apll> calculates the [https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling numbers of the 2<sup>nd</sup> kind].
The count for this function is <apll>M SN2 N</apll> where <apll>M SN2 N</apll> calculates the [https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling numbers of the 2<sup>nd</sup> kind].


For example:
For example:
Line 83: Line 83:
   1  2 3 4
   1  2 3 4


       ⍝ Partitions of {⍳L} into R parts
       ⍝ Partitions of {⍳M} into N parts
       ⍝ Labeled balls, unlabeled boxes, ≥1 # Balls per Box
       ⍝ Labeled balls, unlabeled boxes, ≥1 # Balls per Box
       ⍝ The number to the right in parens
       ⍝ The number to the right in parens
Line 114: Line 114:


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


Line 121: Line 121:


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

Latest revision as of 22:17, 14 May 2017

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]