Pyramid Schemes for Eating M&Ms: Enumeration, Generation, and Gray Codes

We investigate a fun problem invented by the second author while eating colourful pyramids of chocolate M&Ms. In brief, an M&M pyramid of height $n$ has a top row of one M&M, a second row of two M&Ms, a third row of three M&Ms, and so on, with the property that the colours are the same on each row and different on distinct rows. The M&M Problem asks for the number of distinct ways that $n$ of the M&Ms can be removed (i.e., eaten!) so that the remaining M&Ms can be rearranged to form an M&M pyramid of height $n-1$. Here we care only about the quantity of each colour eaten and not the order that they were enjoyed¹¹1In other words, we don’t care if you “eat the red ones last.” This was a slogan for the Canadian version of this type of chocolate candy known as Smarties. In the United States you can also play this game with Smarties although they are the pastel-colored discs that are known as Rockets in Canada! [3, 14].. Figure 1 illustrates that the answer for $n=4$ is $8$. In particular, note that leftmost solution eats the entire bottom green row while the rightmost eats one of each colour.

Section 2 answers this snack-sized problem by proving that there are $2^{n-1}$ solutions. Furthermore, each solution is naturally represented as a binary string of length $n-1$, a composition of $n$, a subset of $[n-1]$, or as a permutation of $[n]$ in which each symbol appears at most one position to the right relative to its natural position in the identity $\mathrm{1\hspace{0.17em}2}\mathrm{\cdots }n$.

In Section 3 we lower the number of possible solutions using a parameter $m$. In the limited version of the problem at most $m$ of each colour can be eaten. There is one solution when $m=1$ (i.e., eat one of each colour). Otherwise, the answers are Fibonacci ($m=2$), Tribonacci ($m=3$), Tetranacci ($m=4$), and so on (with the base cases omitted), up to the unlimited problem with $2^{n-1}$ solutions ($m=n$). The corresponding objects are also limited in natural ways, including binary strings avoiding $0^m$ and permutations in which each value is at most one position to the right and $\mathrm{\ell }=m-1$ positions to the left relative to the identity.

Our first result implies that the number of M&M permutations of $[n]$ is $2^{n-1}$. Perhaps the most well-known class of permutations of this size is peakless permutations. Those permutations play a central role in the recent Combinatorial Generation by Permutation Languages series [25] which is currently on its seventh entry [9, 10]. In particular, the bijection between peakless permutations and binary strings laid the foundation for generalizations of the binary reflected Gray code to larger permutation languages. In this paper we provide a swap Gray code for M&M permutations meaning that successive permutations differ by swapping consecutive entries. The order is visualized as a weaving pattern in Figure 3(a) (using the ribbon style from [40]). If the pattern looks familiar, it is because it is identical to the binary reflected Gray code! Indeed, the crossings in 3(a) line up exactly with the twists in Figure 3(b). Pleasantly, we obtain similar Gray codes for the corresponding objects with parameter $m$ (or $\mathrm{\ell }=m-1$) including binary strings avoiding $0^m$, and M&M permutations in which each value moves at most $\mathrm{\ell }$ positions to the left. Furthermore, the corresponding rearranged pyramids (see Figure 6) differ in the colour of a single M&M!

In Section 5 we turn our attention to generation algorithms. We explain how the Gray codes parameterized by $m$ (or $\mathrm{\ell }=m-1$) are generated by simple greedy algorithms. For example, the bitstrings avoiding $0^m$ are generated by greedily flipping the leftmost bit, while greedily swapping the leftmost pair of values produces the M&M permutations where each value moves at most $\mathrm{\ell }$ positions to the left. Surprisingly, the two greedy algorithms use the same change sequence with bit $b_i$ flipping when adjacent values $p_i{p}_{i+1}$ swap. The same order also produces a pleasant Gray code for the rearranged M&M pyramids: the colour of a single eaten M&M is changed.

While the algorithms in Section 5 are simple, they are not efficient due to memory usage. In Section 6 we derive the first successor rule for the Gray code of binary strings avoiding $0^m$. This allows us to create generation algorithms that are memoryless (i.e., previously generated objects are not remembered) and loopless (i.e., worst-case $O(1)$-time per object) which is optimal in terms of time efficiency.

In Section 7 we return to counting M&Ms, but this time we raise the number of possible solutions by introducing a parameter $r$. In the relaxed problem we widen (or narrow) the pyramid with $n$ rows as follows. The top row has $r$ M&Ms, the second row has $r+1$ M&Ms, the third row has $r+2$ M&Ms, and so on, except that each row also has width at most $n$. The initial shapes for $n=4$ are shown in Figure 4. The goal remains the same: eat M&Ms so that the remaining M&Ms can be rearranged into a standard pyramid shape with $n$ rows.

