CombinatorialCase101: Difference between revisions

From NARS2000
Jump to navigationJump to search
No edit summary
No edit summary
Line 1: Line 1:
This case produces '''Partitions of the set''' <apll>{⍳L}</apll> into at most <apll>R</apll> parts.  Partitioning a set is different from partitioning a number in that the former subdivides the set into non-empty disjoint subsets.
This case produces '''Partitions of the set <apll>{⍳L}</apll> into at most <apll>R</apll> parts'''.  Partitioning a set is different from partitioning a number in that the former subdivides the set into non-empty disjoint subsets.


* <apll>L</apll> labeled balls (1), <apll>R</apll> unlabeled boxes (0), any # balls per box (1)
* <apll>L</apll> labeled balls (1), <apll>R</apll> unlabeled boxes (0), any # balls per box (1)

Revision as of 01:46, 30 April 2017

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

  • L labeled balls (1), R 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 +/L SN2¨0..R where L SN2 R 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 {⍳L} into at most R 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.