Fixed perimiter partitions

Introduction

#

There’s this charming little theorem due to Euler that goes like this:

Or, in other words, for any number \(n\), the number of partitions with odd parts is equal to the number of partitions with distinct parts. In fact, there’s an even stronger version that goes like this.

Where \(O_{j,k}(n)\) is the number of partitions of \(n\) with exactly \(j\) part sizes divisible by \(k\), and \(D_{j,k}(n)\) is the number of partitions of \(n\) with exactly \(j\) part sizes appearing at least \(k\) times. Theorem 1 occurs when \(k=2\) and \(j=0\).

I have to confess, I thought I had a proof of this theorem, but it turns out I missed the mark by just a bit. However, I still feel encouraged, both because my approach works to prove a slightly different result, and also because it gives some interesting insight into the subject. It’s quite possible that this result is something already known about, which would be very interesting to see!

Cross-referencing j and l

#

First, I’ll give some definitions, trying my best to adhere to the same style of notation I’ve seen in other works on partition theory

Originally, I had thought that \(PO_jD_\ell(k,n)\) would equal \(PO_\ell D_j(k,n)\), but this isn’t exactly true. To show what I mean, here’s a table showing \(PO_\ell D_j(3,35)\) for different values of \(j\) and \(k\):

We can see that \(PO_jD_\ell(k,n)\) is generally close to \(PO_\ell D_j(k,n)\), but not exactly equal. Instead, we can give a slightly more contrived theorem, from some slightly more contrived definitions.

With that definition, we then have

proof:
We define \(\varphi\) to be a function from \(𝒫𝒪_j𝒟_\ell^\star(k,n)\) to \(𝒫𝒪_\ell𝒟_j^\star(k,n)\) defined as follows.

Let \({\lambda_1,\lambda_2 \dots}\) be the part sizes in \(\pi\) that are divisible by \(k\), and let \({\mu_1,\mu_2 \dots}\) be the part sizes in \(\pi\) that appear \(k\) or more times. The part \(\varphi(\pi)\) will contain all the parts with sizes that are not in \({\lambda_1,\lambda_2 \dots}\) or \({\mu_1,\mu_2 \dots}\). Additionally, for each part of size \(\lambda_i\) in \(\pi\), \(\varphi(\pi)\) will contain \(k\) instances of \(\frac{\lambda_i}{k}\). For every part size \(\mu_i\) that appears \(a\) times, let \(b\) be the largest number such that \(bk\leq a\). Then \(\varphi(\pi)\) will contain \(b\) instances of \(k\mu_i\), as well as \(a-bxk\) instances of \(k\mu_i\).

An example of \(\varphi(\pi)\) for \(\pi\in 𝒫𝒪_3𝒟_2^\star(2,29)\) is doodled below:

This function is its own inverse, and can be applied to any partition in \(𝒫𝒪_j𝒟_\ell^\star(k,n)\) to get a partition in \(𝒫𝒪_\ell𝒟_j^\star(k,n)\). Therefore, it is a bijection, and \(PO_jD_\ell^\star(k,n) = PO_\ell D_j^\star(k,n)\).

I’ll confess, the claims in the last paragraph of this proof could be better demonstrated, but for a proof sketch, it’s perfectly cromulent. As a demonstration, here’s a table showing \(PO_\ell D_j^\star(3,35)\) for different values of \(j\) and \(k\):

It would be natural to give definitions that don’t precisely count both the divisibility and distinctness within a partition.

We then have an almost instant corollary of Theorem 3 that mimics Theorem 2.

This is because:

$$ O_{j,k}^\star(n) = \sum_{i=0}^\infty PO_jD_i^\star(kn) = \sum_{i=0}^\infty PO_iD_j^\star(kn) = D_{j,k}^\star(n) $$

Now, the main disappointment that one might have with this theorem is how limiting it is. Barely more than half of the partitions with size 35 have the star property. A different property can be defined that allows for an even stronger theorem, although it requires a somewhat more careful scalpel to carve it out. First, let’s define \(\varphi\) for partitions without the star property.

To give an example of this, it might be nice to think of partitions as matrices. In this representation, the top row of a partition represents part sizes, and the bottom row indicates the number of times that part size appears.

$$ [5, 5, 3, 3, 3, 2, 1, 1] \leftrightarrow \begin{bmatrix} 5 & 3 & 2 & 1 \\ 2 & 4 & 1 & 2 \end{bmatrix} $$

Under this, the current version of \(\varphi\) is a bit easier to see.

$$ \varphi\left( \begin{bmatrix} 45 & 21 & 6 & 4 & 2 & 1 \\ 2 & 1 & 4 & 5 & 19 & 2 \end{bmatrix},3\right) = \begin{bmatrix} 18 & 12 & 7 & 6 & 5 & 4 & 2 & 1 \\ 2 & 1 & 3 & 4 & 18 & 2 & 1 & 2 \end{bmatrix} $$

