Essays, Posts & Presentations

An Intriguing Identity: Connecting Distinct and Complete Integer Partitions

George Beck

Author

George Beck

Title

An Intriguing Identity: Connecting Distinct and Complete Integer Partitions

Description

An investigation into the connection between distinct and complete integer partitions in the field of number theory. All Wolfram Language code is provided.

An Intriguing Identity: Connecting Distinct and Complete Integer Partitions

January 9, 2019

George Beck, Document & Media Systems

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:

7+3+3+1

. 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:

In[]:=

PartitionsP[14]

Out[]=

135

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.

In[]:=

Ferrers@p_:=Framed@Grid[Table["●",#]&/@p]

In[]:=

ConjugatePartition[l_List]:=Module[{i,r=Reverse[l],n=Length[l]},Table[n+1-Position[r,_?(#≥i&),Infinity,1][[1,1]],{i,l[[1]]}]]

In[]:=

DistinctPartitionQ@x_:=Length@xLength@Union@x

In[]:=

DistinctPartitions@n_:=Select[IntegerPartitions@n,DistinctPartitionQ]

In[]:=

PartitionMu@λ_:=If[DistinctPartitionQ@λ,(-1)^Length@λ,0]

In[]:=

DistinctPartitionsByMax[n_,m_]:=DistinctPartitionsByMax[n,m]=Select[IntegerPartitions@n,(Sort@#==Union@#)&&(Max@#m)&]

In[]:=

PartitionsMuByMax[n_,m_]:=PartitionsMuByMax[n,m]=Length@DistinctPartitionsByMax[n,m]-2Length@Select[DistinctPartitionsByMax[n,m],EvenQ@*Length]

In[]:=

PartitionsMuByMax@r_:=Table[PartitionsMuByMax[i,j],{i,r},{j,i}]

In[]:=

ν@r_:=PadRight@Table[PartitionsMuByMax[i,j],{i,r},{j,i}]

In[]:=

KStepPartitionQ[λ_,k_]:=MemberQ[Range@k,Last@λ]&&And@@Table[λ[[j]]-k≤Total@Drop[λ,First@Last@Position[λ,λ[[j]]]],{j,-1+Length@λ}]

In[]:=

KStepPartitionQ[0,_]:={{0}}

In[]:=

KStepPartitions[n_,k_]:=Select[IntegerPartitions@n,KStepPartitionQ[#,k]&]

In[]:=

KStep[0,k_]:=1

In[]:=

KStep[n_,k_]:=KStep[n,k]=Length@KStepPartitions[n,k]

In[]:=

CompletePartitionQ@p_:=KStepPartitionQ[p,1]

In[]:=

CompletePartitions[n_]:=KStepPartitions[n,1]

In[]:=

Complete[n_]:=KStep[n,1]

In[]:=

preγ@r_:=Table[KStep[i-1,j-1],{i,r},{j,r}]

In[]:=

γ@r_:=PadRight@Table[KStep[i-j,j-1],{i,r},{j,i}]

In[]:=

StrictCompositions[n_]:=Join@@Permutations/@IntegerPartitions[n]

In[]:=

StrictCompositionsByMax[n_,m_]:=Total[-(-1)^(Length/@Select[StrictCompositions@n,Max@#m&])]

In[]:=

σ@r_:=PadRight@Table[StrictCompositionsByMax[n,m],{n,r},{m,n}]

In[]:=

α@r_:=PadRight@Table[1,{i,r},{j,i}]

In[]:=

χ@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

λ=(

…λ

)⊢n

For example,

(3,1,1)⊢5

In Mathematica, we use a list:

In[]:=

{3,1,1}//Total

Out[]=

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:

In[]:=

IntegerPartitions[5]

Out[]=

{{5},{4,1},{3,2},{3,1,1},{2,2,1},{2,1,1,1},{1,1,1,1,1}}

Here they are again more compactly:

In[]:=

Row/@IntegerPartitions@5

Out[]=

{5,41,32,311,221,2111,11111}

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:

In[]:=

Ferrers@{2,1,1}

Out[]=

●	●
●
●

Conjugate Partition

The conjugate partition

λ'

of a partition

is the partition corresponding to the transpose of the Ferrers diagram of

In[]:=

Ferrers@ConjugatePartition@{2,1,1}

Out[]=

●	●	●
●

(3,1)

is the conjugate partition of

(2,1,1)

, and vice versa.

Distinct Partition

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

In[]:=

Row/@DistinctPartitions@6

Out[]=

{6,51,42,321}

The remaining partitions of 6 have repeated parts:

In[]:=

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

Out[]=

{33,222,411,2211,3111,21111,111111}

This is the sequence counting the number of distinct partitions of

In[]:=

PartitionsQ@Range[20]

Out[]=

{1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64}

Generating Functions

Number of Partitions

The number of partitions of

1,2,3,5,7,11,…

, but the next number is not 13:

In[]:=

PartitionsP@Range[12]

Out[]=

{1,2,3,5,7,11,15,22,30,42,56,77}

The generating function for this sequence

p(n)

is:

In[]:=

Row[{Sum[PartitionsP@nx^n,{n,12}]," + …"}]

Out[]=

x+2

+11

+15

+22

+30

+42

+56

+77

+ …

The generating function is equal to the infinite product

∞

∏

i=1

Number of Distinct Partitions

The number of distinct partitions of

In[]:=

PartitionsQ@Range[12]

Out[]=

{1,1,2,2,3,4,5,6,8,10,12,15}

The generating function for this sequence

q(n)

is:

In[]:=

Row[{Sum[PartitionsQ@nx^n,{n,12}]," + …"}]

Out[]=

+10

+12

+15

+ …

It is equal to the infinite product

∞

∏

i=1

(1+

)

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:

In[]:=

Select[Range@100,SquareFreeQ]

Out[]=

{1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,39,41,42,43,46,47,51,53,55,57,58,59,61,62,65,66,67,69,70,71,73,74,77,78,79,82,83,85,86,87,89,91,93,94,95,97}

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

In[]:=

Select[Range@100,Not@*SquareFreeQ]

Out[]=

{4,8,9,12,16,18,20,24,25,27,28,32,36,40,44,45,48,49,50,52,54,56,60,63,64,68,72,75,76,80,81,84,88,90,92,96,98,99,100}

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,

μ(n)=0

2. If

is square free, then

can be written as the product of

distinct primes, for some positive integer

. In that case,

μ(n)=

(-1)

In other words,

of a square-free integer is

-1

according to whether

has an odd or an even number of prime factors. For example,

μ(4)=0

μ(5)=-1

μ(6)=1

Möbius Partition Function
μ
P

The function

is the partition analogue of the ordinary Möbius function

In[]:=

Text@Grid[{{"μ","

"},{,},{"product","partition"},{"primes factors","parts"},{"square-free","distinct"}},AlignmentLeft,Dividers{{False,True},{False,True}}]

Out[]=

μ	μ P

product	partition
primes factors	parts
square-free	distinct

The definition of

1. Let

(λ)=0

if the partition

has a repeated part.

2. If the partition

has distinct parts and

parts in all,

(λ)=

(-1)

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

In[]:=

Grid[{Row@#,PartitionMu@#}&/@IntegerPartitions@6,Alignment{Right,Left}]

Out[]=

6	-1
51	1
42	1
411	0
33	0
321	-1
3111	0
222	0
2211	0
21111	0
111111	0

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:

In[]:=

MatrixForm[t10=Table[Binomial[n,k],{n,0,9},{k,0,9}],TableAlignmentsRight]/.0"·"

Out[]//MatrixForm=

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	2	1	·	·	·	·	·	·	·
1	3	3	1	·	·	·	·	·	·
1	4	6	4	1	·	·	·	·	·
1	5	10	10	5	1	·	·	·	·
1	6	15	20	15	6	1	·	·	·
1	7	21	35	35	21	7	1	·	·
1	8	28	56	70	56	28	8	1	·
1	9	36	84	126	126	84	36	9	1

Here is the matrix product

T·T

In[]:=

MatrixForm[t10.t10,TableAlignmentsRight]/.0"·"

Out[]//MatrixForm=

1	·	·	·	·	·	·	·	·	·
2	1	·	·	·	·	·	·	·	·
4	4	1	·	·	·	·	·	·	·
8	12	6	1	·	·	·	·	·	·
16	32	24	8	1	·	·	·	·	·
32	80	80	40	10	1	·	·	·	·
64	192	240	160	60	12	1	·	·	·
128	448	672	560	280	84	14	1	·	·
256	1024	1792	1792	1120	448	112	16	1	·
512	2304	4608	5376	4032	2016	672	144	18	1

Here is the matrix inverse of

In[]:=

MatrixForm[Inverse@t10,TableAlignmentsRight]/.0"·"

Out[]//MatrixForm=

1	·	·	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·	·	·
1	-2	1	·	·	·	·	·	·	·
-1	3	-3	1	·	·	·	·	·	·
1	-4	6	-4	1	·	·	·	·	·
-1	5	-10	10	-5	1	·	·	·	·
1	-6	15	-20	15	-6	1	·	·	·
-1	7	-21	35	-35	21	-7	1	·	·
1	-8	28	-56	70	-56	28	-8	1	·
-1	9	-36	84	-126	126	-84	36	-9	1

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

{1,2,…,n}

have

cycles:

In[]:=

(s1=Table[StirlingS1[n,k],{n,8},{k,8}])/.0"·"//MatrixForm

Out[]//MatrixForm=

1	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·
2	-3	1	·	·	·	·	·
-6	11	-6	1	·	·	·	·
24	-50	35	-10	1	·	·	·
-120	274	-225	85	-15	1	·	·
720	-1764	1624	-735	175	-21	1	·
-5040	13068	-13132	6769	-1960	322	-28	1

A set partition of a finite set, say

T={1,2,3,…,n}

, is a set of disjoint nonempty subsets of

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

{1,2,…,n}

have

subsets:

In[]:=

(s2=Table[StirlingS2[n,k],{n,8},{k,8}])/.0"·"//MatrixForm

Out[]//MatrixForm=

1	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·
1	3	1	·	·	·	·	·
1	7	6	1	·	·	·	·
1	15	25	10	1	·	·	·
1	31	90	65	15	1	·	·
1	63	301	350	140	21	1	·
1	127	966	1701	1050	266	28	1

The two matrices are inverses of each other:

In[]:=

Row[{MatrixForm@s1,Style[" · ",24],MatrixForm@s2,Style[" = ",24],MatrixForm[s1.s2]}]/.0->"·"

Out[]=

1	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·
2	-3	1	·	·	·	·	·
-6	11	-6	1	·	·	·	·
24	-50	35	-10	1	·	·	·
-120	274	-225	85	-15	1	·	·
720	-1764	1624	-735	175	-21	1	·
-5040	13068	-13132	6769	-1960	322	-28	1

1	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·
1	3	1	·	·	·	·	·
1	7	6	1	·	·	·	·
1	15	25	10	1	·	·	·
1	31	90	65	15	1	·	·
1	63	301	350	140	21	1	·
1	127	966	1701	1050	266	28	1

1	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·
·	·	1	·	·	·	·	·
·	·	·	1	·	·	·	·
·	·	·	·	1	·	·	·
·	·	·	·	·	1	·	·
·	·	·	·	·	·	1	·
·	·	·	·	·	·	·	1

Infinite Matrices Can Be Weird

For square matrices

and

, if

A·B=I

, then

B·A=I

. 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

r×r

matrices, where

r∈



Matrix
ν

Definition of
ν

Define the

r×r

matrix

(n,p)=-∑

(λ)

, where the sum is over

λ⊢n

and

max(λ)=p

1≤n,p≤r

Here is an alternative definition.

Let



odd,n,p

be the partitions of

into an odd number of parts with maximum part

Let



even,n,p

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

Let

#(X)

be the number of elements in

Then

(n,p)=#



odd,n,p

-#(



even,n,p

)

, with

1≤n,p≤r

Here is

In[]:=

ν@10/.0"·"//MatrixForm

Out[]//MatrixForm=

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	-1	1	·	·	·	·	·	·	·
·	·	-1	1	·	·	·	·	·	·
·	·	-1	-1	1	·	·	·	·	·
·	·	1	-1	-1	1	·	·	·	·
·	·	·	·	-1	-1	1	·	·	·
·	·	·	1	·	-1	-1	1	·	·
·	·	·	1	·	·	-1	-1	1	·
·	·	·	-1	2	·	·	-1	-1	1

To verify that

(10,5)=2

, look at the partitions of 10:

In[]:=

Row/@IntegerPartitions@10

Out[]=

{10,91,82,811,73,721,7111,64,631,622,6211,61111,55,541,532,5311,5221,52111,511111,442,4411,433,4321,43111,4222,42211,421111,4111111,3331,3322,33211,331111,32221,322111,3211111,31111111,22222,222211,2221111,22111111,211111111,1111111111}

The ones with maximum part 5 are:

In[]:=

Select[IntegerPartitions@10,Max@#5&]

Out[]=

{{5,5},{5,4,1},{5,3,2},{5,3,1,1},{5,2,2,1},{5,2,1,1,1},{5,1,1,1,1,1}}

Applying

to each of those gives:

In[]:=

PartitionMu/@%

Out[]=

{0,-1,-1,0,0,0,0}

Minus the sum is 2, so

(10,5)=2

, as claimed.

Inverse of
ν

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

-1

In[]:=

Inverse[ν@15]/.0"·"//MatrixForm

Out[]//MatrixForm=

1	·	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·	·	·	·	·	·
·	4	4	3	2	1	1	·	·	·	·	·	·	·	·
·	5	5	4	3	2	1	1	·	·	·	·	·	·	·
·	8	8	6	5	3	2	1	1	·	·	·	·	·	·
·	10	10	9	6	5	3	2	1	1	·	·	·	·	·
·	16	16	13	10	7	5	3	2	1	1	·	·	·	·
·	20	20	17	13	10	7	5	3	2	1	1	·	·	·
·	31	31	25	20	14	11	7	5	3	2	1	1	·	·
·	39	39	33	26	20	14	11	7	5	3	2	1	1	·
·	55	55	46	37	28	21	15	11	7	5	3	2	1	1

What is the sequence in the second column,

1,1,1,2,2,4,5,8,10,16,20,…

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,

(3,1)

is a subpartition of

(3,1,1)

. A subsum is the sum of a subpartition. So there are eight (

)

subsums of

(3,1,1)

corresponding to the eight subpartitions of

(3,1,1}

In[]:=

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

Out[]=

subpartition	subsum
{}	0
{3}	3
{1}	1
{1}	1
{3,1}	4
{3,1}	4
{1,1}	2
{3,1,1}	5

Complete Partition

Now let’s look at complete partitions. We define a partition

λ⊢n

to be complete if it has all possible subsums

1,2,3,…,n

Here are the five complete partitions of 6:

In[]:=

Row/@Select[IntegerPartitions@6,CompletePartitionQ]

Out[]=

{321,3111,2211,21111,111111}

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

In[]:=

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

Out[]=

{6,51,42,411,33,222}

This is the sequence counting the number

c(n)

of complete partitions of

In[]:=

Complete/@Range[0,10]

Out[]=

{1,1,1,2,2,4,5,8,10,16,20}

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

1≤j<m

≤1+

j+1

j+2

+…+

For example,

411

is not complete (no subsum is 3) because

4≰1+(1+1)

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

≤k

and for each

0≤j≤m

≤k+

j+1

j+2

+…+

Define the empty partition to be the only zero-step partition.

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

In[]:=

Row/@CompletePartitions@5

Out[]=

{311,221,2111,11111}

Here are the

-step partitions of 5, for

k=1,2,3,4,5

In[]:=

Row/@KStepPartitions[5,1]

Out[]=

{311,221,2111,11111}

In[]:=

Row/@KStepPartitions[5,2]

Out[]=

{32,311,221,2111,11111}

In[]:=

Row/@KStepPartitions[5,3]

Out[]=

{41,32,311,221,2111,11111}

In[]:=

Row/@KStepPartitions[5,4]

Out[]=

{41,32,311,221,2111,11111}

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

In[]:=

Row/@KStepPartitions[5,5]

Out[]=

{5,41,32,311,221,2111,11111}

Matrix of Number of
k
-Step Partitions

Define

l(n,k)

to be the number of

-step partitions of

In[]:=

preγ@10/.0"·"//MatrixForm

Out[]//MatrixForm=

1	1	1	1	1	1	1	1	1	1
·	1	1	1	1	1	1	1	1	1
·	1	2	2	2	2	2	2	2	2
·	2	2	3	3	3	3	3	3	3
·	2	4	4	5	5	5	5	5	5
·	4	5	6	6	7	7	7	7	7
·	5	8	9	10	10	11	11	11	11
·	8	10	13	13	14	14	15	15	15
·	10	16	17	20	20	21	21	22	22
·	16	20	25	26	28	28	29	29	30

The second column is the number of complete partitions of

—that is,

c(n)=l(n,2)

Definition of
γ

Define the matrix

γ(i,j)=l(i-j,j-1)

i≤i,j≤r

. In words, the columns of

are the number of

-step partitions shifted down to form a lower-triangular matrix.

Here is the matrix

In[]:=

γ@10/.0"·"//MatrixForm

Out[]//MatrixForm=

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

It matches the inverse of

In[]:=

Inverse@ν@10/.0"·"//MatrixForm

Out[]//MatrixForm=

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

Main Theorem

-1
ν
=γ

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

r≥1

, the identity matrix.

This presents the situation when

r=6

In[]:=

Row[{ν@6/.0"·"//MatrixForm,Style[" · ",16],γ@6/.0"·"//MatrixForm,Style[" = ",16],IdentityMatrix@6/.0"·"//MatrixForm}]

Out[]=

1	·	·	·	·	·
·	1	·	·	·	·
·	-1	1	·	·	·
·	·	-1	1	·	·
·	·	-1	-1	1	·
·	·	1	-1	-1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	1	1	·	·	·
·	1	1	1	·	·
·	2	2	1	1	·
·	2	2	2	1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	·	1	·	·	·
·	·	·	1	·	·
·	·	·	·	1	·
·	·	·	·	·	1

Paul Hanna’s Generating Function

Hanna conjectured that

∞

∑

n=0

c(n)

(1-q)1-

…1-

n+1



, (1)

where

c(n)

is the sequence that counts the number of complete partitions of

Proof: Rewrite the desired identity as

∞

∏

n=1

(1-

)

∞

∑

n=0

c(n)

1-

n+1

1-

n+2

1-

n+3

…

(2)

∞

∑

n=1

p(n)

∞

∑

n=0

∑

1-

n+1

1-

n+2

1-

n+3

…

, (3)

where the last sum is over all complete partitions

We claim every partition contains a maximal complete subpartition. For example,

(9,7,3,1,1)

has the maximal complete subpartition

(3,1,1)

. If the maximal subpartition

π'

partitions

, then

n+1

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

n+1

because the fact that

n+1

is missing in

means that no larger complete subpartition can be produced. Hence

∑

∞

∏

j=n+2

1-



c(n)

∞

∏

j=n+2

1-



generates all partitions whose maximal complete subpartition is a partition of

Summing over all

n≥0

gives (3), and consequently (1).

Identifying coefficients for like powers of

proves that

ν·c=(1,0,0,0,…)

, the second column of

. The straightforward bookkeeping generalization

∞

∑

n=0

l(n,k)

(1-q)1-

…1-

n+k



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

In[]:=

Row[{MatrixForm@{Last[ν@10]}," · ",MatrixForm@γ[10][[All,2]]}]

Out[]=

(

-1

) ·

0
1
1
1
2
2
4
5
8
10

An entry from

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

In[]:=

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

Out[]=

{{},{},{},{4321},{541,532},{64,631},{73,721},{82},{91},{10}}

Here are the complete partitions counted in the third column of

In[]:=

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

Out[]//MatrixForm=

{}

{1}

{11}

{21,111}

{211,1111}

{311,221,2111,11111}

{321,3111,2211,21111,111111}

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

In[]:=

Complete/@Range[6]

Out[]=

{1,1,2,2,4,5}

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

{541,532}{{21,111}}

That is:

{541,21}

{541,111}

{532,21}

{532,111}

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

d=(

,…,

)∈

and

c=(

…)∈

1. If

is even, then

β(d,c)=((

,…,

),(

…))

2. If

is odd, then

β(d,c)=((

,…,

),(

,…))

In other words:

1. Add the second-largest part

to the first part

and adjoin

2. Drop the largest part

from

and in

, subtract

from the largest part

and adjoin

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

changes them:

β(541,21)=(91,421)

β(541,111)=(91,4111)

β(532,21)=(82,321)

β(532,111)=(82,3111)

The resulting pairs are still

(distinct,complete)

. 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

(1,0,2)

and

(1,2,0)

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:

In[]:=

Row/@(C4=StrictCompositions@4)

Out[]=

{4,31,13,22,211,121,112,1111}

Let

L(s)

be the number of parts of the composition

. Here are the lengths of the compositions just shown:

In[]:=

Length/@C4

Out[]=

{1,2,2,2,3,3,3,4}

Matrix
σ

is for partitions, so is

for strict compositions. Let’s define the

r×r

matrix

σ(n,m)=-

#(s)

(-1)

, where

1≤n≤r

1≤m≤r

. The sum is over all strict compositions

with maximum part

, and

#(s)

is the number of parts of

For example, for

n=4

m=2

, these are the strict compositions:

In[]:=

Row/@Select[C4,Max@#2&]

Out[]=

{22,211,121,112}

Three have odd length and one has even length, so

σ(4,2)=3-1=2

Just like the matrix

before, we define the

r×r

matrix

σ(n,m)

1≤n,m≤r

In[]:=

σ@10/.0"·"//Grid

Out[]=

1	·	·	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·	·	·
1	-2	1	·	·	·	·	·	·	·
-1	2	-2	1	·	·	·	·	·	·
1	-1	1	-2	1	·	·	·	·	·
-1	·	1	1	-2	1	·	·	·	·
1	·	-1	·	1	-2	1	·	·	·
-1	1	-1	1	·	1	-2	1	·	·
1	-2	2	-1	·	·	1	-2	1	·
-1	2	-1	-1	1	·	·	1	-2	1

Inverse of
σ

Take the inverse of

. What are these numbers?

In[]:=

Inverse[σ@10]/.0"·"//Grid

Out[]=

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	2	1	·	·	·	·	·	·	·
1	2	2	1	·	·	·	·	·	·
1	3	3	2	1	·	·	·	·	·
1	2	3	3	2	1	·	·	·	·
1	3	4	4	3	2	1	·	·	·
1	3	4	4	4	3	2	1	·	·
1	3	4	5	5	4	3	2	1	·
1	2	4	5	5	5	4	3	2	1

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:

In[]:=

α@10/.0"·"//Grid

Out[]=

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	1	1	·	·	·	·	·	·	·
1	1	1	1	·	·	·	·	·	·
1	1	1	1	1	·	·	·	·	·
1	1	1	1	1	1	·	·	·	·
1	1	1	1	1	1	1	·	·	·
1	1	1	1	1	1	1	1	·	·
1	1	1	1	1	1	1	1	1	·
1	1	1	1	1	1	1	1	1	1

Matrix χ

Define the lower-triangular matrix

χ(n,k)=

ifkn

0otherwise

where

1≤k≤n

In[]:=

χ@10/.0"·"//Grid

Out[]=

1	·	·	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·	·	·
-1	·	1	·	·	·	·	·	·	·
·	-1	·	1	·	·	·	·	·	·
-1	·	·	·	1	·	·	·	·	·
1	-1	-1	·	·	1	·	·	·	·
-1	·	·	·	·	·	1	·	·	·
·	·	·	-1	·	·	·	1	·	·
·	·	-1	·	·	·	·	·	1	·
1	-1	·	·	-1	·	·	·	·	1

Conjecture

Let’s calculate the matrix product:

In[]:=

α[10].χ[10].α[10]/.0"·"//Grid

Out[]=

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	2	1	·	·	·	·	·	·	·
1	2	2	1	·	·	·	·	·	·
1	3	3	2	1	·	·	·	·	·
1	2	3	3	2	1	·	·	·	·
1	3	4	4	3	2	1	·	·	·
1	3	4	4	4	3	2	1	·	·
1	3	4	5	5	4	3	2	1	·
1	2	4	5	5	5	4	3	2	1

That matrix product matches the inverse of

In[]:=

Inverse[σ[10]]/.0"·"//Grid

Out[]=

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	2	1	·	·	·	·	·	·	·
1	2	2	1	·	·	·	·	·	·
1	3	3	2	1	·	·	·	·	·
1	2	3	3	2	1	·	·	·	·
1	3	4	4	3	2	1	·	·	·
1	3	4	4	4	3	2	1	·	·
1	3	4	5	5	4	3	2	1	·
1	2	4	5	5	5	4	3	2	1

This led me to conjecture that

-1

=α·χ·α

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, forthcoming.

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.

Cite this as: George Beck, "An Intriguing Identity: Connecting Distinct and Complete Integer Partitions" from the Notebook Archive (2019), https://notebookarchive.org/2020-01-46d1x43

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	2	1	·	·	·	·	·	·	·
1	3	3	1	·	·	·	·	·	·
1	4	6	4	1	·	·	·	·	·
1	5	10	10	5	1	·	·	·	·
1	6	15	20	15	6	1	·	·	·
1	7	21	35	35	21	7	1	·	·
1	8	28	56	70	56	28	8	1	·
1	9	36	84	126	126	84	36	9	1

1	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·
·	·	1	·	·	·	·	·
·	·	·	1	·	·	·	·
·	·	·	·	1	·	·	·
·	·	·	·	·	1	·	·
·	·	·	·	·	·	1	·
·	·	·	·	·	·	·	1

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	-1	1	·	·	·	·	·	·	·
·	·	-1	1	·	·	·	·	·	·
·	·	-1	-1	1	·	·	·	·	·
·	·	1	-1	-1	1	·	·	·	·
·	·	·	·	-1	-1	1	·	·	·
·	·	·	1	·	-1	-1	1	·	·
·	·	·	1	·	·	-1	-1	1	·
·	·	·	-1	2	·	·	-1	-1	1

1	·	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·	·	·	·	·	·
·	4	4	3	2	1	1	·	·	·	·	·	·	·	·
·	5	5	4	3	2	1	1	·	·	·	·	·	·	·
·	8	8	6	5	3	2	1	1	·	·	·	·	·	·
·	10	10	9	6	5	3	2	1	1	·	·	·	·	·
·	16	16	13	10	7	5	3	2	1	1	·	·	·	·
·	20	20	17	13	10	7	5	3	2	1	1	·	·	·
·	31	31	25	20	14	11	7	5	3	2	1	1	·	·
·	39	39	33	26	20	14	11	7	5	3	2	1	1	·
·	55	55	46	37	28	21	15	11	7	5	3	2	1	1

1	1	1	1	1	1	1	1	1	1
·	1	1	1	1	1	1	1	1	1
·	1	2	2	2	2	2	2	2	2
·	2	2	3	3	3	3	3	3	3
·	2	4	4	5	5	5	5	5	5
·	4	5	6	6	7	7	7	7	7
·	5	8	9	10	10	11	11	11	11
·	8	10	13	13	14	14	15	15	15
·	10	16	17	20	20	21	21	22	22
·	16	20	25	26	28	28	29	29	30

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	-1	1	·	·	·
·	·	-1	1	·	·
·	·	-1	-1	1	·
·	·	1	-1	-1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	·	1	·	·	·
·	·	·	1	·	·
·	·	·	·	1	·
·	·	·	·	·	1

1	·	·	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·	·	·
1	-2	1	·	·	·	·	·	·	·
-1	2	-2	1	·	·	·	·	·	·
1	-1	1	-2	1	·	·	·	·	·
-1	·	1	1	-2	1	·	·	·	·
1	·	-1	·	1	-2	1	·	·	·
-1	1	-1	1	·	1	-2	1	·	·
1	-2	2	-1	·	·	1	-2	1	·
-1	2	-1	-1	1	·	·	1	-2	1

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	2	1	·	·	·	·	·	·	·
1	3	3	1	·	·	·	·	·	·
1	4	6	4	1	·	·	·	·	·
1	5	10	10	5	1	·	·	·	·
1	6	15	20	15	6	1	·	·	·
1	7	21	35	35	21	7	1	·	·
1	8	28	56	70	56	28	8	1	·
1	9	36	84	126	126	84	36	9	1

1	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·
·	·	1	·	·	·	·	·
·	·	·	1	·	·	·	·
·	·	·	·	1	·	·	·
·	·	·	·	·	1	·	·
·	·	·	·	·	·	1	·
·	·	·	·	·	·	·	1

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	-1	1	·	·	·	·	·	·	·
·	·	-1	1	·	·	·	·	·	·
·	·	-1	-1	1	·	·	·	·	·
·	·	1	-1	-1	1	·	·	·	·
·	·	·	·	-1	-1	1	·	·	·
·	·	·	1	·	-1	-1	1	·	·
·	·	·	1	·	·	-1	-1	1	·
·	·	·	-1	2	·	·	-1	-1	1

1	·	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·	·	·	·	·	·
·	4	4	3	2	1	1	·	·	·	·	·	·	·	·
·	5	5	4	3	2	1	1	·	·	·	·	·	·	·
·	8	8	6	5	3	2	1	1	·	·	·	·	·	·
·	10	10	9	6	5	3	2	1	1	·	·	·	·	·
·	16	16	13	10	7	5	3	2	1	1	·	·	·	·
·	20	20	17	13	10	7	5	3	2	1	1	·	·	·
·	31	31	25	20	14	11	7	5	3	2	1	1	·	·
·	39	39	33	26	20	14	11	7	5	3	2	1	1	·
·	55	55	46	37	28	21	15	11	7	5	3	2	1	1

1	1	1	1	1	1	1	1	1	1
·	1	1	1	1	1	1	1	1	1
·	1	2	2	2	2	2	2	2	2
·	2	2	3	3	3	3	3	3	3
·	2	4	4	5	5	5	5	5	5
·	4	5	6	6	7	7	7	7	7
·	5	8	9	10	10	11	11	11	11
·	8	10	13	13	14	14	15	15	15
·	10	16	17	20	20	21	21	22	22
·	16	20	25	26	28	28	29	29	30

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	-1	1	·	·	·
·	·	-1	1	·	·
·	·	-1	-1	1	·
·	·	1	-1	-1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	·	1	·	·	·
·	·	·	1	·	·
·	·	·	·	1	·
·	·	·	·	·	1

1	·	·	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·	·	·
1	-2	1	·	·	·	·	·	·	·
-1	2	-2	1	·	·	·	·	·	·
1	-1	1	-2	1	·	·	·	·	·
-1	·	1	1	-2	1	·	·	·	·
1	·	-1	·	1	-2	1	·	·	·
-1	1	-1	1	·	1	-2	1	·	·
1	-2	2	-1	·	·	1	-2	1	·
-1	2	-1	-1	1	·	·	1	-2	1

An Intriguing Identity: Connecting Distinct and Complete Integer Partitions

Wolfram Language Definitions

Integer Partitions

Definition of an Integer Partition

Other Definitions

Ferrers Diagram

Conjugate Partition

Distinct Partition

Generating Functions

Number of Partitions

Number of Distinct Partitions

Two Möbius Functions

Square-Free Numbers

Möbius Function μ

Möbius Partition Function μP

Infinite Triangular Matrices

Pascal’s Triangle

Stirling Numbers of the First and Second Kind

Infinite Matrices Can Be Weird

Matrix ν

Definition of ν

Inverse of ν

Matrix γ

Subpartitions and Subsums of a Partition

Complete Partition

Park’s Condition

k-Step Partition

Matrix of Number of k-Step Partitions

Definition of γ

Main Theorem

-1ν=γ

Paul Hanna’s Generating Function

Combinatorial Proof

Involution β

Compositions

Definition

Strict Compositions

Matrix σ

Inverse of σ

Matrix α

Matrix χ

Conjecture

Conclusion

References

Möbius Function
μ

Möbius Partition Function
μ
P

Matrix
ν

Definition of
ν

Inverse of
ν

Matrix
γ

Matrix of Number of
k
-Step Partitions

Definition of
γ

-1
ν
=γ

Involution
β

Matrix
σ

Inverse of
σ

1	·	·	·	·	·	·	·	·	·
1	1	·	·	·	·	·	·	·	·
1	2	1	·	·	·	·	·	·	·
1	3	3	1	·	·	·	·	·	·
1	4	6	4	1	·	·	·	·	·
1	5	10	10	5	1	·	·	·	·
1	6	15	20	15	6	1	·	·	·
1	7	21	35	35	21	7	1	·	·
1	8	28	56	70	56	28	8	1	·
1	9	36	84	126	126	84	36	9	1

1	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·
·	·	1	·	·	·	·	·
·	·	·	1	·	·	·	·
·	·	·	·	1	·	·	·
·	·	·	·	·	1	·	·
·	·	·	·	·	·	1	·
·	·	·	·	·	·	·	1

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	-1	1	·	·	·	·	·	·	·
·	·	-1	1	·	·	·	·	·	·
·	·	-1	-1	1	·	·	·	·	·
·	·	1	-1	-1	1	·	·	·	·
·	·	·	·	-1	-1	1	·	·	·
·	·	·	1	·	-1	-1	1	·	·
·	·	·	1	·	·	-1	-1	1	·
·	·	·	-1	2	·	·	-1	-1	1

1	·	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·	·	·	·	·	·
·	4	4	3	2	1	1	·	·	·	·	·	·	·	·
·	5	5	4	3	2	1	1	·	·	·	·	·	·	·
·	8	8	6	5	3	2	1	1	·	·	·	·	·	·
·	10	10	9	6	5	3	2	1	1	·	·	·	·	·
·	16	16	13	10	7	5	3	2	1	1	·	·	·	·
·	20	20	17	13	10	7	5	3	2	1	1	·	·	·
·	31	31	25	20	14	11	7	5	3	2	1	1	·	·
·	39	39	33	26	20	14	11	7	5	3	2	1	1	·
·	55	55	46	37	28	21	15	11	7	5	3	2	1	1

1	1	1	1	1	1	1	1	1	1
·	1	1	1	1	1	1	1	1	1
·	1	2	2	2	2	2	2	2	2
·	2	2	3	3	3	3	3	3	3
·	2	4	4	5	5	5	5	5	5
·	4	5	6	6	7	7	7	7	7
·	5	8	9	10	10	11	11	11	11
·	8	10	13	13	14	14	15	15	15
·	10	16	17	20	20	21	21	22	22
·	16	20	25	26	28	28	29	29	30

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

1	·	·	·	·	·	·	·	·	·
·	1	·	·	·	·	·	·	·	·
·	1	1	·	·	·	·	·	·	·
·	1	1	1	·	·	·	·	·	·
·	2	2	1	1	·	·	·	·	·
·	2	2	2	1	1	·	·	·	·
·	4	4	3	2	1	1	·	·	·
·	5	5	4	3	2	1	1	·	·
·	8	8	6	5	3	2	1	1	·
·	10	10	9	6	5	3	2	1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	-1	1	·	·	·
·	·	-1	1	·	·
·	·	-1	-1	1	·
·	·	1	-1	-1	1

1	·	·	·	·	·
·	1	·	·	·	·
·	·	1	·	·	·
·	·	·	1	·	·
·	·	·	·	1	·
·	·	·	·	·	1

1	·	·	·	·	·	·	·	·	·
-1	1	·	·	·	·	·	·	·	·
1	-2	1	·	·	·	·	·	·	·
-1	2	-2	1	·	·	·	·	·	·
1	-1	1	-2	1	·	·	·	·	·
-1	·	1	1	-2	1	·	·	·	·
1	·	-1	·	1	-2	1	·	·	·
-1	1	-1	1	·	1	-2	1	·	·
1	-2	2	-1	·	·	1	-2	1	·
-1	2	-1	-1	1	·	·	1	-2	1