Boolean operations on Ferrers diagrams for partitions of integers.
Version of Thursday 11 April 2019.
Dave Barber's other pages.

Section 1. A major area of research in mathematics is the partitioning of integers. On its face, the task is simple: to write a positive integer as the sum of one or more (usually smaller) positive integers. However, the underlying theory quickly grows complicated.

To begin with an example, here is a listing of all the partitions of the number seven:

 ⟨ 7 ⟩ ⟨ 6, 1 ⟩ ⟨ 5, 2 ⟩ ⟨ 5, 1, 1 ⟩ ⟨ 4, 3 ⟩ ⟨ 4, 2, 1 ⟩ ⟨ 4, 1, 1, 1 ⟩ ⟨ 3, 3, 1 ⟩ ⟨ 3, 2, 2 ⟩ ⟨ 3, 2, 1, 1 ⟩ ⟨ 3, 1, 1, 1, 1 ⟩ ⟨ 2, 2, 2, 1 ⟩ ⟨ 2, 2, 1, 1, 1 ⟩ ⟨ 2, 1, 1, 1, 1, 1 ⟩ ⟨ 1, 1, 1, 1, 1, 1, 1 ⟩

For instance, ⟨ 4, 2, 1 ⟩ says that 4 + 2 + 1 = 7.

In this report, the addends are written in a comma-separated list between shallow angle brackets, which grouping symbols were chosen because they are rarely seen elsewhere in mathematics. Repeated numbers in a partition are significant, so a partition is not a set. The numbers may be written in any order, but the custom is to write them in non-increasing order.

The number seven happens to have 15 partitions, but there is no simple formula to determine how many partitions a number will have.

Section 2. There are many ways that partitions might be restricted, but two of them are especially well known. The first is to limit the maximum value of any addend. Here are the partitions of 7 with no addend greater than three:

 ⟨ 3, 3, 1 ⟩ ⟨ 3, 2, 2 ⟩ ⟨ 3, 2, 1, 1 ⟩ ⟨ 3, 1, 1, 1, 1 ⟩ ⟨ 2, 2, 2, 1 ⟩ ⟨ 2, 2, 1, 1, 1 ⟩ ⟨ 2, 1, 1, 1, 1, 1 ⟩ ⟨ 1, 1, 1, 1, 1, 1, 1 ⟩

The second way is to limit the number of addends in the partition. Here are the partitions of 7 that contain no more than 3 addends:

 ⟨ 7 ⟩ ⟨ 6, 1 ⟩ ⟨ 5, 2 ⟩ ⟨ 5, 1, 1 ⟩ ⟨ 4, 3 ⟩ ⟨ 4, 2, 1 ⟩ ⟨ 3, 3, 1 ⟩ ⟨ 3, 2, 2 ⟩

Section 3. Every partition generates a conjugate partition which can be found by constructing its Ferrers diagram. To give an example, in diagram 3:1 below left, each row has the number of stars corresponding to the ⟨ 7, 6, 4, 3, 1, 1 ⟩ partition of 22, while each column has the number of stars corresponding to the ⟨ 6, 4, 4, 3, 2, 2, 1 ⟩ partition. Hence these two partitions are conjugates.

Below right is shown the transpose of 3:1. For many purposes, there is no difference between a Ferrers diagram and its transpose. In any case, they contain the same information.

3:1
22  6  4  4   3  2  2  1
7
6
4
3
1
1
transpose of 3:1
22  7  6   4  3  1  1
6
4
4
3
2
2
1

In a Ferrers diagram, the terms of each of the two partitions are written in non-increasing order. As a result, the stars are said to be consolidated toward the top and left.

The Durfee square is the largest square that can be constructed among the stars in the Ferrers diagram. For the partitions above its size is 3, and it is emphasized below:

Durfee square of 3:1
22  6  4  4   3  2  2  1
7
6
4
3
1
1

The size of the Durfee square is equal to the number of stars on the diagram's principal diagonal.

A Durfee triangle can also be constructed. It is the largest right isoceles triangle that can be constructed among the stars in the Ferrers diagram. In this example its size is 5:

Durfee triangle of 3:1
22  6  4  4   3  2  2  1
7
6
4
3
1
1