• $\mathrm{■}$

  When $r=0$ there is only one solution as the initial shape is a pyramid with $n-1$ rows.

• $\mathrm{■}$

  When $r=1$ we have the original problem so the number of solutions is $2^{n-1}$.

• $\mathrm{■}$

  When $r=n-1$ or $r=n$ the number of solutions is $n!$ since any permutation of the colours is possible for the remaining pyramid.

More generally, we prove that the number of solutions is the $n$-term product $⟨n,r⟩!=1\cdot 2\cdot 3\mathrm{\cdots }r\cdot r+1\cdot r+1\mathrm{\cdots }r+1$ which we refer to as a flatorial number.

In North America many holidays involve the giving and receiving of treats that often come in different colours, but are otherwise similar. At Easter there are Cadbury’s mini eggs; at Halloween there are many examples including M&Ms, Resses Pieces, Rockets, Smarties, Skittles; at Christmas there are Hershey’s kisses in holiday colours; Chocolate Chanukkah gelt is sometimes given during Hanukkah which varies in size (or coin denomination) rather than colour. Different candies come in different numbers of colours as shown in Table 1 which can aid you in determining what confectionary to purchase as you explore the mathematics we discuss²²2Remember to brush and floss every day while engaging in such research.. To make our work as accessible as possible to a more healthy dietary exploration, we note that mixed nuts could easily include up to nine different types: almond, brazil, cashew, hazelnuts, macadamia, peanut, pecans, pistachios, walnuts. The problem originated with M&Ms and since Mars Wrigley Confectionery does produce at least nineteen different colours, allowing for large pyramids, we will discuss the problem in the context of M&Ms.

When reaching into a bag of M&Ms and pulling out a handful, usually the distribution of colours is not uniform and some colours appear more often and some only a few times. Noticing this in a sample handful of M&Ms one time, the second author started to arrange them on the table in order of the number of times a colour appeared. Frequently these distributions were close to being a pyramid. While it is a natural impulse to start nibbling on some M&Ms from the handful, for a mathematician it was perhaps inevitable to start with the few necessary to create a true pyramid. Once having a pyramid with $n$ different rows (colours), the author wondered how he could eat $n$ of the M&Ms and obtain a pyramid with $n-1$ different rows.

Given a rainbow pyramid of height $n$, in how many ways can we remove a total of $n$ so that the remainder can form a rainbow pyramid of height $n-1$?

The largest colour class in a pyramid with $n$ rows is size $n$ so it is clear that we must eat at least one M&M from the largest class. Once this is eaten there are now two colour classes that have size $n-1$. One and only one of them must remain at the end when we produce a pyramid with $n-1$ rows, so we have a choice between eating one M&M from exactly one of these two colour classes. At each stage, after we have eaten one M&M from our choice of exactly two colour classes of size $i$, all the colour classes of size $i$ and larger in the pyramid with $n-1$ rows will have been determined and no more M&Ms can be eaten from any of these size classes. We have two colour classes of size $i-1$ and the colour class of size $i-1$ in the pyramid with $n-1$ rows must be one of these. Therefore, we must eat one M&M from exactly one of these classes of size $i-1$ and an induction proves the following theorem.

Before moving on to other mathematical connections, we note a recent amusing experience. The second author was eating a rainbow pyramid of a more healthy food (cherry tomatoes) where he has a prejudice against the red tomatoes. Whatever rainbow pyramid he initially started with, he found once he reached the next smaller rainbow pyramid he was inevitably left without any red tomatoes due to this bias. Thus when there are $i$ red tomatoes in a rainbow pyramid with $n$ rows, instead of $2^{n-1}$ possible eating paths to the next rainbow pyramid, he was left with $2^{n-i}$ eating paths³³3Exercise left to the reader.. In this case, the red tomatoes were more numerous than the other colours and in his lunch the red colour class was often the largest and frequently he was left with no choices at all. Samuel Beckett has a delightful expression of how our prejudices, both positive and negative, reduce the fullness of our experiences in life (also featuring permutations) in his novel Murphy [4].

