https://leetarxiv.substack.com/p/counting-integer-compositions

 
LeetArxiv

LeetArxiv

SubscribeSign in

Share this post

 
[https]
LeetArxiv
LeetArxiv
What Every Programmer Should Know About Enumerative Combinatorics
Copy link
Facebook
Email
Notes
More

What Every Programmer Should Know About Enumerative Combinatorics

A Programmer's Introduction to Exact Counting and Enumeration of
Integer Partitions and Compositions.

 
Murage Kibicho's avatar
Murage Kibicho
May 15, 2025
8

Share this post

 
[https]
LeetArxiv
LeetArxiv
What Every Programmer Should Know About Enumerative Combinatorics
Copy link
Facebook
Email
Notes
More
 
4
 
Share
 
[https]

Quick intro

LeetArxiv is Leetcode for implementing Arxiv and other research
papers.

This is Chapter 1 in our upcoming book, What Every Programmer Needs
to Know about Enumerative Combinatorics.

Past Chapters (Early access for paying subscribers)

  * Chapter 1 (we are here) : Introduction to Integer Partitions and
    Integer Compositions.

  * Chapter 2 : The Factorial Number System as an Alternative to
    Base-2 Binary Computer Architectures.

  * Chapter 3 : The Combinatorial Number System as another
    Alternative to Base-2 Binary Computer Architectures.

  * Chapter 4 : Burrows-Wheeler and Bijective Burrows-Wheeler Sorting
    Algorithms.

  * Chapter 5 : Sinkhorn Propagation as a Backpropagation Substitute.

Stop reading papers. Start coding them. Subscribe for weekly paper
implementations, one semicolon at a time.

[                    ]
Subscribe
1.0 Quick Introduction to Enumerative Combinatorics

Enumerative combinatorics is a branch of mathematics focused on
counting the elements of a set.

For example, determining the number of unique user IDs in a database
is a problem in enumerative combinatorics.

This article showcases how programmers without formal math
backgrounds can use observation and pattern recognition to approach
problems in enumerative combinatorics.

2.0 Introduction to Integer Partitions and Integer Compositions

This section serves as a brief introduction to the theory of integer
partitions and integer compositions.

2.1 Integer Partitions

In combinatorics, a partition of an integer n is a way of writing n
as the sum of a sequence of positive integers (Knuth 1994)1.

For instance, the number 4 can be partitioned into 5 parts :

 
[https]

There is no known closed-form formula to count the number of
partitions of an integer (Knuth 1994). Therefore, we turn to integer
compositions, for which closed-form formulas are known.

2.2 Integer Compositions

A composition is an ordered partition of an integer (Andrews 2004)2.

*One can think of compositions as the permutations of each partition

For instance, the number 4 has 8 compositions :

 
[https]

2.2.1 Formulas for Integer Compositions

The total number of compositions C(n) of a positive integer n is
given by the formula (OEIS 2012)3 :

 
[https]

The number of compositions of n into exactly k positive, non-zero
integers C(n, k)is given by the binomial coefficient (OEIS 2012) :

 
[https]

The proof appears in Corollary 2.5 (Bona 2007)4.

For instance, there are exactly 3 ways to compose the integer 4 into 
2 parts :

 
[https]

A weak composition of an integer is a composition where parts are
allowed to be zero. The number of weak compositions of n into k parts
can be found by either of these formulas :

 
[https]

These formulas appear in Theorem 2.2 (Bona 2007).

2.2.2 C Code to Generate Weak Integer Compositions

Several algorithms exist to enumerate the set of weak compositions of
an integer n into k parts.

First, we provide a function BinomialCoefficient to calculate n
choose k.

Second, we provide PrintArray to print an integer array.

Finally, we provide EnumerateWeakCompositions to iteratively generate
the entire set of weak compositions.

We provide the C code below to generate all weak integer compositions
of an integer into k parts :

