Browse by Topic
Related Topics

# An Intriguing Identity: Connecting Distinct and Complete Integer Partitions

Number theory is a very old subject that in modern times has branched into various large areas. One of these is additive number theory, with problems like this: when is a prime the sum of two squares? Primes are part of the more classical area now called multiplicative number theory, so as this problem of Fermat’s indicates, the two areas are intimately connected. The problem I discuss in this blog is a mix of additive and multiplicative number theory, with a dash of linear algebra.

Before I give strict definitions, here is the intuitive version of an integer partition via an example: . However, don’t add up! Just think of the sum 14 as being broken up into the four parts: 7, 3, 3, 1. Now the standard additive question is, how many ways are there of breaking 14 into parts? In other words, how many partitions of 14 are there? As we often say, the Wolfram Language has a function for that:

 ✕ `PartitionsP[14]`

I’ll explain the pieces of the problem at hand as we go along; consider this a succinct abstract:

Two infinite lower-triangular matrices related to integer partitions are inverses of each other. The matrix ν comes from an additive analogue of the multiplicative Möbius μ function, while γ comes from counting generalized complete partitions; a complete partition of n has all possible subsums 1 to n.

## Wolfram Language Definitions

First I’ll set up the function definitions we will use.

 ✕ `Ferrers@p_ := Framed@Grid[Table["\[FilledCircle]", #] & /@ p]`
 ✕ ```ConjugatePartition[l_List] := Module[{i, r = Reverse[l], n = Length[l]}, Table[n + 1 - Position[r, _?(# >= i &), Infinity, 1][[1, 1]], {i, l[[1]]}]]```
 ✕ `DistinctPartitionQ@x_ := Length@x == Length@Union@x`
 ✕ ```DistinctPartitions@n_ := Select[IntegerPartitions@n, DistinctPartitionQ]```
 ✕ ```PartitionMu@\[Lambda]_ := If[DistinctPartitionQ@\[Lambda], (-1)^Length@\[Lambda], 0]```
 ✕ ```DistinctPartitionsByMax[n_, m_] := \!\(TraditionalForm\`DistinctPartitionsByMax\)[n, m] = Select[IntegerPartitions@n, (Sort@# == Union@#) && (Max@# == m) &]```
 ✕ ```PartitionsMuByMax[n_, m_] := PartitionsMuByMax[n, m] = Length@DistinctPartitionsByMax[n, m] - 2 Length@Select[DistinctPartitionsByMax[n, m], EvenQ@*Length]```
 ✕ `PartitionsMuByMax@r_ := Table[PartitionsMuByMax[i, j], {i, r}, {j, i}]`
 ✕ `\[Nu]@r_ := PadRight@Table[PartitionsMuByMax[i, j], {i, r}, {j, i}]`
 ✕ ```KStepPartitionQ[\[Lambda]_, k_] := MemberQ[Range@k, Last@\[Lambda]] && And @@ Table[\[Lambda][[j]] - k <= Total@Drop[\[Lambda], First@Last@Position[\[Lambda], \[Lambda][[j]]] ], {j, -1 + Length@\[Lambda]}]```
 ✕ `KStepPartitionQ[0, _] := {{0}}`
 ✕ ```KStepPartitions[n_, k_] := Select[IntegerPartitions@n, KStepPartitionQ[#, k] &]```
 ✕ `KStep[0, k_] := 1`
 ✕ `KStep[n_, k_] := KStep[n, k] = Length@KStepPartitions[n, k]`
 ✕ `CompletePartitionQ@p_ := KStepPartitionQ[p, 1]`
 ✕ `CompletePartitions[n_] := KStepPartitions[n, 1]`
 ✕ `Complete[n_] := KStep[n, 1]`
 ✕ `pre\[Gamma]@r_ := Table[KStep[i - 1, j - 1], {i, r}, {j, r}]`
 ✕ `\[Gamma]@r_ := PadRight@Table[KStep[i - j, j - 1], {i, r}, {j, i}]`
 ✕ `StrictCompositions[n_] := Join @@ Permutations /@ IntegerPartitions[n]`
 ✕ ```StrictCompositionsByMax[n_, m_] := Total[-(-1)^(Length /@ Select[StrictCompositions@n, Max@# == m &])]```
 ✕ `\[Sigma]@r_ := PadRight@Table[StrictCompositionsByMax[n, m], {n, r}, {m, n}]`
 ✕ `\[Alpha]@r_ := PadRight@Table[1, {i, r}, {j, i}]`
 ✕ `\[Chi]@r_ := PadRight@Table[If[Mod[n, k] == 0, MoebiusMu[n/k], 0], {n, r}, {k, n}]`

