Combinatorics

Combinatorics functions in the Compute Engine provide essential tools for counting and enumerating discrete structures. These functions enable computation of binomial and multinomial coefficients, generation of permutations and combinations, construction of Cartesian products and power sets, and calculation of special combinatorial numbers such as derangements and Bell numbers. These utilities are fundamental for combinatorial analysis and discrete mathematics.

---

Functions

Choose: (n: number, m: number) -> number

Computes the binomial coefficient, often read as “n choose m,” representing the number of ways to select m elements from a set of n elements without regard to order.

This function answers the question: "How many different groups of size m can be formed from n distinct items?" It is a fundamental concept in combinatorics used in probability and statistics.

For example, to compute the number of ways to choose 2 items from 5:
Step 1: Calculate factorials: 5! = 120, 2! = 2, (5-2)! = 3! = 6
Step 2: Apply formula: 5! / (2! \times 3!) = 120 / (2 \times 6) = 10
So, there are 10 different ways to choose 2 items from 5.

The function returns NaN if n < 0, m < 0, or m > n.

["Choose", 5, 2]

See also: Binomial coefficient - Wikipedia

\mathrm{Choose}(n, m) = \binom{n}{m} = \frac{n!}{m!(n-m)!}

$$$\mathrm{Choose}(n, m) = \binom{n}{m} = \frac{n!}{m!(n-m)!}$$

Fibonacci: (n: integer) -> integer

Returns the n^th Fibonacci number, a sequence defined by the sum of the two preceding numbers starting with 0 and 1.

For negative indices, the function returns -Fibonacci(-n), following the standard extension of Fibonacci numbers to negative integers.

The Fibonacci sequence models many natural phenomena and appears in computer algorithms and mathematics. It starts as 0, 1, 1, 2, 3, 5, 8, ...

For example, to find the 7th Fibonacci number:
Step 1: Start with F(0) = 0, F(1) = 1
Step 2: Compute subsequent terms: F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8, F(7) = 13
Hence, the 7th Fibonacci number is 13.

["Fibonacci", 7]
// -> 13

See also: Fibonacci number - Wikipedia

\mathrm{Fibonacci}(n) = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ \mathrm{Fibonacci}(n-1) + \mathrm{Fibonacci}(n-2), & n > 1 \\ -\mathrm{Fibonacci}(-n), & n < 0\end{cases}

$$$\mathrm{Fibonacci}(n) = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ \mathrm{Fibonacci}(n-1) + \mathrm{Fibonacci}(n-2), & n > 1 \\ -\mathrm{Fibonacci}(-n), & n < 0\end{cases}$$

Binomial: (n: integer, k: integer) -> integer

Calculates the binomial coefficient C(n, k), the number of ways to choose k elements from a set of n elements. Returns 0 if k < 0 or k > n, and 1 if k = 0 or k = n.

This function is similar to Choose but specialized for integer inputs and returns integer results. It is widely used in combinatorics, probability, and algebra.

Example: To find the number of ways to choose 2 elements from 6:
Calculate \binom{6}{2} = \frac{6!}{2!4!} = \frac{720}{2 \times 24} = 15.

["Binomial", 6, 2]

See also: Binomial coefficient - Wikipedia

\mathrm{Binomial}(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}