This file contains hidden or bidirectional Unicode text that may be
interpreted or compiled differently than what appears below. To
review, open the file in an editor that reveals hidden Unicode
characters. Learn more about bidirectional Unicode characters
Show hidden characters


  #include <stdio.h>

  #include <stdlib.h>

  #include <assert.h>

  #define MAX_K 100

  unsigned long long BinomialCoefficient(int n, int k)

  {

  if(k > n - k){k = n - k;}

  unsigned long long result = 1;

  for(int i = 0; i < k; ++i)

  {

  result *= (n - i);

  result /= (i + 1);

  }

  return result;

  }

  

  void PrintArray(int length, int *array)

  {

  for(int i = 0; i < length; i++)

  {

  printf("%3d, ", array[i]);

  }

  printf("\n");

  }

  

  void EnumerateWeakCompositions(int n, int k)

  {

  //MAX_K is the total number of compositions

  assert(k < MAX_K);

  int currentComposition[MAX_K] = {0};

  //Set the first composition

  currentComposition[k-1] = n;

  int currentSetIndex = 0;

  while(1)

  {

  //Print Current Composition

  printf("%3d : ", currentSetIndex);

  PrintArray(k, currentComposition);

  //Generate next Composition

  int i = 0;

  for(i = k - 2; i >= 0; i--)

  {

  if(currentComposition[i] < n)

  {

  int sum = 0;

  for(int j = 0; j <= i; j++){sum += currentComposition[j];}

  if(sum < n)

  {

  currentComposition[i] += 1;

  int remainder = n;

  for(int j = 0; j <= i; j++){remainder -= currentComposition[j];}

  for(int j = i + 1; j < k -1; j++){currentComposition[j] = 0;}

  currentComposition[k-1] = remainder;

  break;

  }

  }

  }

  //Increase currentSetIndex by 1

  currentSetIndex += 1;

  //Exit the while loop

  if(i < 0){break;}

  }

  }

  

  int main()

  {

  int n = 8;

  int k = 3;

  unsigned long long totalCompositions = BinomialCoefficient(n + k - 
  1, k - 1);

  printf("Weak compositions of %d into %d parts (total = %llu):\n", n
  , k, totalCompositions);

  EnumerateWeakCompositions(n,k);

  }


view raw WeakComposition.c hosted with  by GitHub

3.0 Patterns Observed Within the Enumerated Set of Weak Compositions

*Latex renders better outside the Substack app. This section is best
viewed inside a browser.

We shall examine the example of splitting the integer 8 into 3 weak
compositions. There are 45 elements in the resulting set :

\(\begin{array}{r@{ : \quad}r@{,\quad}r@{,\quad}r} 0 & 0 & 0 & 8 \\ 1
& 0 & 1 & 7 \\ 2 & 0 & 2 & 6 \\ 3 & 0 & 3 & 5 \\ 4 & 0 & 4 & 4 \\ 5 &
0 & 5 & 3 \\ 6 & 0 & 6 & 2 \\ 7 & 0 & 7 & 1 \\ 8 & 0 & 8 & 0 \\ 9 & 1
& 0 & 7 \\ 10 & 1 & 1 & 6 \\ 11 & 1 & 2 & 5 \\ 12 & 1 & 3 & 4 \\ 13 &
1 & 4 & 3 \\ 14 & 1 & 5 & 2 \\ 15 & 1 & 6 & 1 \\ 16 & 1 & 7 & 0 \\ 17
& 2 & 0 & 6 \\ 18 & 2 & 1 & 5 \\ 19 & 2 & 2 & 4 \\ 20 & 2 & 3 & 3 \\
21 & 2 & 4 & 2 \\ 22 & 2 & 5 & 1 \\ 23 & 2 & 6 & 0 \\ 24 & 3 & 0 & 5
\\ 25 & 3 & 1 & 4 \\ 26 & 3 & 2 & 3 \\ 27 & 3 & 3 & 2 \\ 28 & 3 & 4 &
1 \\ 29 & 3 & 5 & 0 \\ 30 & 4 & 0 & 4 \\ 31 & 4 & 1 & 3 \\ 32 & 4 & 2
& 2 \\ 33 & 4 & 3 & 1 \\ 34 & 4 & 4 & 0 \\ 35 & 5 & 0 & 3 \\ 36 & 5 &
1 & 2 \\ 37 & 5 & 2 & 1 \\ 38 & 5 & 3 & 0 \\ 39 & 6 & 0 & 2 \\ 40 & 6
& 1 & 1 \\ 41 & 6 & 2 & 0 \\ 42 & 7 & 0 & 1 \\ 43 & 7 & 1 & 0 \\ 44 &
8 & 0 & 0 \\ \end{array}\)

