Lightweight Mathematical Combinations Using C# in Visual Studio Magazine

I wrote an article titled “Lightweight Mathematical Combinations Using C#” in the July 2022 edition of the Microsoft Visual Studio Magazine. See https://visualstudiomagazine.com/articles/2022/07/20/math-combinations-using-csharp.aspx.

A zero-based mathematical (n, k) combination is a subset of k integers from 0 to n-1. For example, if n = 5 and k = 3 there are 10 combinations:

It’s usual to list combinations in what’s called lexicographical order. If each combination is interpreted as an ordinary integer, the combinations are listed from smallest (12) to largest (234).

The number of (n,k) combinations is n! / (k! * (n-k)!) where n! is factorial(n) = n * (n-1) * (n-2) * . . 1. The function is often called Choose(). For example, Choose(5, 3) = 5! / (3! * (5-3)!) = 120 / (6 * 2) = 120 / 12 = 10.

The number of combinations gets very, very large as n and k increase. For example, Choose(500, 100) =

204,169,423,593,847,671,561,387,240,724,193,094,
030,165,460,090,325,932,474,143,661,505,758,330,
944,415,515,994,945,349,100,113,181,687,417,345

which is significantly larger than the estimated number of atoms in the Universe.

To deal with combinations using the C# language it’s necessary to use the BigInteger data type which can handle arbitrarily large values.

Mathematical combinations are related to, but quite different from, mathematical permutations. A zero-based mathematical permutation of order n is a rearrangement of the integers from 0 to n-1. For example, one permutation of order n = 5 is (2, 0, 1, 4, 3).

In my article I explain how to implement combinations using a simple integer array, compute Choose(n, k) using the BigInteger type, display all (n,k) combinations using a Successor() function, and compute a specific combination element directly.

The examples in the article use zero-based combinations. This is convenient because in many practical uses of combinations, combination values map to array indices. In a pure mathematical context, one-based combinations are more common.

Trade stimulators were early gambling machines. They first appeared in the 1880s. They were placed in bars, cigar shops, and general stores. These early machines didn’t pay off automatically — the owner of the store would pay winners from his cash register.

The first five-card poker trade stimulators didn’t allow holding cards. When a hold feature was added, draw poker trade stimulators became very popular. Most machines had 10 cards on each of the five reels so the virtual deck had only 50 cards instead of 52. Typically the Ten of Spades and Jack of Hearts were omitted. I’m not sure how this changes the possible five-card combinations.

Left: A five-card draw poker machine from the Groetchen Company, circa 1935. Center: A machine with horizontal reels, designed by Charles Fey (1862-1944), who also introduced the first modern slot machine with automatic payout in 1895. Right: A machine from the Rock-Ola Company, circa 1935. Rock-Ola is best known for juke boxes but the company made many other kinds of coin operated games.