## Integer Partitions

### Definition of an Integer Partition

Let’s establish the definitions for a multiset and an integer partition:

• A multiset is a collection of elements (like a set) where an element can occur more than once (unlike a set).
• An integer partition of a positive integer is a multiset of positive integers (called its parts) that sum to . In math, we write .

For example, .

In Mathematica, we use a list:

 ✕ `{3, 1, 1} // Total`

Since the elements of a multiset and a set are unordered, we can arbitrarily choose to order the parts of a partition from largest to smallest. Here are the integer partitions of 5:

 ✕ `IntegerPartitions[5]`

Here they are again more compactly:

 ✕ `Row /@ IntegerPartitions@5`

### Other Definitions

An older alternative definition is along these lines: “A partition is a way of writing an integer n as a sum of positive integers where the order of the addends is not significant…. By convention, partitions are normally written from largest to smallest addends… for example, 10 = 3 + 2 + 2 + 2 + 1.”

With such a definition, 3 + 2 + 2 + 2 + 1 has to be frozen, because as an arithmetic expression it is 10 and the parts are gone.

Yet another definition: is a partition of if the finite sequence is such that and .

### Ferrers Diagram

For each part of a partition , draw a row of dots, then stack the rows:

 ✕ `Ferrers@{2, 1, 1}`

### Conjugate Partition

The conjugate partition of a partition is the partition corresponding to the transpose of the Ferrers diagram of :

 ✕ `Ferrers@ConjugatePartition@{2, 1, 1}`

So is the conjugate partition of , and vice versa.

### Distinct Partition

A distinct partition has no repeated part. Here are the four distinct partitions of 6:

 ✕ `Row /@ DistinctPartitions@6`

The remaining partitions of 6 have repeated parts:

 ✕ `Row /@ Complement[IntegerPartitions@6, DistinctPartitions@6]`

This is the sequence counting the number of distinct partitions of :

 ✕ `PartitionsQ@Range[20]`

## Generating Functions

### Number of Partitions

The number of partitions of is but the next number is not 13:

 ✕ `PartitionsP@Range[12]`

The generating function for this sequence is:

 ✕ `Row[{Sum[PartitionsP@n x^n, {n, 12}], " + \[Ellipsis]"}]`

The generating function is equal to the infinite product .

### Number of Distinct Partitions

The number of distinct partitions of :

 ✕ `PartitionsQ@Range[12]`

The generating function for this sequence is:

 ✕ `Row[{Sum[PartitionsQ@n x^n, {n, 12}], " + \[Ellipsis]"}]`

It is equal to the infinite product .

## Two Möbius Functions

### Square-Free Numbers

A square-free integer is one that is not divisible by a square greater than 1. Here are the square-free numbers up to 100:

 ✕ `Select[Range@100, SquareFreeQ]`

Here are numbers up to 100 that are not square free:

 ✕ `Select[Range@100, Not@*SquareFreeQ]`

### Möbius Function μ

In multiplicative number theory, the Möbius μ function is defined on the positive integers as follows:

1. If is not square free, .
2. If is square free, then can be written as the product of distinct primes, for some positive integer . In that case, .

In other words, of a square-free integer is or according to whether has an odd or an even number of prime factors. For example, , , .

### Möbius Partition Function μP

The function is the partition analogue of the ordinary Möbius function :

 ✕ ```Text@Grid[{ {"\[Mu]", "\!\(\*SubscriptBox[\(\[Mu]\), \(P\)]\)"}, {, }, {"product", "partition"}, {"primes factors", "parts"}, {"square\[Hyphen]free", "distinct"} }, Alignment -> Left, Dividers -> {{False, True}, {False, True}}]```

The definition of :

