Combinatorial

Z←a‼V returns an array whose values depend upon which Combinatorial function is chosen by the left operand a.

V is a two-element numeric vector. For convenience, the two elements are referred to as L and R as in (L R)←V

a is a scalar one- or two- element vector number which serves as the Selector for the Twelve Combinatorial Functions. The first element (Function Selector) in a is a non-negative integer for each of the Twelve functions (where the number is written as a three-digit number with leading zeros to emphasize that each digit has a separate meaning): 000   L Pigeons in R holes 001   Partitions of the number L into no more than R parts 002   Partitions of the number L into R parts 010   L Combinations of R items 011   L Multisets of R items 012   Compositions of the number L into R parts   a.k.a. Partitions of the number L into R ordered parts 100   L Pigeons in R holes 101   Partitions of the set {⍳L} into no more than R parts 101   Partitions of the set {⍳L} into R parts 101   L Permutations of R items 101   L Tuples of R items 101   Partitions of the set {⍳L} into R ordered parts

The second element (Count/Generate Flag) in a is an optional Boolean value where 0 (the default) means count the number of elements in the Combinatorial function as applied to R, and 1 means generate the array of elements.

Examples

The expression 110‼L R produces L Permutations of R items. When the two elements of the right argument are equal, it represents the usual Permutation function.

      110‼3 3   ⍝ Count the !3 Permutations
6
      110 1‼3 3 ⍝ Generate the !3 Permutations
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3
      110 1‼2 3 ⍝ Generate the 2 Permutations of 3 items
1 2
2 1
1 3
3 1
2 3
3 2
      perm←{110 1‼⍵ ⍵} ⍝ Permutation function
      perm 3
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3

The expression 10‼L R produces L Combinations of R items.

      comb←{10 1‼⍺ ⍵} ⍝ Combinations function
      3 comb 5
1 2 3
1 2 4
1 3 4
2 3 4
1 2 5
1 3 5
2 3 5
1 4 5
2 4 5
3 4 5

The expression 1‼L R produces Partitions of L into at most R parts.

      1‼7 3
8
      ⍪1 1‼7 3
 7     
 6 1   
 5 2   
 5 1 1 
 4 3   
 4 2 1 
 3 3 1 
 3 2 2

If you have seen the movie “The Man Who Knew Infinity” (2015) (about the life and academic career of the brilliant Indian mathematician Srinivasa Ramanujan), you may recall that at one point it focuses on the problem of calculating p(200) — the number of Partitions of the number 200 into at most 200 parts. This number can be calculated by

      1‼200 200
3972999029388

in a few thousands of a second.

The Twelvefold Way

The Twelvefold Way consolidates twelve Combinatorial algorithms into a single 2×2×3 array based on the simple concept of placing balls into boxes (urns, to you old-timers). The three dimensions of the array can be described as follows:

• The balls may be labeled (or not) {2 ways},
• The boxes may be labeled (or not) {2 ways}, and
• The # balls allowed in a box may be one of (at most one | unrestricted | at least one) {3 ways}.

Amazingly, these twelve choices spanning three dimensions knit together within a single concept (balls in boxes) all of the following interesting, fundamental, and previously disparate and disorganized Combinatorial algorithms:

• Permutations
• Combinations
• Compositions
• Multisets
• Partitions of a set
• Partitions of a number
• Tuples
• Pigeon Holes

As mentioned above, although the first element of the Function Selector is an integer, it is written as a three-digit number with leading zeros to emphasize that each digit has a separate meaning. Those meanings are exactly related to the 2×2×3 array mentioned above.

• The first digit represents the Balls as Unlabeled (0) or Labeled (1)
• The second digit represents the Boxes as Unlabeled (0) or Labeled (1)
• The third digit represents the capacity of the Balls in the Boxes of At most One (0), Unrestricted (1), or At Least One (2).

For example:

• A function selector of 010 means unlabeled balls (0), labeled boxes (1), and at most one ball in each box (0). If we have 2 unlabeled balls (●●) and 4 labeled boxes (1234) with at most one ball per box, there are 6 (↔ 2!4) ways to meet these criteria:

  ● ● 1 2 3 4

  ● ● 1 2 3 4

  ● ● 1 2 3 4

  ● ● 1 2 3 4

  ● ● 1 2 3 4

  ● ● 1 2 3 4

  from which it is easy to see that these criteria correspond to L combinations of R items (↔ L!R).