Diagram 3:2 is an example where some stars of the Durfee square are not present in the Durfee triangle, and vice versa. Highlighted are the differences:

3:2
20  5  4  4   4  1  1  1
7✻B✻B✻B ✻B✻T✻N✻N
4✻B✻B✻B ✻B
4✻B✻B✻B ✻S
4✻B✻B✻S ✻S
1✻T
✻S = square only
✻T = triangle only
✻B = both
✻N = neither

Calculating the size of a Durfee square is almost trivial, but finding the size of a Durfee triangle requires more calculation, although not complicated.

It is possible for a partition to be self-conjugate, as ⟨ 6, 6, 3, 2, 2, 2 ⟩ below:

3:3
21  6  6   3  2  2  2
6
6
3
2
2
2

Every positive integer except 2 admits of at least one self-conjugate partition.

Here are the partitions of 7 arranged as conjugates:

 ⟨ 7 ⟩ ⇔ ⟨ 1, 1, 1, 1, 1, 1, 1 ⟩ ⟨ 6, 1 ⟩ ⇔ ⟨ 2, 1, 1, 1, 1, 1 ⟩ ⟨ 5, 2 ⟩ ⇔ ⟨ 2, 2, 1, 1, 1 ⟩ ⟨ 4, 3 ⟩ ⇔ ⟨ 2, 2, 2, 1 ⟩ ⟨ 5, 1, 1 ⟩ ⇔ ⟨ 3, 1, 1, 1, 1 ⟩ ⟨ 4, 2, 1 ⟩ ⇔ ⟨ 3, 2, 1, 1 ⟩ ⟨ 3, 3, 1 ⟩ ⇔ ⟨ 3, 2, 2 ⟩ ⟨ 4, 1, 1, 1 ⟩ ⇔ itself

Section 4. In the Ferrers diagram, every cell either has a star or it does not. This binary nature suggests introducing Boolean algebra; the implementation for partitions is straightforward.

4:1
18  5  4  4   2  1  1  1
7
4
3
3
1
4:2
22  7  6   3  3  2  1
6
5
4
2
2
2
1

Pad them with zeroes to make them the same size. Because the components of a partition are addends, zeroes are harmless.

18  5  4  4   2  1  1  1
7
4
3
3
1
0
0
22  7  6  3   3  2  1  0
6
5
4
2
2
2
1

The Boolean AND operation, applied in parallel to corresponding cells, yields this:

4:1 AND 4:2
16 5 =
min (5, 7)
4 =
min (4, 6)
3 =
min (4, 3)
2 =
min (2, 3)
1 =
min (1, 2)
1 =
min (1, 1)
0 =
min (1, 0)
6 = min (7, 6)
4 = min (4, 5)
3 = min (3, 4)
2 = min (3, 2)
1 = min (1, 2)
0 = min (0, 2)
0 = min (0, 1)

The Boolean OR operation is analogous:

4:1 OR 4:2
24 7 =
max (5, 7)
6 =
max (4, 6)
4 =
max (4, 3)
3 =
max (2, 3)
2 =
max (1, 2)
1 =
max (1, 1)
1 =
max (1, 0)
7 = max (7, 6)
5 = max (4, 5)
4 = max (3, 4)
3 = max (3, 2)
2 = max (1, 2)
2 = max (0, 2)
1 = max (0, 1)

Dropping any empty rows or columns, the results can be condensed thus:

4:1 AND 4:2
16  5  4   3  2  1  1
6
4
3
2
1
4:1 OR 4:2
24  7  6  4   3  2  1  1
7
5
4
3
2
2
1

The AND can be performed a little more efficiently if, before calculation takes place, the input diagrams are truncated to the same size:

4:1 truncated
17  5  4  4   2  1  1
6
4
3
3
1
4:2 truncated
19  5  5   3  3  2  1
6
5
4
2
2

Section 5. The binary AND and OR operations can be generalized into an AT_LEAST operation which can take any number of inputs. Incidentally, this works throughout Boolean algebra, not merely in the context of Ferrers diagrams. For an example, start with these four arbitrary partitions:

5:1
21  6  5  5   2  1  1  1
7
4
3
3
3
1
5:2
16  5  4   2  2  2  1
6
5
2
2
1
5:3
17   5  4  3  1   1  1  1  1
8
3
3
2
1
5:4
15  6  4  2  2  1
5
4
2
2
1
1

