CombinatorialCase001: Difference between revisions
From NARS2000
Jump to navigationJump to search
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
This case produces the '''Partitions of the number | This case produces the '''Partitions of the number M into at most N parts'''. | ||
* <apll> | * <apll>M</apll> unlabeled balls (0), <apll>N</apll> unlabeled boxes (0), any # of balls per box (1) | ||
* Not <apll>⎕IO</apll>-sensitive | * Not <apll>⎕IO</apll>-sensitive | ||
* Counted result is an integer scalar | * Counted result is an integer scalar | ||
* Generated result is a nested vector of integer vectors. | * Generated result is a nested vector of integer vectors. | ||
The count for this function is <apll>( | The count for this function is <apll>(M+N)PN N</apll> where <apll>M PN N</apll> calculates the number of [https://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_part_size_or_number_of_parts Partitions] of the number <apll>M</apll> into exactly <apll>N</apll> parts. | ||
For example: | For example: | ||
| Line 96: | Line 96: | ||
3 2 1 | 3 2 1 | ||
2 2 2 | 2 2 2 | ||
⍝ Partitions of | ⍝ Partitions of M into at most N parts | ||
⍝ Unlabeled balls & boxes, any # Balls per Box | ⍝ Unlabeled balls & boxes, any # Balls per Box | ||
⍪001 1‼5 5 | ⍪001 1‼5 5 | ||
| Line 128: | Line 128: | ||
==Identities== | ==Identities== | ||
As shown in [https://en.wikipedia.org/wiki/Twelvefold_way#case_fnx Wikipedia], <apll>( | As shown in [https://en.wikipedia.org/wiki/Twelvefold_way#case_fnx Wikipedia], <apll>(M+N)PN N ↔ +/M PN¨0..N</apll>. | ||
Because partitions of <apll> | Because partitions of <apll>M</apll> into <apll>N</apll> non-negative parts ([[CombinatorialCase001|<apll>001</apll>]]) is the same as partitions of <apll>M+N</apll> into <apll>N</apll> positive parts ([[CombinatorialCase002|<apll>002</apll>]]), these cases are related by the following identity: | ||
<apll>001 | <apll>001 1‼M N ↔ (⊂[⎕IO+1] ¯1+002 1‼(M+N) N)~¨0</apll> | ||
Latest revision as of 18:49, 19 June 2017
This case produces the Partitions of the number M into at most N parts.
- M unlabeled balls (0), N unlabeled boxes (0), any # of balls per box (1)
- Not ⎕IO-sensitive
- Counted result is an integer scalar
- Generated result is a nested vector of integer vectors.
The count for this function is (M+N)PN N where M PN N calculates the number of Partitions of the number M into exactly N parts.
For example:
If we have 6 unlabeled balls (●●●●●●) and 3 unlabeled boxes with any # of balls per box, there are 7 (↔ (6+3)PN 3) ways to meet these criteria:
|
|
|
|
|
|
|
The diagram above corresponds to the nested array
⍪001 1‼6 3
6
5 1
4 2
4 1 1
3 3
3 2 1
2 2 2
⍝ Partitions of M into at most N parts
⍝ Unlabeled balls & boxes, any # Balls per Box
⍪001 1‼5 5
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
⍪001 1‼5 4
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
⍪001 1‼5 3
5
4 1
3 2
3 1 1
2 2 1
⍪001 1‼5 2
5
4 1
3 2
⍪001 1‼5 1
5
Identities
As shown in Wikipedia, (M+N)PN N ↔ +/M PN¨0..N.
Because partitions of M into N non-negative parts (001) is the same as partitions of M+N into N positive parts (002), these cases are related by the following identity:
001 1‼M N ↔ (⊂[⎕IO+1] ¯1+002 1‼(M+N) N)~¨0
