Combinatorics Utilities

stirling2( n :: Int64, k :: Int64  ) :: Int64

Counts the number of ways to partition n items into k unlabelled groups. This quantity is known as Stirling's number of the 2nd kind:

\[\left\{n \atop k \right\} = \frac{1}{k!}\sum_{i=0}^k (-1)^i\binom{k}{i}(k-i)^n\]

Throws a DomainError if inputs do not satisfy n ≥ k ≥ 1.

stirling2_partitions( n :: Int64, k :: Int64 ) :: Vector{Vector{Vector{Int64}}}

Enumerates the unique partitions of n items into k unlabelled sets. Each partition is a vector containing a set of k vectors designating each group.

E.g.

julia> stirling2_partitions(4, 2)
7-element Vector{Vector{Vector{Int64}}}:
 [[1, 2, 3], [4]]
 [[3], [1, 2, 4]]
 [[1, 2], [3, 4]]
 [[1, 3], [2, 4]]
 [[2], [1, 3, 4]]
 [[2, 3], [1, 4]]
 [[1], [2, 3, 4]]

This recursive algorithm was inspired by this blog.

stirling2_matrices( n :: Int64, k :: Int64 ) :: Vector{Matrix{Bool}}

Generates the set of matrices with k rows and n columns where rows correspond to the groups and columns are the grouped elements. A non-zero element designates that the column id is grouped into the corresponding row.

E.g.

julia> stirling2_matrices(4, 2)
7-element Vector{Matrix{Bool}}:
 [1 1 1 0; 0 0 0 1]
 [0 0 1 0; 1 1 0 1]
 [1 1 0 0; 0 0 1 1]
 [1 0 1 0; 0 1 0 1]
 [0 1 0 0; 1 0 1 1]
 [0 1 1 0; 1 0 0 1]
 [1 0 0 0; 0 1 1 1]

A DomainError is thrown if n ≥ k ≥ 1 is not satisfied.

permutation_matrices( dim :: Int64 ) :: Vector{Matrix{Bool}}

Generates the set of square permutation matrices of dimension dim.

E.g.

julia> permutation_matrices(3)
6-element Vector{Matrix{Bool}}:
 [1 0 0; 0 1 0; 0 0 1]
 [1 0 0; 0 0 1; 0 1 0]
 [0 1 0; 1 0 0; 0 0 1]
 [0 0 1; 1 0 0; 0 1 0]
 [0 1 0; 0 0 1; 1 0 0]
 [0 0 1; 0 1 0; 1 0 0]

n_choose_k_matrices( n :: Int64, k :: Int64 ) :: Vector{Matrix{Bool}}

Generates a set of n by k matrices which represent all combinations of selecting k columns from n rows. Each column, contains a single non-zero element and k rows contain a non-zero element.

E.g.

julia> n_choose_k_matrices( 4, 2 )
6-element Vector{Matrix{Bool}}:
 [1 0; 0 1; 0 0; 0 0]
 [1 0; 0 0; 0 1; 0 0]
 [1 0; 0 0; 0 0; 0 1]
 [0 0; 1 0; 0 1; 0 0]
 [0 0; 1 0; 0 0; 0 1]
 [0 0; 0 0; 1 0; 0 1]

A DomainError is thrown if n ≥ k ≥ 1 is not satisfied.

base_n_val(
    num_array :: Vector{Int64},
    base :: Int64;
    big_endian=true :: Bool
) :: Int64

Given an array representing a number in base-n returns the value of that number in base-10.

Inputs:

• num_array - Vector containing semi-positive integers less than base.
• base - The base-n number represented by num_array.
• big_endian - true if most significant place is at index 1, else false.