Now tally all the stars by position:

star counts
69   22  17  12  7   5  3  2  1
26 4444 4321
16 4443 1000
10 4420 0000
9 4410 0000
6 4110 0000
2 2000 0000

Of corresponding cells:

• AT_LEAST (1; 5:1, 5:2, 5:3, 5:4 has a star anywhere the tally contains at least a 1;
• AT_LEAST (2; 5:1, 5:2, 5:3, 5:4 has a star anywhere the tally contains at least a 2;
• AT_LEAST (3; 5:1, 5:2, 5:3, 5:4 has a star anywhere the tally contains at least a 3;
• AT_LEAST (4; 5:1, 5:2, 5:3, 5:4 has a star anywhere the tally contains at least a 4.

Ferrers diagrams for the results:

AT_LEAST (1; 5:1, 5:2, 5:3, 5:4)
23   6  5  5  2   2  1  1  1
8
5
3
3
3
1
AT_LEAST (2; 5:1, 5:2, 5:3, 5:4)
18  6  4  3   2  1  1  1
7
4
3
2
1
1
AT_LEAST (3; 5:1, 5:2, 5:3, 5:4)
15  5  4   2  2  1  1
6
4
2
2
1
AT_LEAST (4; 5:1, 5:2, 5:3, 5:4)
13  5  4  2  1  1
5
3
2
2
1

If the number supplied to AT_LEAST is 1, the operation is equivalent to Boolean OR. If the number is equal to the quantity of partitions, the operation is equivalent to AND. Notable is that supplying the number 2 with 3 partitions yields a majority operation, as does supplying the number n with 2n−1 partitions.

Section 6. With the ease of defining the binary AND and OR operations, one might expect to also find a unary Boolean NOT operation. However, uncertainty is introduced by the padding required for the OR operation and the truncation that occurs with the AND operation. For these examples, diagram 4:1 is recalled from section 4 above.

Version one:

4:1 originally
18  5  4  4   2  1  1  1
7
4
3
3
1
then negated
17  0  1  1   3  4  4  4
0
3
4
4
6
and reversed
17  4  4  4   3  1  1  0
6
4
4
3
0

Version two:

18  5  4  4   2  1  1  1
7
4
3
3
1
0
0
then negated
31  2  3  3   5  6  6  6
0
3
4
4
6
7
7
and reversed
31  6  6  6   5  3  3  2
7
7
6
4
4
3
0

Version three:

4:1 truncated for the
more efficient AND
17  5  4   4  2  1  1
6
4
3
3
1
then negated

13  0  1   1  3  4  4
0
2
3
3
5
and reversed

13  4  4   3  1  1  0
5
3
3
2
0

Reversal is employed to restore consolidation. Because a partition is a sum, and addition is commutative, there is no harm in re-ordering the rows, or the columns, of the diagram. (Of course, switching a row with a column will not work.)

Three different answers ensue. It is not at all clear which of these — or something else — ought to be considered "correct" negation. Padding is certainly necessary for the OR calculation, and truncation does not damage the result in the AND calculation, so the two resizing procedures ought never to be blithely dismissed as a mere "inconvenience" in efforts to define NOT.

Section 7. The Boolean XOR operation fares no better than NOT, possibly because it is difficult to devise an XOR in terms of AND and OR without using NOT. Given partitions 7:1 and 7:2, here is one of the many ways to define it:

7:1 XOR 7:2 = (7:1 AND NOT 7:2) OR (7:2 AND NOT 7:1)

Example:

7:1
28  6  6   4  4  4  4
6
6
6
6
2
2
7:2
27  6  6   6  5  2  2
6
6
4
4
4
3
7:1 XOR 7:2
7  0  0   2  1  2  2
0
0
2
2
2
1

It is not possible to re-order the rows, or the columns, of 7:1 XOR 7:2 to achieve consolidation, and that leaves the Ferrers diagram defective.

Similar comments apply to logical equality, which operation is the negative of XOR.

Section 8. There are no surprises in extending Ferrers diagrams to three dimensions. Because they are bulky to display, an extended example is given on another page.

Section 9. Fuzzy logic can also be applied to Ferrers diagrams. They, too, are on a separate page.