$$$\mathrm{Binomial}(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$$

CartesianProduct: (set₁: set, set₂: set, ...) -> set

Returns the Cartesian product of one or more input sets, producing all ordered tuples where each element is drawn from the corresponding input set.

This function answers: "What are all possible combinations of elements where you pick one from each set?"

Example: Given sets A = \{1, 2\} and B = \{a, b\}, the Cartesian product A \times B is:
\{ (1, a), (1, b), (2, a), (2, b) \}

["CartesianProduct", {"set": [1, 2]}, {"set": ["a", "b"]}]

See also: Cartesian product - Wikipedia

A \times B = \{ (a, b) \mid a \in A, b \in B \}

$$$A \times B = \{ (a, b) \mid a \in A, b \in B \}$$

PowerSet: (set: set) -> set

Computes the power set of the given set, which is the set of all subsets including the empty set and the set itself.

This function helps enumerate every possible subset, useful in combinatorics, logic, and computer science.

Example: For the set \{ a, b \}, the power set is: \{ \{\}, \{a\}, \{b\}, \{a, b\} \}

["PowerSet", ["Set", a, b]]
// -> ["Set", ["EmptySet"], ["Set", a], ["Set", b], ["Set", a, b]]

See also: Power set - Wikipedia

\mathcal{P}(A) = \{ S \mid S \subseteq A \}

$$$\mathcal{P}(A) = \{ S \mid S \subseteq A \}$$

Permutations: (collection: list, k?: integer) -> list<list>

Generates all permutations of the input collection of length k. If k is omitted, permutations of the full length of the collection are returned.

Permutations represent all possible ordered arrangements of elements.

Example: For collection [1, 2, 3] and k=2, permutations include: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2].

["Permutations", ["List", 1, 2, 3], 2]
// -> ["List", 
//      ["List", 1, 2], 
//      ["List", 1, 3], 
//      ["List", 2, 1], 
//      ["List", 2, 3], 
//      ["List", 3, 1], 
//      ["List", 3, 2]
// ]

See also: Permutation - Wikipedia

Combinations: (collection: list, k: integer) -> list<list>

Returns all k-element combinations (unordered subsets) of the input collection.

Combinations represent subsets where order does not matter.

Example: For collection [1, 2, 3] and k=2, combinations are: [1,2], [1,3], [2,3].

["Combinations", ["List", 1, 2, 3], 2]
// -> [["List", 1, 2], ["List", 1, 3], ["List", 2, 3]]

See also: Combination - Wikipedia

Multinomial: (k₁: integer, k₂: integer, ...) -> integer

Calculates the multinomial coefficient for the given group sizes, representing the number of ways to partition a set of n = k_1 + k_2 + \cdots elements into groups of sizes k_1, k_2, \ldots.

This extends the binomial coefficient to multiple groups and is useful in probability and combinatorics.

Example: For groups of sizes 2 and 1 (total 3 elements), the multinomial coefficient is:
\frac{3!}{2!1!} = \frac{6}{2} = 3.

["Multinomial", 2, 1]

See also: Multinomial theorem - Wikipedia

\mathrm{Multinomial}(k_1, \ldots, k_m) = \frac{(k_1 + \cdots + k_m)!}{k_1! \cdots k_m!}

$$$\mathrm{Multinomial}(k_1, \ldots, k_m) = \frac{(k_1 + \cdots + k_m)!}{k_1! \cdots k_m!}$$

Subfactorial: (n: integer) -> integer

Returns the number of derangements of n elements, i.e., permutations with no fixed points where no element appears in its original position.

Derangements are important in problems like the "hat-check problem" in probability.

Example: For n=4, the number of derangements is:
!4 = 4! \times \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right) = 9.

["Subfactorial", 4]

See also: Derangement - Wikipedia

!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}

$$$!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$$

BellNumber: (n: integer) -> integer

Computes the Bell number B(n), which counts the number of ways to partition a set of n elements into any number of non-empty, disjoint subsets.

Bell numbers appear in combinatorics and partition theory.

Example: For n=3, the Bell number is 5, representing the partitions:
\{ \{1,2,3\}, \{1,2\},\{3\}, \{1,3\},\{2\}, \{2,3\},\{1\}, \{1\},\{2\},\{3\} }.

["BellNumber", 3]
// -> 5

See also: Bell number - Wikipedia

B(n) = \sum_{k=0}^{n-1} \binom{n-1}{k} B(k), \quad B(0) = 1

$$$B(n) = \sum_{k=0}^{n-1} \binom{n-1}{k} B(k), \quad B(0) = 1$$