3.1 Observations on the Rightmost Columns

 1. Notice that the rightmost column forms chains of
    strictly-decreasing sequences. The digits begin at n and descend
    to zero, then the digits start again at n-1 and decrease to zero,
    repeating this pattern :

    \(\begin{array}{r@{ : \quad}r@{,\quad}r@{,\quad}r} 0 & 8 \\ 1 & 7
    \\ 2 & 6 \\ 3 & 5 \\ 4 & 4 \\ 5 & 3 \\ 6 & 2 \\ 7 & 1 \\ 8 & 0 \\
    9 & 7 \\ 10 & 6 \\ 11 & 5 \\ 12 & 4 \\ 13 & 3 \\ 14 & 2 \\ 15 & 1
    \\ 16 & 0 \\ 17 & 6 \\ \vdots & \vdots \\ 44 & 0 \\ \end{array}\)

    We claim that for the right-most column, the digits repeatedly
    occur as the chain of sequences :

    \(n,...,0,n-1,...,0,n-2,...,0\)

 2. Notice that the rightmost column and the second column from the
    right are mirror images of each other :

    \(\begin{array}{r@{ : \quad}r@{,\quad}r@{,\quad}r} 0 & 0 & 8 \\ 1
    & 1 & 7 \\ 2 & 2 & 6 \\ 3 & 3 & 5 \\ 4 & 4 & 4 \\ 5 & 5 & 3 \\ 6&
    6 & 2 \\ 7 & 7 & 1 \\ 8 & 8 & 0 \\ \end{array}\)

    We claim that the sequence of digits in the second column from
    the right is a mirrored and inverted sequence of the rightmost
    column :

\(\begin{array}{r@{ : \quad}r@{,\quad}r@{,\quad}r} 0 & n \\ 1 & n-1 \
\ 2 & n-2 \\ \vdots & \vdots \\ n-2 & 2 \\ n-1 & 1 \\ n & 0 \\ \end
{array}\)

 3. Observe that the digit count in the third column from the right
    corresponds to the number of entries in the decreasing sequence
    of the rightmost column. For instance, we observe the third
    column from the right contains 9 zeros :

    \(\begin{array}{r@{ : \quad}r@{,\quad}r@{,\quad}r} 0 & 0 & \cdots
    & 8 \\ 1 & 0 & \cdots & 7 \\ 2 & 0 & \cdots & 6 \\ 3 & 0 & \cdots
    & 5 \\ 4 & 0 & \cdots & 4 \\ 5 & 0 & \cdots & 3 \\ 6 & 0 & \cdots
    & 2 \\ 7 & 0 & \cdots & 1 \\ 8 & 0 & \cdots & 0 \\ \end{array}\)

From our observations, we claim that tracking the digits in the
column immediately to the right provides enough information to
determine the count of specific digits in any given column.

We further claim that tracking rightmost sums is a possible way to
enumerate the set. This method is inefficient. Thus, we make
observations on the leftmost columns.

3.2 Observations on the Leftmost Columns

The key observation in this section is that : starting from the
leftmost column, the set can be efficiently enumerated using only
binomial coefficients and binary search.

In section 3.0, we saw that there are 45 weak compositions of 8 into 
3 parts.

Observe that 45 is a sum of binomial coefficients :

 
[https]

Notice that in the leftmost column, there are 9 zeros, 8 ones, 7
twos, 6 three, 5 fours, 4 fives, 3 sixes, 2 sevens, and 1 eight.

The main takeaway is that we can use the Hockey Stick Identity 
(Hlapointe 2023)5 to count the number of specific digits in the
leftmost column.

*The Hockey Stick Identity is a formula for summing diagonals along
Pascal's Triangle

In our case, this formulation of the Hockey Stick Identity works best
:

 
[https]

By observation, we note that we use the same identity to count the
number of specific digits in columns from left to right.

4.0 Indexing Elements Within an Enumerated Set

This section utilizes a binary search algorithm to address the
following questions :

 1. What is the weak composition at index j in the enumeration of all
    weak compositions of n into k parts?

 2. What integer corresponds to a given weak composition in this
    enumeration?

We perform a simple binary search to achieve this