Murphy receded a little way into the north [of the park] and prepared to finish his lunch. He took the biscuits carefully out of the packet and laid them face upward on the grass, in order as he felt of edibility. They were the same as always, a Ginger, an Osborne, a Digestive, a Petit Beurre and one anonymous. He always ate the first-named last, because he liked it the best, and the anonymous first, because he thought it very likely the least palatable. The order in which he ate the remaining three was indifferent to him and varied irregularly from day to day. On his knees now before the five it struck him for the first time that these prepossessions reduced to a paltry six the number of ways in which he could make this meal. But this was to violate the very essence of assortment, this was red permanganate on the Rima of variety. Even if he conquered his prejudice against the anonymous, still there would be only twenty-four ways in which the biscuits could be eaten. But were he to take the final step and overcome his infatuation with the ginger, then the assortment would spring to life before him, dancing the radiant measure of its total permutability, edible in a hundred and twenty ways!

Overcome by these perspectives Murphy fell forward on his face in the grass, beside those biscuits of which it could be said as truly as of the stars, that one differed from another, but of which he could not partake in their fullness until he had learnt not to prefer any one to any other.

Murphy is “wrestling with the demon of gingerbread” when he is distracted by a woman speaking. While in conversation the woman’s dog eats all the biscuits except the ginger.

There are other combinatorial classes of objects that have cardinality $2^{n-1}$. Here we consider binary strings, subsets, compositions, and a special type of permutation, and show that they have natural bijections to our rainbow pyramid solutions. These results are then summarized in Theorem 2 and illustrated in Example 3 and Figure 5.

In the sequence of binary choices outlined above, we start by eating one M&M from the largest class. Then at stage $i$ we are always choosing between eating one of the existing colour class of size $i$ or one of the colour class most recently eaten. If we encode these choices as $b_i=1,0$ respectively, then we form a bijection to the binary strings $b_1{b}_2\mathrm{\cdots }{b}_{n-1}$ of length $n-1$. We note that the sequence of decisions are made in time as the $b_i$ are listed from right to left in this string. If $b_i=1$, then we will have the opportunity to eat more of that colour, but if $b_i=0$ then we will not. Thus if $b_i=0$ this indicates that no M&M of colour $i$ is ever eaten and that colour will be the colour class of size $i$ in the obtained rainbow pyramid. Thus the values of $i$ for which $b_i=1$ are precisely the colours where at least one M&M of that colour are eaten. The positions of the zeros give a bijection to the subsets of $[n-1]$ via the “uneaten map” and the positions of the ones give another bijection to the subsets of $[n-1]$ via the “(at least one) eaten map” (disregarding the colour $n$ which must always be eaten).

Labelling the M&Ms in the colour class of size $i$ with the label $i$ for simplicity, we can form the sequence of the number of $i$s that we ate, left to right, from 1 to $n$, “eaten representation”. In eaten representation $e$ we will say that $e_i$ is the number of items labelled $i$ that are eaten. This is an ordered summation to $n$, allowing zeros, such that the summand in position $i$ must be no larger than $i$ and the summand in position $n$ is at least 1. Observe that the position of the zeros match the positions of the zeros in the binary string representation. If we drop the zeros we obtain a simple composition of $n$ and thus a map from the eaten representation to the compositions of $n$. We claim that this map is injective. It is easy to check that this is true for small values of $n$. For an induction, now suppose that there are two eaten representations, $e$ and $f$, mapping to the same composition of $n$ and that we have the smallest value of $n$ for which this is possible. Since at least one item labelled $n$ is eaten we know that the rightmost summand of the composition must be the number of $n$s eaten, and that these two values agree in both composition and thus agree in the eaten representation. For each $n$ eaten after the first, the next smaller colour class is ignored. Thus $e_n=f_n$ and for both eaten representations the next rightmost non-zero value is in position $n-e_n$. Thus the eaten representation from position $n-e_n$ left is a valid eaten representation for a rainbow pyramid of height $n-e_n$ and inducton gives the result. Since the number of eaten representations and number of compositions of $n$ both have cardinality $2^{n-1}$ this gives a bijection between the two sets.

Again labeling the items in the colour class of size $i$ with label $i$, the starting rainbow pyramid is naturally represented by the identify permutation $12\mathrm{\cdots }n$. After having eaten the $n$ M&Ms to obtain the new rainbow pyramid, add back one M&M of each colour to produce another pyramid of the original size and consider its corresponding permutation, $\pi$, of $1,2,\mathrm{\dots },n$. The positions of the zeros in the binary string representation (and also the zeros in the eaten representation) correspond exactly to the set of colours that were not eaten at all. These colour classes stayed the same size and then add the one additional M&M added so in $\pi$ have moved right exactly one position from their starting position. Since there were $i$ items labeled $i$ in the starting rainbow pyramid, no label can move more than one position to the right. The new permutation $\pi$ is uniquely determined by what has been eaten so this gives a bijection to the set of permutations of size $n$ such that each symbol appears at most one position to the right relative to its natural position in the identity $\mathrm{1\hspace{0.17em}2}\mathrm{\cdots }n$. That this family had cardinality $2^{n-1}$ was observed by Arndt [2] in work that we discuss later on.

