On Non-squashing Partitions

Back on the 19th June 2016, I created a blog post titled Partitions that finished with my saying that the post was "only the briefest of introductions to the topic". Since then I've not delved much deeper into partitions and today's number of 26303, representing my diurnal age, rekindled my interest. The number belongs to OEIS A089054:

A089054

Solution to the non-squashing boxes problem (version 1).

The comments say the following:

Given \(n\) boxes labeled \(1 \dots n\), such that box \(k\) weighs \(k\) grams and can support a total weight of \(k \) grams; \(a(n)\) = number of stacks of boxes that can be formed such that no box is squashed.

For 26303, the associated number of boxes is 40. However, let's start with a smaller number of boxes to illustrate what is going on. Figure 1 shows the example of four boxes:

Figure 1

For 4 boxes, there are 14 different ways of stacking boxes so that no box is squashed. See Figure 2.

Figure 2

Note that the null stack, where no boxes are used, is also counted. Up to 26303 (where we are dealing with 40 boxes), the sequence runs (beginning with \(n=0\):

1, 2, 4, 8, 14, 23, 36, 54, 78, 109, 149, 199, 262, 339, 434, 548, 686, 849, 1043, 1269, 1535, 1842, 2199, 2607, 3078, 3613, 4225, 4915, 5700, 6581, 7576, 8686, 9934, 11321, 12871, 14585, 16493, 18596, 20925, 23481, 26303, ...

The figure of 2 for \(n=1\) arises from the fact that there can be a single 1 box or the null box. There is a generating function that will yield these numbers: $$ \frac{B(x)-x}{(1-x)^2} \text{ where } B(x)=1 + \frac{x}{1-x} + \frac{\sum \limits_{k>=1} x^{3 \times 2^{k-1}}}{\prod \limits_{j=0 \dots k} (1-x^{2^j)}}$$Let's test this function out using \(k=1\):$$\begin{align} B(x)&=1+ \frac{x}{1-x}+\frac{x^3}{(1-x)(1-x^2)}\\ \\ \frac{B(x)-x}{(1-x)^2} &=\dfrac{1+ \dfrac{x}{1-x}+\dfrac{x^3}{(1-x)(1-x^2)}-x}{(1-x)^2} \end{align}$$

This does in fact produce the first term 1 because the Taylor series expansion is \(1+3x+6x^2+10x^3+\dots \) but the other coefficients are not relevant and it would be necessary to work out a new polynomial for the case of \(k=2\) and so on. A tedious procedure. Let's just assume it works.

Thus there are 26303 ways to stack 40 boxes so that there is no collapse. Examples are [39, 40], [1, 39, 40], [1, 2, 37, 40] and on and on and on. The whole business is explained in detail in this PDF file by Sloane and Sellers: 

https://arxiv.org/pdf/math/0312418.pdf 

but I haven't the mental stamina to get to the bottom of it all in this post. Suffice to say that I've reconnected with the topic of partitions. 

It should be noted that a traditional partition of 40 would be something like [1, 39] where the elements add to 40. The non-squashing partitions of 40 are different as we've seen and take forms like [39, 40], [1, 39, 40], [1, 2, 37, 40] etc. In these, the totals can be no more than 2 x 40 and so in fact range from 0 to 80. This means that for any number \(n\), the non-squashing partitions of \(n\) are particular partitions of all the numbers ranging from 0 to \(2n\).

To illustrate we can go back to the case of \(n=4\) and list the 14 non-squashing partitions of 4 as being (refer back to Figure 2): 

[4], [3, 4], [1, 3, 4], [1, 2, 4], [1, 4], [2, 4], [3], [2, 3], [1, 2, 3], [1, 3], [2], [1, 2], [1], [ ]