This file contains hidden or bidirectional Unicode text that may be
interpreted or compiled differently than what appears below. To
review, open the file in an editor that reveals hidden Unicode
characters. Learn more about bidirectional Unicode characters
Show hidden characters


  #include <stdio.h>

  #include <stdlib.h>

  #include <assert.h>

  #define MAX_K 100

  unsigned long long BinomialCoefficient(int n, int k)

  {

  if(k > n - k){k = n - k;}

  unsigned long long result = 1;

  for(int i = 0; i < k; ++i)

  {

  result *= (n - i);

  result /= (i + 1);

  }

  return result;

  }

  

  void CompareArray(int length, int *array0, int *array1)

  {

  for(int i = 0; i < length; i++)

  {

  assert(array0[i] == array1[i]);

  }

  }

  

  void PrintArray(int length, int *array)

  {

  for(int i = 0; i < length; i++)

  {

  printf("%2d,", array[i]);

  }

  printf("\n");

  }

  

  int FindArraySum(int length, int *array)

  {

  int sum = 0;

  for(int i = 0; i < length; i++)

  {

  sum += array[i];

  }

  return sum;

  }

  

  void EnumerateWeakCompositions(int n, int k, int index)

  {

  //MAX_K is the total number of compositions

  assert(k < MAX_K);

  int currentComposition[MAX_K] = {0};

  //Set the first composition

  currentComposition[k-1] = n;

  int currentSetIndex = 0;

  while(1)

  {

  //Print Current Composition

  if(index == -1)

  {

  printf("%3d : ", currentSetIndex);

  PrintArray(k, currentComposition);

  }

  else

  {

  if(currentSetIndex == index)

  {

  printf("%3d : ", currentSetIndex);

  PrintArray(k, currentComposition);

  break;

  }

  }

  

  

  //Generate next Composition

  int i = 0;

  for(i = k - 2; i >= 0; i--)

  {

  if(currentComposition[i] < n)

  {

  int sum = 0;

  for(int j = 0; j <= i; j++){sum += currentComposition[j];}

  if(sum < n)

  {

  currentComposition[i] += 1;

  int remainder = n;

  for(int j = 0; j <= i; j++){remainder -= currentComposition[j];}

  for(int j = i + 1; j < k -1; j++){currentComposition[j] = 0;}

  currentComposition[k-1] = remainder;

  break;

  }

  }

  }

  //Increase currentSetIndex by 1

  currentSetIndex += 1;

  //Exit the while loop

  if(i < 0){break;}

  }

  }

  

  void GenerateRandomComposition(int n, int k, int randomTime, int *
  array)

  {

  array[0] = n;

  for(int i = 0; i < randomTime; i++)

  {

  int a = rand() % k;

  int b = rand() % k;

  if(array[a] > 0 && array[b] < n)

  {

  array[a] -= 1;

  array[b] += 1;

  }

  }

  //Ensure sum matches n

  int sum = FindArraySum(k, array);

  assert(sum == n);

  }

  

  //First trial

  int FindWeakCompositionIndex0(int n, int k, int *array)

  {

  //Ensure sum matches n

  int sum = FindArraySum(k, array);

  assert(sum == n);

  int index = -1;

  

  unsigned long long currentSum = 0;

  unsigned long long low = 0;

  unsigned long long high = BinomialCoefficient(n + k - 1, k - 1);

  int highestValue = n;

  for(int i = 0; i < k; i++)

  {

  int currentValue = array[i];

  currentSum = 0;

  printf("%lld %d (%d) %lld\n", low, currentValue, highestValue, high
  );

  if(i == 0)

  {

  low = 0;

  high = 0;

  for(int j = 0; j <= currentValue && j <= highestValue; j++)

  {

  unsigned long long binomialCoefficient = BinomialCoefficient(
  highestValue + k-2 - j, k - 2);

  printf("\t|%d %d %lld\n", n + k-2 - j, k - 2, binomialCoefficient);

  currentSum += binomialCoefficient;

  low = high;

  high += binomialCoefficient;

  }

  }

  else

  {

  high = low;

  for(int j = 0; j <= currentValue; j++)

  {

  unsigned long long binomialCoefficient = BinomialCoefficient(
  highestValue + k-2 -i - j, k - 2-i);

  printf("\t|%d %d %lld\n", n + k-2 - j, k - 2, binomialCoefficient);

  if(j > 0){low = high;}

  high += binomialCoefficient;

  

  }

  }

  highestValue -= currentValue;

  }

  

  //Ensure it was found

  index = 1;

  assert(index > 0);

  return index;

  }

  

  //Second Trial

  int FindWeakCompositionIndex(int n, int k, int *array)

  {

  //Ensure sum matches n

  int sum = FindArraySum(k, array);

  assert(sum == n);

  int highestValue = n;

  int currentValue = 0;

  

  unsigned long long low = 0;

  unsigned long long high = 0;

  for(int i = 0; i < k; i++)

  {

  currentValue = array[i];

  //printf("%lld %d (%d) %lld\n", low, currentValue, highestValue,
  high);

  if(high - low == 1){break;}

  high = low;

  for(int j = 0; j <= currentValue; j++)

  {

  unsigned long long binomialCoefficient = BinomialCoefficient(
  highestValue + k-2 - i - j, k - 2- i);

  low = high;

  high += binomialCoefficient;

  }

  highestValue -= currentValue;

  }

  assert(high-low == 1);

  EnumerateWeakCompositions(n,k, low);

  return low;

  }

  

  void IndexToWeakComposition(int index, int n, int k, int *array)

  {

  assert(index > -1);

  unsigned long long low = 0;

  int highestValue = n;

  int currentValue = 0;

  for(int i = 0; i < k; i++)

  {

  for(int j = 0; j <= highestValue; j++)

  {

  unsigned long long binomialCoefficient = BinomialCoefficient(
  highestValue + k-2 - i - j, k - 2- i);

  if(low + binomialCoefficient > index)

  {

  currentValue = j;

  array[i] = j;

  break;

  }

  low += binomialCoefficient;

  }

  highestValue -= currentValue;

  }

  array[k-1] = highestValue;

  }

  

  int main()

  {

  srand(45346);

  int n = 24;

  int k = 7;

  int randomTime = 179203;

  unsigned long long totalCompositions = BinomialCoefficient(n + k - 
  1, k - 1);

  printf("Weak compositions of %d into %d parts (total = %llu):\n", n
  , k, totalCompositions);

  //EnumerateWeakCompositions(n,k, -1);

  

  int *array0 = calloc(k, sizeof(int));

  int *array1 = calloc(k, sizeof(int));

  GenerateRandomComposition(n, k, randomTime, array0);

  PrintArray(k, array0);

  //int index0 = FindWeakCompositionIndex0(n, k, array0);

  int index = FindWeakCompositionIndex(n, k, array0);

  IndexToWeakComposition(index, n, k, array1);

  CompareArray(k, array0, array1);

  free(array0);

  free(array1);

  }


