CombinatorialCase000/100: Difference between revisions
From NARS2000
Jump to navigationJump to search
No edit summary |
mNo edit summary |
||
| Line 1: | Line 1: | ||
<apll> | <apll>M</apll> Pigeons into <apll>N</apll> holes | ||
Cases '''000''' and '''100''' are both trivial. | Cases '''000''' and '''100''' are both trivial. | ||
* <apll> | * <apll>M</apll> unlabeled (0) or labeled (1) balls into <apll>N</apll> unlabeled boxes (0), at most one per box (0) | ||
* Not <apll>⎕IO</apll>-sensitive | * Not <apll>⎕IO</apll>-sensitive | ||
* Counted result is a Boolean scalar | * Counted result is a Boolean scalar | ||
* Generated result is a Boolean matrix. | * Generated result is a Boolean matrix. | ||
The count for this function is <apll> | The count for this function is <apll>M≤N</apll>. | ||
If <apll> | If <apll>M>N</apll>, then there is no answer, or more accurately, the result is an empty matrix of shape <apll>0 N</apll>. If <apll>M≤N</apll>, then the result is a one-row matrix with <apll>M</apll> leading <apll>1</apll>s and the rest <apll>0</apll>s. Combining these two cases yields a result of <apll>((M≤N) N)⍴N↑M⍴1</apll>. | ||
For example: | For example: | ||
| Line 90: | Line 90: | ||
1 1 1 0 0 | 1 1 1 0 0 | ||
⍝ | ⍝ M pigeons into N holes | ||
⍝ Unlabeled balls & boxes, ≤1 # Balls per Box | ⍝ Unlabeled balls & boxes, ≤1 # Balls per Box | ||
000 1‼4 5 | 000 1‼4 5 | ||
1 1 1 1 0</pre></apll> | 1 1 1 1 0</pre></apll> | ||
Latest revision as of 11:09, 14 May 2017
M Pigeons into N holes
Cases 000 and 100 are both trivial.
- M unlabeled (0) or labeled (1) balls into N unlabeled boxes (0), at most one per box (0)
- Not ⎕IO-sensitive
- Counted result is a Boolean scalar
- Generated result is a Boolean matrix.
The count for this function is M≤N.
If M>N, then there is no answer, or more accurately, the result is an empty matrix of shape 0 N. If M≤N, then the result is a one-row matrix with M leading 1s and the rest 0s. Combining these two cases yields a result of ((M≤N) N)⍴N↑M⍴1.
For example:
If we have 3 unlabeled balls (●●●) and 5 unlabeled boxes with at most one ball per box, there is only 1 (↔ 3≤5) way to meet these criteria:
|
|
|
|
|
as well as
|
|
|
|
|
The diagram above corresponds to
000 1‼3 5
1 1 1 0 0
⍝ M pigeons into N holes
⍝ Unlabeled balls & boxes, ≤1 # Balls per Box
000 1‼4 5
1 1 1 1 0