1. Let if the partition has a repeated part.
2. If the partition has distinct parts and parts in all, .

Here are the partitions of 6 and the corresponding values of the Möbius partition function :

 ✕ ```Grid[{Row@#, PartitionMu@#} & /@ IntegerPartitions@6, Alignment -> {Right, Left}]```

## Infinite Triangular Matrices

### Pascal’s Triangle

The prime example of an infinite lower-triangular matrix is Pascal’s triangle . Imagine that the rows keep going down and the columns keep going to the right. For readability, let’s replace 0s with dots:

 ✕ ```MatrixForm[t10 = Table[Binomial[n, k], {n, 0, 9}, {k, 0, 9}], TableAlignments -> Right] /. 0 -> "\[CenterDot]"```

Here is the matrix product :

 ✕ `MatrixForm[t10.t10, TableAlignments -> Right] /. 0 -> "\[CenterDot]"`

Here is the matrix inverse of :

 ✕ ```MatrixForm[Inverse@t10, TableAlignments -> Right] /. 0 -> "\[CenterDot]"```

### Stirling Numbers of the First and Second Kind

The Stirling numbers of the first and second kind are another example of a pair of inverse lower-triangular matrices.

A Stirling number of the first kind counts how many permutations of have cycles:

 ✕ ```(s1 = Table[StirlingS1[n, k], {n, 8}, {k, 8}]) /. 0 -> "\[CenterDot]" // MatrixForm```

A set partition of a finite set, say , is a set of disjoint nonempty subsets of .

A Stirling number of the second kind counts how many set partitions of have subsets:

 ✕ ```(s2 = Table[StirlingS2[n, k], {n, 8}, {k, 8}]) /. 0 -> "\[CenterDot]" // MatrixForm```

The two matrices are inverses of each other:

 ✕ ```Row[{MatrixForm@s1, Style[" \[CenterDot] ", 24], MatrixForm@s2, Style[" = ", 24], MatrixForm[s1.s2]}] /. 0 -> "\[CenterDot]"```

### Infinite Matrices Can Be Weird

For square matrices and , if , then . As the Demonstration The Derivative and the Integral as Infinite Matrices shows, there are (very familiar) infinite matrices and such that is the identity matrix, but .

Even though infinite lower-triangular matrices with 1s on the main diagonal behave well, we only deal with matrices, where .

## Matrix ν

### Definition of ν

Define the matrix by , where the sum is over and , .

Here is an alternative definition.

Let be the partitions of into an odd number of parts with maximum part .

Let be the same, except the number of parts should be even.

Let be the number of elements in .

Then , with .

Here is :

 ✕ `\[Nu]@10 /. 0 -> "\[CenterDot]" // MatrixForm`

To verify that , look at the partitions of 10:

 ✕ `Row /@ IntegerPartitions@10`

The ones with maximum part 5 are:

 ✕ `Select[IntegerPartitions@10, Max@# == 5 &]`

Applying to each of those gives:

 ✕ `PartitionMu /@ %`

Minus the sum is 2, so , as claimed.

### Inverse of ν

As Jacobi wrote, “Always invert!” (referring to elliptic integrals). This is :

 ✕ `Inverse[\[Nu]@15] /. 0 -> "\[CenterDot]" // MatrixForm`

What is the sequence in the second column, ?

You can find the sequence at the OEIS by looking it up. That hits A126796: Number of complete partitions of n, which is a great start in understanding the matrix !

## Matrix γ

### Subpartitions and Subsums of a Partition