view raw EnumerateWeakComposition.c hosted with  by GitHub

Subscribe if you made it this far.

[                    ]
Subscribe
Citation

Cited as

Kibicho, Murage. (May 2025). Chapter 1 : A Programmer's Introduction to Exact Counting and Enumeration of Integer Partitions and Compositions. What Every Programmer Should Know About Enumerative Combinatorics. LeetArxiv. https://leetarxiv.substack.com/p/counting-integer-compositions.

or

@article{Kibicho2025Chapter1:ProgrammerIntroductionToIntegerPartitionsAndCompositions,
  title   = "Chapter 1 : A Programmer's Introduction to Exact Counting and Enumeration of Integer Partitions and Compositions.",
  author  = "Kibicho, Murage",
  journal = "LeetArxiv",
  year    = "2025",
  month   = "May",
  url     = "https://leetarxiv.substack.com/p/counting-integer-compositions"
}

References

1

Knuth, D. E., Graham, R. L., & Patashnik, O. (1994). Concrete
Mathematics: A Foundation for Computer Science (2nd ed.).
Addison-Wesley.

2

Andrews, George E., & Kimmo Eriksson. (2004). Integer Partitions.
Cambridge University Press.

3

OEIS Foundation Inc. (2012). Integer compositions. OEIS Wiki. Link.

4

Bona, Miklos. (2007). Introduction to Enumerative Combinatorics.
McGraw Hill.

5

Hlapointe. (2023). Proof of the Hockey Stick/Zhu Shijie Identity
[?][?]=0n (t choose k) = (n+1 choose k+1). Mathematics Stack Exchange. 
Link.

8

Share this post

 
[https]
LeetArxiv
LeetArxiv
What Every Programmer Should Know About Enumerative Combinatorics
Copy link
Facebook
Email
Notes
More
 
4
 
Share

Discussion about this post

CommentsRestacks
User's avatar
[                    ]
[                    ]
[                    ]
[                    ]
TopLatestDiscussions

No posts

Ready for more?

[                    ]
Subscribe
(c) 2025 Murage Kibicho
Privacy [?] Terms [?] Collection notice
 Start writingGet the app
Substack is the home for great culture

Share

Copy link
Facebook
Email
Notes
More
This site requires JavaScript to run correctly. Please turn on
JavaScript or unblock scripts