I appreciate that the exact language of partition theory can be awkward to interpret. If a mathematical definition and example aren’t adequate, the reader is also welcome to look over how I defined \(\varphi\) in Python:

def phi_transform(partition, k):

new_partition = []
part_sizes = []
part_multiplicities = []

# here, I rewrite the partition as consisting of two lists. one of the part sizes,
# and one of the number of times that part appears
last_part = 0
for part in partition:
    if part != last_part:
        part_sizes.append(part)
        part_multiplicities.append(1)
    else:
        part_multiplicities[-1] += 1
    last_part = part

for i in range(len(part_sizes)):

    # This keeps all the stationary blocks and extra parts
    if part_multiplicities[i] >= k and part_sizes[i] % k ==0:
        for time in range(part_multiplicities[i]):
            new_partition.append(part_sizes[i])
    elif part_multiplicities[i] < k and part_sizes[i] % k !=0:
        for time in range(part_multiplicities[i]):
            new_partition.append(part_sizes[i])

    # This converts the parts that are divisible by k into parts that appear many times
    elif part_sizes[i] % k ==0:
        max_exponent = 1
        while part_sizes[i] % k**(max_exponent+1) == 0:
            max_exponent += 1
        for time in range(part_multiplicities[i]*(k**max_exponent)):
            new_partition.append(part_sizes[i]//(k**max_exponent))
            
    # This combines parts that appear k**b times into parts that are divisible by k**b
    elif part_multiplicities[i] >= k:
        max_exponent = 1
        while part_multiplicities[i] >= k**(max_exponent+1):
            max_exponent += 1
        max_multiplicity = 1
        while part_multiplicities[i] >= (max_multiplicity+1)*(k**max_exponent):
            max_multiplicity += 1
        for time in range(max_multiplicity):
            new_partition.append(part_sizes[i]*(k**max_exponent))
        for time in range(part_multiplicities[i] - ((max_multiplicity)*(k**max_exponent))):
            new_partition.append(part_sizes[i])

new_partition.sort(reverse=True)
return(new_partition)

In general, if \(\pi\) is a partition with \(j\) part sizes divisible by \(k\) and \(\ell\) part sizes that appear \(k\) or more times, then \(\varphi(p,k)\) contains \(\ell\) part sizes divisible by \(k\) and \(j\) part sizes appearing \(k\) or more times. There’s a handful of circumstances that would get in the way of that. To avoid those circumstances, let’s define the following adjustment to our previously defined property:

The first of these requirements guarantees that no two part sizes will be brought to the same point while being brought apart. The second of these requirements guarantees that no part will be brought into an already existing stationary block while combining together. The third of these requirements ensures that no part size leaves behind a large number of small parts after being combined together.

This double-star property is much more precise than the star property and captures a much larger set of partitions. Just like with the star property, we have

$$ PO_jD_\ell^{\star\star}(k,n) = PO_\ell D_j^{\star\star}(k,n) $$

and

$$ O_{j,k}^{\star\star}(n) = \sum_{i=0}^\infty PO_jD_i^{\star\star}(kn) = \sum_{i=0}^\infty PO_iD_j^{\star\star}(kn) = D_{j,k}^{\star\star}(n) $$

For all the same reasons as before. In fact, if I were to graph \(PO_j D_\ell^{\star\star}(3,35)\) for different values of \(j\) and \(k\), it would look like this:

This accounts for a much larger proportion of partitions. Roughly 80 percent of partitions with size 35 have the double-star property. If we relax our requirement even further to include all partitions for which \(\varphi\) swaps the number of part sizes divisible by \(k\) and the number of part sizes appearing \(k\) or more times, we cast an even broader net. If we let \(𝒫𝒪_j𝒟_\ell^{\heartsuit}(k,n)\) to be the subset of \(𝒫𝒪_j𝒟_\ell(k,n)\) for which \(\varphi\), we get the following chart for \(𝒫𝒪_j𝒟_\ell^{\heartsuit}(3,35)\):

Finally, if I could be allowed to make just one more such chart, here’s the values of \(𝒫𝒪_j𝒟_\ell(3,35)-𝒫𝒪_j𝒟_\ell^{\heartsuit}(3,35)\):

I’d like to make a more general point about these kinds of grids.

This is one of those lemmas that I have no doubt exists somewhere in the literature, but I figure would be easier to re-prove than find. Because these are notes to demonstrate an idea rather than for publication, I’ll let myself get the extra practice of making a proof for myself.

proof:
This proof will work inductively. For the base case, let \(M\inℳ\) have 0 for all entries and let \(P=\emptyset\). It is trivial to note that \(P\) contains 0 permutations taking \(i\) to \(j\) for any values of \(i\) and \(j\), because \(P\) contains no permutations at all.

Next, let \(M\) be such that \(\sum_i M_{i,k} \leq 1\) and \(\sum_j M_{k,j} \leq 1\) for any value of \(k\). Define \(\sigma\) to be a map from \(ℤ_{\geq 0}\) to \(ℤ_{\geq 0}\) such that \(\sigma(i)=j\) if and only if \(M_{i,j} = 1\). Because of the restrictions on \(M\), \(\sigma\) is an injective function, and therefore a permutation.

Suppose there is some number \(n\) such that any matrix \(L\inℳ\) with \(\sum_{i,j} L_{i,j} \leq n\) has a set of permutations \(S\) such that \(L_{i,j}=|S_{i,j}|\). Let \(N\) and \(M\) be distinct non-zero matrices in \(ℳ\) with \(\sum_{i,j} M_{i,j} = n+1\) and \(\sum_{i,j} N_{i,j} \leq n\). Because both matrices are distinct and non-zero, there is a matrix \(Q=M-N\) that is non-zero and distinct from \(M\). Additionally,

$$ \sum_{i}Q_{i,k}=\sum_{i}M_{i,k}-\sum_i N_{i,k}=\sum_{i}M_{k,i}-\sum_i N_{k,i}=\sum_{i}Q_{k,i} $$

so \(Q\in ℳ\). Because \(\sum_{i,j}N_{i,j}\leq n\) and \(\sum_{i,j}Q_{i,j}\leq n\), there exists multisets of partitions \(S\) and \(R\) such that \(N_{i,j}=|S_{i,j}|\) and \(Q_{i,j}=|R_{i,j}|\). It follows that

$$ M_{i,j} = N_{i,j}+Q_{i,j} = |S_{i,j}|+|Q_{i,j}|= |(S\cup Q)_i,j| $$

The following corollary is easy to build:

This applies directly to what we have already shown. Partitions in \(𝒫𝒪_j𝒟_\ell^{\star\star}(k,n)\) are brought to partitions in \(𝒫𝒪_\ell 𝒟_j^{\star\star}(k,n)\) by \(\varphi\), meaning that each partition and its image under \(\varphi\) correspond to a transposition of \(j\) and \(\ell\). There must exist some other \(n\)-cycles of partitions that make up the rest of \(p(k,n)\), although this is a matter of future speculation.

Franklin equations for fixed perimeter partitions

#

The reason I’ve been using this method to explore Theorem 2 has been to use that as inspiration for exploring a conjectured fixed perimeter analogue. The conjecture, due to Gray, Payne, Swisher, and Watson, looks like this:

If \\(j\geq0\\), \\(k\geq2\\), then \\(FD_{j,k}(n)\geq FO_{j,k}(n)\\) for sufficiently large \\(n\\).

Where \(FD_{j,k}(n)\) is the number of partitions with perimeter \(n\) that contain exactly \(j\) part sizes appear at least \(k\) times, and \(FO_{j,k}(n)\) is the number of partitions with perimeter \(n\) that contain exactly \(j\) part sizes divisible by \(k\). If I were to try to prove this conjecture using the same general strategy I used while considering Theorem 2, I’d start by defining the following expressions:

Where \(r(n|\star)\) is the number of partitions with perimeter \(n\) that follow condition \(\star\). I’m curious what sort of relationships exist between \(FO_jD_\ell(k,n)\) and \(FO_\ell D_j(k,n)\). To begin, let’s look at a table of values for \(FO_jD_\ell(3,16)\).

I’ll first note that \(\sum_j FD_{j,k}(n)=\sum_j FO_{j,k}(n)\) for any values of \(j\), \(k\), and \(n\). This means that it is only possible for \(FD_{j,k}(n)\) to be larger than \(FO_{j,k}(n)\) for some combinations of \(j\) if \(FD_{j,k}(n)\) is smaller than \(FO_{j,k}(n)\). Looking at this from the perspective built in the last chapter, we can conclude that there must be more partitions at the top left of the chart, rather than strictly as parts of permutations.

If possible, it would be nice to find a mapping that takes individual partitions with low values of \(j\) and high values of \(\ell\) and maps them to non-overlapping sets of partitions with high values of \(j\) and low values of \(\ell\). Unfortunately, we can see that \(FO_jD_\ell(k,n)\) is not always larger than \(FO_\ell D_j(k,n)\) when \(j>\ell\). For example, \(FO_3D_2(3,16)\le FO_2D_3(3,16)\).

Other thoughts

#

I’d like to introduce one more idea I’ve had floating around. In addition to the standard way of writing partitions as non-increasing list of integers, the Ferrers diagram, and the Fu-Tang profile, I’ll often think of partitions as 2-d matrices, in which the top row contains all integers less than or equal to the arm length, and the bottom row contains the multiplicities of parts with that length. To give an example,

$$\begin{align*} &7+6+6+3+2+1+1+1 \\ \equiv &\{E,N,N,N,E,N,E,E,E,N,N,E,N\}\\ \equiv &\begin{bmatrix} 7 & 6 & 5 & 4 & 3 & 2 & 1\\ 1 & 2 & 0 & 0 & 1 & 1 & 3\end{bmatrix}\\ \end{align*}$$

We can simplify this even further by only including the bottom row.

$$\begin{align*} &7+6+6+3+2+1+1+1 \\ \equiv &\{E,N,N,N,E,N,E,E,E,N,N,E,N\}\\ \equiv & [1,2,0,0,1,1,3]\\ \end{align*}$$

Effectively, this way of representing partitions is the same as counting the lengths of ``\(N\)" strings in the Fu-Tang profile, written backwards. It’s quite useful, in my opinion, and it’s what I use to represent fixed-length partitions in computer searches. I’ll call this the \textit{sequence} view of a partition for now, although it’s quite likely that someone else has already given it a name.

The nice thing about the sequence view, for the sake of fixed-perimeter partitions, is how easy it is to see the aspects of a partition’s perimeter. The length of a sequence is the partition’s arm length, and the sum of a sequence is the partition’s leg length. The only requirement for a sequence to represent a partition is that the first digit must be 1.

This allows for fixed perimeter partitions to be counted pretty tidily without the need for generating functions. To calculate \(r(\alpha,\lambda,n)\), we need to populate a sequence that is \(\alpha\) spots long. The first spot in the sequence must be at least 1, but after that, we have \(\lambda-1\) ``counters" to place in \(\alpha\) spots. Using the stars and bars formula, we get:

$$ r(\alpha,\lambda,n)=\binom{\alpha+\lambda-2}{\alpha-1} $$

This same method can give us \(FO_{j,k}(\alpha,\lambda,n)\) as well. First, let’s assume that \(\alpha\) is not divisible by \(k\). In this case, there are \(\left\lfloor\frac{\alpha}{k}\right\rfloor\) values in \([1,\alpha]\) that are divisible by \(k\). The number of ways to choose from \(j\) of these values is therefore

$$ \binom{\left\lfloor\frac{\alpha}{k}\right\rfloor}{j} $$

Any partition in \(ℱ𝒪_{j,k}(\alpha,\lambda,n)\) must have at least one part of size \(\alpha\) and at least one part of \(j\) sizes divisible by \(k\). The remaining \(\lambda-j-1\) parts can have any size out of \(\alpha-\left\lfloor\frac{\alpha}{k}\right\rfloor+j\) possible sizes. Therefore, we have

$$\begin{align*} FO_{j,k}(\alpha,\lambda,n) &=\binom{\left\lfloor\frac{\alpha}{k}\right\rfloor}{j}\cdot\binom{\lambda-j-1+\alpha-\left\lfloor\frac{\alpha}{k}\right\rfloor+j-1}{\alpha-\left\lfloor\frac{\alpha}{k}\right\rfloor+j-1}\\ &=\binom{\left\lfloor\frac{\alpha}{k}\right\rfloor}{j}\cdot\binom{\lambda+\alpha-\left\lfloor\frac{\alpha}{k}\right\rfloor-2}{\alpha-\left\lfloor\frac{\alpha}{k}\right\rfloor+j-1}\\ \end{align*}$$

If \(\alpha\) is divisible by \(k\), then this formula has to be adjusted. The necessary part of size \(\alpha\) means that only \(j-1\) sizes divisible by \(k\) need to be chosen, and there are only \(\frac{\alpha}{k}-1\) options to choose from.

$$ \binom{\frac{\alpha}{k}-1}{j-1} $$

After the part sizes divisible by $k$ are chosen, there are \(\lambda-j\) parts to place, and they may have sizes within a set of size \(\alpha-\frac{\alpha}{k}+j\). Therefore, if \(\alpha\) is divisible by \(k\),

$$\begin{align*} FO_{j,k}(\alpha,\lambda,n) &=\binom{\frac{\alpha}{k}-1}{j-1}\cdot\binom{\lambda-j+\alpha-\frac{\alpha}{k}+j-1}{\alpha-\frac{\alpha}{k}+j-1}\\ &=\binom{\frac{\alpha}{k}-1}{j-1}\cdot\binom{\lambda+\alpha-\frac{\alpha}{k}-1}{\alpha-\frac{\alpha}{k}+j-1}\\ \end{align*}$$

Finding a formula for \(FD_{j,k}(\alpha,\lambda,n)\) seems considerably more difficult, unfortunately.