Suppose that we want to avoid eating too many M&Ms of the same colour. More specifically, we limit ourselves to eating at most $m$ copies of any given colour, where $m$ is some fixed constant. This leads to a generalization of our original problem parameterized by $m$.

Given a rainbow pyramid of height $n$, in how many ways can we remove at most $m$ of each colour so that the remainder can form a rainbow pyramid of height $n-1$?

Once again we consider solutions as unordered selections of colours, and every solution removes exactly $n$ of the M&Ms. Now let us consider how our various representations are modified under this chromatic limitation. For some objects it is convenient to use $\mathrm{\ell }=m-1$.

Binary strings of length $n-1$.

As in the original problem we know that at least one copy of colour $n$ is removed, and bit $b_i=1$ when at least one copy of colour $i$ is removed. However, not every binary string of length $n-1$ encodes a valid solution when the use of each colour is limited. Indeed, the following points show that a solution is valid, if and only if, the binary string avoids substrings of the form $0^m$ (or equivalently, $0^{\mathrm{\ell }}$ is the longest run of $0$s allowed).

• $\mathrm{■}$

  Substring $b_{i-m}{b}_{i-m+1}\mathrm{\cdots }{b}_i=00\mathrm{\cdots }01=0^{m}1$ indicates $m$ copies of colour $i$ are removed.

• $\mathrm{■}$

  Suffix $b_{n-m+1}{b}_{n-m+2}\mathrm{\cdots }{b}_n=00\mathrm{\cdots }0=0^m$ indicates $m$ copies of colour $n$ are removed.

Subsets of $[n-1]$.

Consecutive values in the subset (union with $\{0,n\}$) differ by at most $m$.

Compositions of $n$.

Each part is at most $m$.

Permutations of $[n]$.

Each symbol can move at most one position to the right and at most $\mathrm{\ell }$ positions to the left relative to the identity.

These observations lead to the following theorem. Note that the correspondences with the M&M Problem are new, while those involving the other M&M objects can be found in various textbooks on combinatorics [28].

Given a combinatorial object of a particular type and size (e.g., $n$-bit binary strings, permutations of $[n]$, binary trees with $n$ nodes) a Gray code orders the objects such that consecutive objects are similar to each other in some particular way. Humans with various backgrounds have been constructing these types of patterns for hundreds of years. For example, bell-ringers in the 1600s created plain changes [16, 52] which orders the $n!$ permutations of $[n]$ so that consecutive permutations different by swapping two consecutive values in one-line notation (e.g., $\overline{12}3$, $2\overline{13}$, $\overline{23}1$, $3\overline{21}$, $\overline{31}2$, $132$ for $n=3$). Plain changes was rediscovered multiple times in the 1960s leading to its alternate moniker: the Steinhaus-Johnson-Trotter algorithm [53, 30, 56]. Another Gray code for permutations, this time using prefix-reversals, was discovered in the late 1700s by Klügel [29] (e.g., $\overleftrightarrow{123}$, $\overleftrightarrow{21}3$, $\overleftrightarrow{312}$, $\overleftrightarrow{13}2$, $\overleftrightarrow{231}$, $\overleftrightarrow{32}1$).

The obsession with listing all possibilities with small changes between them also extends to Beckett and his works. In particular, Quad [5] is a play with four actors in which every non-empty subset of actors appear onstage in successive scenes with a single performer entering or exiting to create the next scene. Furthermore, Beckett required that the actor who had been offstage the longest would always be the one who entered. This idea led to the notion of a Beckett Gray code [49, 60, 15]. Similarly, it is easy to imagine Murphy obsessing over similar issues when eating his cookies.

In this section we discuss the binary reflected Gray code, the concepts of sublist and simultaneous Gray code, and how these ideas apply to our M&M objects parameterized by $m$. The results are illustrated in Figure 6.

In the half-century following Gray’s patent, recursion was used in various ways to create new Gray codes, as reflected in Savage’s survey from the late-1990s [45]. In the last decade, it has become more common to view the binary reflected Gray code as the result of a simple greedy algorithm. The algorithm starts the order with the string $0^n$, then it repeatedly creates a new next string by flipping the leftmost bit in the most recent string. Or less verbosely: flip the leftmost bit. This process continues until no flips are possible (i.e., flipping any bit in the most recent string recreates a previous string).