• A function selector of 110 means labeled balls (1), labeled boxes (1), and at most one ball in each box (0). If we have 3 labeled balls (❶❷❸) and 3 labeled boxes (123) with at most one ball per box, there are 6 (↔ (!⍠¯3)3 ↔ 3×2×1) ways to meet these criteria:

  ❶ ❷ ❸ 1 2 3

  ❷ ❶ ❸ 1 2 3

  ❷ ❸ ❶ 1 2 3

  ❶ ❸ ❷ 1 2 3

  ❸ ❶ ❷ 1 2 3

  ❸ ❷ ❶ 1 2 3

  If we have 2 labeled balls (❶❷) and 3 labeled boxes (123) with at most one ball per box, there are 6 (↔ (!⍠¯2)3 ↔ 3×2) ways to meet these criteria:

  ❶ ❷     1 2 3

  ❷ ❶     1 2 3

  ❷     ❶ 1 2 3

  ❶     ❷ 1 2 3

  ❶ ❷ 1 2 3

  ❷ ❶ 1 2 3

from which it is easy to see that these criteria correspond to L permutations of R items. When L=R, this is the # permutations of ⍳R, (↔ !R), and when L<R, this is the # L-permutations, also called the falling factorial (!⍠(-L))R.

As a side note, the above examples reveal one of the many insights the Twelvefold Way provides into Combinatorial algorithms. Previously, you might not have seen any connection between the algorithms for Combinations and Permutations, but, as the above examples show, they are closely related in that they differ only in the use of labeled vs. unlabeled balls, both in labeled boxes with at most one ball per box.

Labeled vs. Unlabeled

Boxes

For most cases, the boxes are the columns of the result. Two or more labeled boxes may hold identical content, but because the boxes are labeled, they are considered distinct. On the other hand, unlabeled boxes with identical content are indistinguishable. For example, the following (partial) configurations of 3 unlabeled balls (●●●) in 3 unlabeled boxes

● ● ●

● ● ●

● ● ●

are all considered equivalent and are counted only once because the boxes are unlabeled.

Similarly, the following (partial) configurations of 3 labeled balls (❶❷❸) in 2 unlabeled boxes

❶ ❷ ❸

❸ ❶ ❷

❷ ❶ ❸

❸ ❷ ❶

are also all considered equivalent and are counted only once, again because the boxes are unlabeled.

Note that the order of the (labeled) balls within a box is ignored which means that even if the boxes were labeled, the first and third configurations above are equivalent, as are the second and fourth.

Balls

In a similar manner, the counts and generations for combinations (010) and permutations (110) differ by a factor of !L, this time because of the balls: one is unlabeled and the other labeled. That is, the count for L combinations of R items is

L!R ↔ (!R)÷(!R-L)×!L

and the count for L permutations of R items is

(!⍠(-L)) R ↔ (!R)÷!R-L

Of course, when L=R, the permutation count is the familiar !R.

The Functions

The array of functions can be displayed as follows in a table organized by the Function Selector:

FS Table	Balls Per Box At Most One   xx0 Unrestricted xx1 At least one     xx2
L unlabeled balls 00x R unlabeled boxes	L pigeons            000 into R holes	partitions of L    001 into ≤R parts	partitions of L          002 into R parts
L unlabeled balls 01x R labeled boxes	L-combinations    010 of R items	L-multisets        011 of R items	compositions of L     012 into R parts
L labeled balls    10x R unlabeled boxes	L pigeons            100 into R holes	partitions of N   101 into ≤R parts	partitions of N         102 into R parts
L labeled balls    11x R labeled boxes	L-permutations    110 of R items	L-tuples            111 of R items	partitions of N         112 into R ordered parts

Click on one of the above colored cells to see more detail on that function.

Memoization

This technique is a form of caching used to speed up certain algorithms, particularly recursive ones.

Two of the Combinatorial functions (001 and 002) are dependent on the following recurrence relation for Partition Numbers defined on n≥0 and k≥0:

P(0,0) = 1
P(n,k) = P(n-k,k) + P(n-1,k-1)

Within a session of the interpreter, these values are cached internally so that subsequent requests for already calculated Partition Numbers are sped up significantly.

Three other Combinatorial functions (101, 102, and 112) are dependent on the Stirling numbers of the 2nd kind. They satisfy the following recurrence relation defined on n≥0 and k≥0:

S(0,0) = 1
S(n,k) = k × S(n-1,k) + S(n-1,k-1)

These numbers are also cached internally by the interpreter so as to speed up subsequent access.

In case you need to clear the cache so as to time the internal algorithms without the benefit of the cache, the expression

      ∘‼1
Cache cleared

clears the cache.

History

The idea of consolidating these twelve algorithms into a single primitive is credited to Gian-Carlo Rota through a series of lectures given at the Massachusetts Institute of Technology (MIT). The mathematics behind the Twelvefold Way is described in several places, most notably in Richard Stanley's Enumerative Combinatorics, and Wikipedia. The name was suggested by Joel Spencer.

Implementation

This monadic operator is implemented in the Alpha version of NARS2000 and may be downloaded from here. For an in-depth look at the Twelvefold Way and its implementation in APL, see Smith's paper.