# Partitions of b^n Found in Special Lower Triangular Matrices

Paul D Hanna pauldhanna at juno.com
Wed Nov 27 05:50:32 CET 2002

```   Consider the set of lower triangular matrices that satisfy
the peculiar exponential property:
M^b = M excluding the first row and column;
then by construction,
M^(b^n) = M excluding the first n rows and n columns,
where integer b>1 and the first column and main diagonal consist of all
1's.

These matrices are interesting in themselves, but there may be other
relations hidden in them, as the following conjecture would indicate.

Conjecture:
The sum of the n-th row of the above matrix M is equal to
the partitions of b^n into powers of b.

Can anyone prove this?  If true, it would be remarkable.
Listed here are some examples at b=2 and b=3.

(b=2)  Sequence A002577 (pasted below) lists the "Partitions of 2^n
into powers of 2".
Benoit Cloitre pointed out to me that it appears that this sequence
A002577 forms the sums of the rows of the lower triangular matrix M,
b=2, (A078121 - pasted below), which satisfies:
M^2 = M excluding first row and column.

Benoit also prompted me to look for a similar occurrence for b=3 and
the
partitions of 3^n into powers of 3; it seems that Benoit's hunch was
right.

(b=3)  It appears that the sequence A078125 (pasted below) is equal to
the "partitions of 3^n into powers of 3" (Not in EIS), which begin
1,2,5,23,239,... as in
a(0)=1: {1},
a(1)=2: {3; 1+1+1},
a(2)=5: {9; 3+3+3; 3+3+1+1+1; 3+1+1+1+1+1+1; 1+1+1+1+1+1+1+1+1},
...
Of course, these are the coefficients of x^(3^n) in the power series
expansion of 1/[(1-x)(1-x^3)(1-x^9)...(1-x^(3^k))...].

And the sequence A078125 is the sum of the rows of the lower
triangular matrix M, b=3, (A078122 - pasted below), which satisfies:
M^3 = M excluding first row and column.

Could someone verify that the sequence A078125 is indeed equal to
the partitions of 3^n into powers of 3?

Thanks,
Paul D Hanna (pauldhanna at juno.com)
-------------------------------------------------------------------

ID Number: A078121
Sequence:  1,1,1,1,2,1,1,4,4,1,1,10,16,8,1,1,36,84,64,16,1,1,202,656,
680,256,32,1,1,1828,8148,10816,5456,1024,64,1,1,27338,
167568,274856,174336,43680,4096,128,1,1,692004,5866452,
11622976,8909648,2794496,349504
Name:      Infinite lower triangular matrix, M, that satisfies
[M^2](i,j) = M(i+1,j+1) for all i,j>=0
where [M^n](i,j) denotes the element at row i, column j,
of the n-th power of matrix M, with M(0,k)=1 and M(k,k)=1
for all k>=0.
Comments:  M also satisfies: [M^(2k)](i,j) = [M^k](i+1,j+1) for all
i,j,k>=0; thus [M^(2^n)](i,j) = M(i+n,j+n) for all n>=0.
Example:   The square of the matrix is the same matrix excluding the
first row and column:
[1,_0,_0,0,0]^2=[_1,_0,_0,_0,0]
[1,_1,_0,0,0]___[_2,_1,_0,_0,0]
[1,_2,_1,0,0]___[_4,_4,_1,_0,0]
[1,_4,_4,1,0]___[10,16,_8,_1,0]
[1,10,16,8,1]___[36,84,64,16,1]
-------------------------------------------------------------------

ID Number: A002577 (Formerly M1239 and N0473)
Sequence:  1,2,4,10,36,202,1828,27338,692004,30251722,2320518948,
316359580362,77477180493604,34394869942983370,
27893897106768940836,41603705003444309596874,
114788185359199234852802340,588880400923055731115178072778
Name:      Partitions of 2^n into powers of 2.
-------------------------------------------------------------------

ID Number: A078125
Sequence:  1,2,5,23,239,5828,342383,50110484,18757984046,
18318289003448
Name:      First column of matrix A078123, which is the square of the
infinite lower triangular matrix A078122 that shifts
left and up when cubed.
Example:   Square of A078122 = A078123 as can be seen by 4x4 submatrix:
[1,_0,_0,0]^2=[_1,_0,_0,_0]
[1,_1,_0,0]___[_2,_1,_0,_0]
[1,_3,_1,0]___[_5,_6,_1,_0]
[1,12,_9,1]___[23,51,18,_1]
-------------------------------------------------------------------

ID Number: A078122
Sequence:  1,1,1,1,3,1,1,12,9,1,1,93,117,27,1,1,1632,3033,1080,81,1,1,
68457,177507,86373,9801,243,1,1,7112055,24975171,15562314,
2371761,88452,729,1,1,1879090014,8786827629,6734916423,
1291958181,64392813,796797
Name:      Infinite lower triangular matrix, M, that satisfies
[M^3](i,j) = M(i+1,j+1) for all i,j>=0
where [M^n](i,j) denotes the element at row i, column j,
of the n-th power of matrix M, with M(0,k)=1 and M(k,k)=1
for all k>=0.
Comments:  M also satisfies: [M^(3k)](i,j) = [M^k](i+1,j+1) for all
i,j,k>=0; thus [M^(3^n)](i,j) = M(i+n,j+n) for all n>=0.

Example:   [1,_0,_0,0]^3=[_1,__0,_0,_0]
[1,_1,_0,0]___[_3,__1,_0,_0]
[1,_3,_1,0]___[12,__9,_1,_0]
[1,12,_9,1]___[93,117,27,_1]

Further examples of powers of triangular matrix M of A078122:

M=
1,
1,1,
1,3,1,
1,12,9,1,
1,93,117,27,1,
1,1632,3033,1080,81,1,
1,68457,177507,86373,9801,243,1,
1,7112055,24975171,15562314,2371761,88452,729,1,
...

M^2=
1,
2,1,
5,6,1,
23,51,18,1,
239,861,477,54,1,
5828,32856,25263,4347,162,1,
342383,3013980,3016107,699813,39285,486,1,
50110484,690729981,865184724,253656252,19053063,354051,1458,1,
...

M^3 = M excluding first row and column =
1,
3,1,
12,9,1,
93,117,27,1,
1632,3033,1080,81,1,
68457,177507,86373,9801,243,1,
7112055,24975171,15562314,2371761,88452,729,1,
...

M^6 = M^2 excluding first row and column =
1,
6,1,
51,18,1,
861,477,54,1,
32856,25263,4347,162,1,
3013980,3016107,699813,39285,486,1,
690729981,865184724,253656252,19053063,354051,1458,1,
...

M^9 = M^3 excluding first row and column =
1,
9,1,
117,27,1,
3033,1080,81,1,
177507,86373,9801,243,1,
24975171,15562314,2371761,88452,729,1,
...
-------------------------------------------------------------------

```