Many previous Gray code constructions can be re-expressed in terms of greedy algorithms. For example, plain changes and Klügel’s order from Section 4 are generated from $12\mathrm{\cdots }n$ by swapping the smallest value and reversing the shortest prefix, respectively [59].

The greedy perspective has led to a surge of new results, including fun results on pancake flipping [19] and matroids [34]. It has also been used to generate various subsets of binary strings [57, 27] and solve multiple conjectures [33, 33]. However, the biggest success of the approach is the Combinatorial Generation via Permutation Languages series of papers⁴⁴4The smallest “zig-zag language” is another set of permutations enumerated by $2^{n-1}$. The peakless permutations avoid the patterns $231$ and $132$ [7] and the connection between them and the binary reflected Gray code motivated us to consider the Gray codes in this paper.. The series was initially announced in an extended abstract and poster at Permutations Patterns 2019 [23] before appearing as conventional conference and journal papers [24, 25]. Since then it has grown to its seventh entry [9, 10] with a generalization involving multiset permutations (or $s$-words) recently announced [12]. The greedy approach is featured in Mütze’s updated survey of Gray codes [36] which is regularly updated on arXiv [35] and also appears as a dynamic survey in the Electronic Journal of Combinatorics [37].

While the algorithms in Section 5 are simple, they are also inefficient. In particular, remembering previously generated objects uses exponential space relative to $n$ even when $\mathrm{\ell }=1$ (as the Fibonacci sequence grows like $O({\varphi }^n)$ for the golden ratio $\varphi \approx 1.62$).

In this section we develop a successor rule for the binary strings avoiding $0^{\mathrm{\ell }+1}$. In other words, we show how to directly map any such binary string into the next binary string in the Gray code without any additional information. By carefully maintaining $O(n)$ additional space, we are able to repeatedly apply the successor rule in constant time. In other words, we create loopless algorithm which generates successive objects in worst-case $O(1)$-time. Loopless algorithms were pioneered by Ehrlich [18] and are best possible in terms of time-complexity.

To better contextualize these results we first differentiate between enumeration algorithms and generation algorithms.

Now we consider the relaxed problem initially seen in Figure 4(b). When $r=0$ there is only one solution (i.e., no M&Ms are eaten), the original problem is obtained with $r=1$, and problems with $r>1$ involve eating more M&Ms (which is arguably the real goal!).

Given the results of the previous sections, it becomes natural to ask if there are other classes of permutations counted by $2^{n-1}$ or more generally the flatorial numbers. In this section we use a tree-based argument to prove that eight distinct classes have this property [26]. These classes are one-way bounded permutations on $[n]$ for a fixed parameter $0\le r\le n$.

Let $S_n$ be the set of all permutations of $[n]=\{1,2,\mathrm{\dots },n\}$ in one-line notation. Consider the following two subsets of $S_n$ for $n=4$ and a fixed parameter $r=1$ explained below.

The first set contains permutations $p_1{p}_2\mathrm{\cdots }{p}_n$ in which $p_i^{-1}>i$ implies $i\le r$. In other words, if a value $i$ appears further to the right than it does in the identity, then $i\le r$. Since $r=1$ in (8), only value $1$ (underlined) can appear to the right of its position in $\mathrm{𝗂𝖽}$. The second set contains permutations whose inversion vector⁶⁶6The inversion vector counts the smaller inverted values. That is, . (shown below) $v_1{v}_2\mathrm{\cdots }{v}_n$ has $v_i\le r$ for all $i$. In other words, every value is inverted with at most $r$ smaller values. Since $r=1$ in (9), each value is inverted with at most one smaller value.

The two sets have the same cardinality; we will prove that this is true for all $n$ and $r$. Moreover, this is true for eight classes of one-way bounded permutations that are listed in Definition 29. None of our equivalences are obtained by reversing indices $p_n\mathrm{\cdots }{p}_2{p}_1$ and/or inverting values $(n-p_1+1)(n-p_2+1)\mathrm{\cdots }(n-p_n+1)$. These trivial modifications known as the symmetries of the square extend our results to $8\cdot 4=32$ equinumerous types. For example, the “low rights” in (8) become “high lefts” (i.e., implies $i\ge n-r+1$) by reversing and inverting. Our results are summarized in Table 2. While each type is fairly elementary, we were unable to find many references in the literature. Table 3 shows that only three of the types are listed in corresponding Oeis entries. Short descents with $r=2$ arise using classic pattern avoidance [7]: $\overline{\mathrm{𝖽𝗌𝖼}}(n,2)={\mathrm{𝖠𝗏}}_n(312,231)$). Some non-classical avoidance results also appear in the Oeis sequences [8, 20].