For the matrix γ, let’s look at subpartitions and subsums of a partition. A subpartition of a partition is a submultiset of . For instance, is a subpartition of . A subsum is the sum of a subpartition. So there are eight ( subsums of corresponding to the eight subpartitions of :

 ✕ ```Text@Grid[ Transpose@{Prepend[Subsets@{3, 1, 1}, "subpartition"], Prepend[Total /@ Subsets@{3, 1, 1}, "subsum"]} ]```

### Complete Partition

Now let’s look at complete partitions. We define a partition to be complete if it has all possible subsums .

Here are the five complete partitions of 6:

 ✕ `Row /@ Select[IntegerPartitions@6, CompletePartitionQ]`

And here are the partitions of 6 that are not complete:

 ✕ `Row /@ Select[IntegerPartitions@6, Not@*CompletePartitionQ]`

This is the sequence counting the number of complete partitions of :

 ✕ `Complete /@ Range[0, 10]`

### Park’s Condition

Consider the partition 7311. We get the subsums 1, 2, 3, 4, 5 easily from 311. But we cannot get 6, so 7311 is not complete.

Qualitatively, if a part is too large relative to the other parts, we cannot get some intermediate subsums. Park’s condition makes this precise.

Theorem (Park): A partition with is complete iff and for each , , .

For example, is not complete (no subsum is 3) because .

Using Park’s condition, it is easy to check—but only if you want!—that the conjugate of a distinct partition is a complete partition.

### k-Step Partition

Given a non-negative integer , define a partition to be -step iff and for each , , . Define the empty partition to be the only zero-step partition.

Clearly, a one-step partition is a complete partition:

 ✕ `Row /@ CompletePartitions@5`

Here are the -step partitions of 5, for :

 ✕ `Row /@ KStepPartitions[5, 1]`
 ✕ `Row /@ KStepPartitions[5, 2]`
 ✕ `Row /@ KStepPartitions[5, 3]`
 ✕ `Row /@ KStepPartitions[5, 4]`

This is the same as the partitions of 5 with no restrictions:

 ✕ `Row /@ KStepPartitions[5, 5]`

### Matrix of Number of k-Step Partitions

Define to be the number of -step partitions of :

 ✕ `pre\[Gamma]@10 /. 0 -> "\[CenterDot]" // MatrixForm`

The second column is the number of complete partitions of is .

### Definition of γ

Define the matrix by , . In words, the columns of are the number of -step partitions shifted down to form a lower-triangular matrix.

Here is the matrix :

 ✕ `\[Gamma]@10 /. 0 -> "\[CenterDot]" // MatrixForm`

It matches the inverse of :

 ✕ `Inverse@\[Nu]@10 /. 0 -> "\[CenterDot]" // MatrixForm`

## Main Theorem

We can now put everything together. The inverse of the matrix matches the matrix , which is the main theorem for this blog.

Theorem. For each , , the identity matrix.

This presents the situation when :

 ✕ ```Row[{\[Nu]@6 /. 0 -> "\[CenterDot]" // MatrixForm, Style[" \[CenterDot] ", 16], \[Gamma]@6 /. 0 -> "\[CenterDot]" // MatrixForm, Style[" = ", 16], IdentityMatrix@6 /. 0 -> "\[CenterDot]" // MatrixForm}]```

### Paul Hanna’s Generating Function

Hanna conjectured that

,   (1)

where is the sequence that counts the number of complete partitions of .

Proof: Rewrite the desired identity as

(2)

or

,   (3)

where the last sum is over all complete partitions of .

We claim every partition contains a maximal complete subpartition. For example, has the maximal complete subpartition . If the maximal subpartition of partitions , then cannot be a part of the original partition . If it were, we could insert it into , contradicting its maximality.

Furthermore, there is no constraint on the parts in larger than because the fact that is missing in means that no larger complete subpartition can be produced. Hence generates all partitions whose maximal complete subpartition is a partition of .

Summing over all gives (3), and consequently (1).

Identifying coefficients for like powers of proves that , the second column of . The straightforward bookkeeping generalization then proves the main theorem for the other columns.

### Combinatorial Proof

Here is a proof of the main theorem by example. Consider the dot product of row 10 of with :

 ✕ ```Row[{MatrixForm@{Last[\[Nu]@10]}, " \[CenterDot] ", MatrixForm@\[Gamma][10][[All, 2]]}]```

An entry from is the difference between the number of distinct partitions of odd and even length. Here are these partitions:

 ✕ `Table[Row /@ DistinctPartitionsByMax[10, m], {m, 10}]`

Here are the complete partitions counted in the third column of :

 ✕ `MatrixForm@Join[{{}, {}}, Table[Row /@ CompletePartitions[i], {i, 6}]]`

Count them up and recall that the sequence for the number of complete partitions starts like this:

 ✕ `Complete /@ Range[6]`

Consider the fifth term in the dot product: 2×2. It comes from all possible pairs .

That is:

,

,

,

.

The signs of those pairs are all negative, because the four distinct partitions all have an odd number of parts. Using β, we will find four other terms in the dot product that have the opposite sign to get cancellation.

### Involution β

Let be the set of distinct partitions and be the set of complete partitions.

Define the function as follows.

Let and .

1. If is even, then .
2. If is odd, then .

In other words:

1. Add the second-largest part of to the first part and adjoin to .
2. Drop the largest part of from and in , subtract from the largest part and adjoin to .

In the previous example, we had four pairs. Here is how changes them:

,

,

,

.

The resulting pairs are still . However, the odd length becomes an even length, giving the cancellation. Also, reverses itself, so we get complete cancellation.

Formally, the function changes the parity of the length of the distinct partition and is an involution on the set of pairs. Therefore, the dot product is zero.

## Compositions

### Definition

A composition of is a finite sequence of non-negative integers with sum . So unlike an integer partition, order matters. For example, the two compositions and are different.

Allowing 0 as a part only make sense if the number of parts is specified.

### Strict Compositions

A strict composition of is a finite sequence of positive integers with sum . Here are the strict compositions of 4:

 ✕ `Row /@ (C4 = StrictCompositions@4)`

Let be the number of parts of the composition . Here are the lengths of the compositions just shown:

 ✕ `Length /@ C4`

### Matrix σ

As is for partitions, so is for strict compositions. Let’s define the matrix by , where , . The sum is over all strict compositions of with maximum part and is the number of parts of .

For example, for , , these are the strict compositions:

 ✕ `Row /@ Select[C4, Max@# == 2 &]`

Three have odd length and one has even length, so .

Just like the matrix before, we define the matrix by , :

 ✕ `\[Sigma]@10 /. 0 -> "\[CenterDot]" // Grid`

### Inverse of σ

Take the inverse of . What are these numbers?

 ✕ `Inverse[\[Sigma]@10] /. 0 -> "\[CenterDot]" // Grid`

Looking up the second column in the OEIS leads to A002321, which is enough to lead to a conjecture. To formulate it, we define two lower-triangular matrices and .

### Matrix α

Let be the lower-triangular matrix of all 1s:

 ✕ `\[Alpha]@10 /. 0 -> "\[CenterDot]" // Grid`

### Matrix χ

Define the lower-triangular matrix by   where :

 ✕ `\[Chi]@10 /. 0 -> "\[CenterDot]" // Grid`

### Conjecture

Let’s calculate the matrix product:

 ✕ `\[Alpha][10].\[Chi][10].\[Alpha][10] /. 0 -> "\[CenterDot]" // Grid`

That matrix product matches the inverse of :

 ✕ `Inverse[\[Sigma][10]] /. 0 -> "\[CenterDot]" // Grid`

This led me to conjecture that .

Who will prove it?

The relevant OEIS triangles are A134542, A134541, A000012 and A054525.

## Conclusion

It is remarkable that the two kinds of partitions should be connected so simply by matrix inversion. That strict compositions are related to the multiplicative Möbius function again via matrix inversion amazes me. Are there more such pairs in the universe of additive number theory?

## References

Andrews, G., G. Beck and B. Hopkins. “On a Conjecture of Hanna Connecting Distinct Part and
Complete Partitions
.” Annals of Combinatorics 24 (2020): 217–24.

Brown, J. L. “Note on Complete Sequences of Integers.” The American Mathematical Monthly 68,
no. 6 (1961): 557–60.

Hoggatt, V. E and C. H. King. “Problem E-1424.” The American Mathematical Monthly  67 (1960):
593.

MacMahon, P. A. Combinatory Analysis, vol. 1. Cambridge: Cambridge University Press,  1915.

OEIS Foundation Inc. (2019), The On-Line Encyclopedia of Integer Sequences, oeis.org.

Park, S. K. “Complete Partitions.” Fibonacci Quarterly 36, no. 4 (1998): 354–60.

Park, S. K. “The r-Complete Partitions.” Discrete Mathematics 183 (1998): 293–97.

Schneider, R. “Arithmetic of Partitions and the q-Bracket Operator.” Proceedings of the  American
Mathematical Society
145 (2017): 1953–68.