A078121 -id:A078121 - cp's OEIS frontend

A111830 Triangle P, read by rows, that satisfies [P^7](n,k) = P(n+1,k+1) for n>=k>=0, also [P^(7*m)](n,k) = [P^m](n+1,k+1) for all m, where [P^m](n,k) denotes the element at row n, column k, of the matrix power m of P, with P(0,k)=1 and P(k,k)=1 for all k>=0.

1, 1, 1, 1, 7, 1, 1, 154, 49, 1, 1, 16275, 8281, 343, 1, 1, 9106461, 6558209, 410914, 2401, 1, 1, 28543862991, 27307109501, 2298650515, 20170801, 16807, 1, 1, 521136519414483, 636922972420469, 67522139062441, 790856748801, 988621354

Offset: 0

Gottfried Helms and Paul D. Hanna, Aug 22 2005

Also P(n,k) = partitions of (7^n - 7^(n-k)) into powers of 7 <= 7^(n-k).

			Let q=7; the g.f. of column k of matrix power P^m is:
1 + (m*q^k)*L(x) + (m*q^k)^2/2!*L(x)*L(q*x) +
(m*q^k)^3/3!*L(x)*L(q*x)*L(q^2*x) +
(m*q^k)^4/4!*L(x)*L(q*x)*L(q^2*x)*L(q^3*x) + ...
where L(x) satisfies:
x/(1-x) = L(x) + L(x)*L(q*x)/2! + L(x)*L(q*x)*L(q^2*x)/3! + ...
and L(x) = x - 5/2!*x^2 + 83/3!*x^3 + 16110/4!*x^4 +... (A111834).
Thus the g.f. of column 0 of matrix power P^m is:
1 + m*L(x) + m^2/2!*L(x)*L(7*x) + m^3/3!*L(x)*L(7*x)*L(7^2*x) +
m^4/4!*L(x)*L(7*x)*L(7^2*x)*L(7^3*x) + ...
Triangle P begins:
1;
1,1;
1,7,1;
1,154,49,1;
1,16275,8281,343,1;
1,9106461,6558209,410914,2401,1;
1,28543862991,27307109501,2298650515,20170801,16807,1; ...
where P^7 shifts columns left and up one place:
1;
7,1;
154,49,1;
16275,8281,343,1; ...

Cf. A111831 (column 1), A111832 (row sums), A111833 (matrix log); triangles: A110503 (q=-1), A078121 (q=2), A078122 (q=3), A078536 (q=4), A111820 (q=5), A111825 (q=6), A111835 (q=8).

PARI
```
P(n,k,q=7)=local(A=Mat(1),B);if(n
				
```

Let q=7; the g.f. of column k of P^m (ignoring leading zeros) equals: 1 + Sum_{n>=1} (m*q^k)^n/n! * Product_{j=0..n-1} L(q^j*x) where L(x) satisfies: x/(1-x) = Sum_{n>=1} Product_{j=0..n-1} L(q^j*x)/(j+1) and L(x) equals the g.f. of column 0 of the matrix log of P (A111834).

A111835 Triangle P, read by rows, that satisfies [P^8](n,k) = P(n+1,k+1) for n>=k>=0, also [P^(8*m)](n,k) = [P^m](n+1,k+1) for all m, where [P^m](n,k) denotes the element at row n, column k, of the matrix power m of P, with P(0,k)=1 and P(k,k)=1 for all k>=0.

Original entry on oeis.org

1, 1, 1, 1, 8, 1, 1, 232, 64, 1, 1, 36968, 16192, 512, 1, 1, 35593832, 21928768, 1047040, 4096, 1, 1, 219379963496, 178379459392, 11424946688, 67096576, 32768, 1, 1, 9003699178010216, 9288403489672000, 748093366229504, 5862250172416

Offset: 0

Gottfried Helms and Paul D. Hanna, Aug 22 2005

Also P(n,k) = partitions of (8^n - 8^(n-k)) into powers of 8 <= 8^(n-k).

			Let q=8; the g.f. of column k of matrix power P^m is:
1 + (m*q^k)*L(x) + (m*q^k)^2/2!*L(x)*L(q*x) +
(m*q^k)^3/3!*L(x)*L(q*x)*L(q^2*x) +
(m*q^k)^4/4!*L(x)*L(q*x)*L(q^2*x)*L(q^3*x) + ...
where L(x) satisfies:
x/(1-x) = L(x) + L(x)*L(q*x)/2! + L(x)*L(q*x)*L(q^2*x)/3! + ...
and L(x) = x - 6/2!*x^2 + 142/3!*x^3 + 31800/4!*x^4 +... (A111839).
Thus the g.f. of column 0 of matrix power P^m is:
1 + m*L(x) + m^2/2!*L(x)*L(8*x) + m^3/3!*L(x)*L(8*x)*L(8^2*x) + m^4/4!*L(x)*L(8*x)*L(8^2*x)*L(8^3*x) + ...
Triangle P begins:
1;
1,1;
1,8,1;
1,232,64,1;
1,36968,16192,512,1;
1,35593832,21928768,1047040,4096,1;
1,219379963496,178379459392,11424946688,67096576,32768,1; ...
where P^8 shifts columns left and up one place:
1;
8,1;
232,64,1;
36968,16192,512,1; ...

Cf. A111836 (column 1), A111837 (row sums), A111838 (matrix log); triangles: A110503 (q=-1), A078121 (q=2), A078122 (q=3), A078536 (q=4), A111820 (q=5), A111825 (q=6), A111830 (q=7).

PARI
```
P(n,k,q=8)=local(A=Mat(1),B);if(n
				
```

Let q=8; the g.f. of column k of P^m (ignoring leading zeros) equals: 1 + Sum_{n>=1} (m*q^k)^n/n! * Product_{j=0..n-1} L(q^j*x) where L(x) satisfies: x/(1-x) = Sum_{n>=1} Product_{j=0..n-1} L(q^j*x)/(j+1) and L(x) equals the g.f. of column 0 of the matrix log of P (A111839).

A089177 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n))) giving number of non-squashing partitions of n into k parts.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 4, 4, 1, 1, 5, 6, 2, 1, 6, 9, 4, 1, 7, 12, 6, 1, 8, 16, 10, 1, 1, 9, 20, 14, 2, 1, 10, 25, 20, 4, 1, 11, 30, 26, 6, 1, 12, 36, 35, 10, 1, 13, 42, 44, 14, 1, 14, 49, 56, 20, 1, 15, 56, 68, 26, 1, 16, 64, 84, 36, 1, 1, 17, 72, 100, 46, 2, 1, 18, 81, 120, 60, 4, 1

Offset: 0

N. J. A. Sloane, Dec 08 2003

T(n,k) = A181322(n,k) - A181322(n,k-1) for n>0. - Alois P. Heinz, Jan 25 2014

			Triangle begins:
  1;
  1, 1;
  1, 2,  1;
  1, 3,  2;
  1, 4,  4,  1;
  1, 5,  6,  2;
  1, 6,  9,  4;
  1, 7, 12,  6;
  1, 8, 16, 10,  1;

Alois P. Heinz, Rows n = 0..1002, flattened
N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003; Discrete Math., 294 (2005), 259-274.

Cf. A078121, A089178. Columns give A002620, A008804, A088932, A088954. Row sums give A000123.

T:= proc(n) option remember;
     `if`(n=0, 1, zip((x, y)-> x+y, [T(n-1)], [0, T(floor(n/2))], 0)[])
    end:
seq(T(n), n=0..25);  # Alois P. Heinz, Apr 01 2012

row[0] = {1}; row[1] = {1, 1}; row[n_] := row[n] = Plus @@ PadRight[ {row[n-1], Join[{0}, row[Floor[n/2]]]} ]; Table[row[n], {n, 0, 25}] // Flatten (* Jean-François Alcover, Jan 31 2014 *)

Row 0 = {1}, row 1 = {1 1}; for n >=2, row n = row n-1 + (row floor(n/2) shifted one place right).
G.f. for column k (k >= 2): x^(2^(k-2))/((1-x)*Product_{j=0..k-2} (1-x^(2^j))). [corrected by Jason Yuen, Jan 12 2025]
Conjecture: let R(n,x) be the n-th reversed row polynomial, then R(n,x) = Sum_{k=0..A000523(A053645(n)) + 1} T(A053645(n),k)*R(2^(A000523(n)-k),x) for n > 0, n != 2^m with R(0,x) = 1 where R(2^m,x) is the (m+1)-th row polynomial of A078121. - Mikhail Kurkov, Jun 28 2025

More terms from Alford Arnold, May 22 2004

A078123 Square of infinite lower triangular matrix A078122.

Original entry on oeis.org

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, 18757984046, 406279238154

Offset: 0

Paul D. Hanna, Nov 18 2002

			Square of A078122 = A078123 as can be seen by 4 X 4 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]

Alois P. Heinz, Rows n = 0..60, flattened

Cf. A078121, A078122, A078124, A078125.

S:= proc(i, j) option remember;
       add(M(i, k)*M(k, j), k=0..i)
    end:
M:= proc(i, j) option remember; `if`(j=0 or i=j, 1,
       add(S(i-1, k)*M(k, j-1), k=0..i-1))
    end:
seq(seq(S(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Feb 27 2015

S[i_, j_] := S[i, j] = Sum[M[i, k]*M[k, j], {k, 0, i}]; M[i_, j_] := M[i, j] = If[j == 0 || i == j, 1, Sum[S[i-1, k]*M[k, j-1], {k, 0, i-1}]]; Table[Table[S[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Mar 06 2015, after Alois P. Heinz *)

M(1, j) = A078125(j), M(j+1, j)=2*3^j.

A125799 Antidiagonal sums of table A125790.

Original entry on oeis.org

1, 2, 4, 9, 25, 94, 520, 4521, 64793, 1581010, 67106004, 5029631745, 673439168257, 162631617757086, 71416302988324776, 57430160224301687377, 85096038984339418975505, 233592305902515392375925762, 1193627868786115606927913952196, 11402285904243733254203516140245465

Offset: 0

Paul D. Hanna, Dec 10 2006

nonn

Table A125790 is related to partitions into powers of 2, with A002577 in column 1 of A125790; further, column k of A125790 equals row sums of matrix power A078121^k, where triangle A078121 shifts left one column under matrix square.

Cf. A125790, A078121; columns: A002577, A125792, A125793, A125794, A125795, A125796; diagonals: A125797, A125798.

a(n)=local(q=2,A=Mat(1), B); for(m=1, n+1, B=matrix(m, m); for(i=1, m, for(j=1, i, if(j==i || j==1, B[i, j]=1, B[i, j]=(A^q)[i-1, j-1]); )); A=B); return(sum(c=0,n,(A^(c+1))[n-c+1,1]))

A381810 Array read by downward antidiagonals: A(n,k) is a generalization of odd columns of A125790 defined in Comments for n > 0, k >= 0.

Original entry on oeis.org

2, 4, 4, 6, 16, 6, 8, 36, 20, 10, 10, 64, 42, 84, 14, 12, 100, 72, 286, 100, 20, 14, 144, 110, 680, 322, 120, 26, 16, 196, 156, 1330, 744, 364, 140, 36, 18, 256, 210, 2300, 1430, 816, 406, 656, 46, 20, 324, 272, 3654, 2444, 1540, 888, 3396, 740, 60, 22, 400, 342, 5456, 3850, 2600, 1650, 10816, 3682, 840, 74

Offset: 1

Mikhail Kurkov, May 05 2025

This is generalization in the sense that first column of A125790 is A000123(2^(n-1)) while in this square array column zero is conjecturally A000123(n).
A(n,k) = v_{A001511(n)} where we start with vector v of fixed length L(n) = A070939(n) with elements v_i = A125790(i,2*k+1), pre-calculate A078121 up to L(n)-th row, reserve t as an empty vector of fixed length L(n) and for i=1..A119387(n+1), for j=1..L(n)-i+1 apply t := v (at the beginning of each cycle for i) and also apply v_j := Sum_{k=1..j+1} A078121(j,k-1)*t_k if R(n,L(n)-i) = 1, otherwise v_j := Sum_{k=1..j+1} A078121(j,k-1)*t_k*(-1)^(j+k+1). Here R(n,k) = floor(n/(2^k)) mod 2 is the (k+1)-th bit in the binary expansion of n.
Conjecture: sequence A(n,k) for fixed n is a polynomial of degree A070939(n).

			Array begins:
===========================================================
n\k|  0    1     2      3      4      5       6       7 ...
---+-------------------------------------------------------
1  |  2,   4,    6,     8,    10,    12,     14,     16 ...
2  |  4,  16,   36,    64,   100,   144,    196,    256 ...
3  |  6,  20,   42,    72,   110,   156,    210,    272 ...
4  | 10,  84,  286,   680,  1330,  2300,   3654,   5456 ...
5  | 14, 100,  322,   744,  1430,  2444,   3850,   5712 ...
6  | 20, 120,  364,   816,  1540,  2600,   4060,   5984 ...
7  | 26, 140,  406,   888,  1650,  2756,   4270,   6256 ...
8  | 36, 656, 3396, 10816, 26500, 55056, 102116, 174336 ...
  ...

Cf. A000123, A001511, A007814, A053645, A062383, A070939, A078121, A106400, A119387, A125790, A236206.

upto1(n) = my(v1); v1 = vector(n+1, i, vector(i, j, j==1 || j==i)); for(i=2, n, for(j=1, i-1, v1[i+1][j+1] = sum(k=j-1, i-1, v1[i][k+1]*v1[k+1][j]))); v1
A(n,m) = my(L = logint(n,2), A = valuation(n,2), B = logint(n>>A,2), v1, v2, v3); v1 = upto1(L+2); v2 = vector(L+2, i, vecsum(v1[i])); for(i=1, 2*m, v2 = vector(L+2, i, sum(j=1, i, v1[i][j]*v2[j]))); for(i=1, B, v3 = v2; for(j=1, L-i+1, v2[j+1] = sum(k=1, j+1, v1[j+1][k]*v3[k+1]*if(!bittest(n,L-i+1), (-1)^(j+k+1), 1)))); v2[A+2]

upto1(n) = my(v1); v1 = vector(n+1, i, vector(i, j, j==1 || j==i)); for(i=2, n, for(j=1, i-1, v1[i+1][j+1] = sum(k=j-1, i-1, v1[i][k+1]*v1[k+1][j]))); v1
upto2(n,m) = my(L = logint(n,2), A = valuation(n,2), B = logint(n>>A,2), v1, v2, v3, v4, v5); v1 = upto1(L+2); v2 = vector(L+2, i, 1); v3 = vector(m+1, i, 0); for(s=0, m, for(i=1, min(s+1,2), v2 = vector(L+2, i, sum(j=1, i, v1[i][j]*v2[j]))); v4 = v2; for(i=1, B, v5 = v4; for(j=1, L-i+1, v4[j+1] = sum(k=1, j+1, v1[j+1][k]*v5[k+1]*if(!bittest(n,L-i+1), (-1)^(j+k+1), 1)))); v3[s+1] = v4[A+2]); v3 \\ slightly modified version of the first program, some kind of memoization; generates A(n,k) for k=0..m

A(2^(n-1),k) = A125790(n,2*k+1) for n > 0, k >= 0.
Conjectured formulas: (Start)
A(n,0) = A000123(n) for n > 0.
A(n,k) = Sum_{j=0..k} A000123(A062383(n)*j+n)*A106400(k-j) for n > 0, k >= 0.
If we change v_i = A125790(i,2*k+1) to v_i = A125790(i,2*k) to get similar generalization of even columns, then for resulting array B(n,k) we have B(n,k) = Sum_{j=0..k} A000123(A062383(n)*j+A053645(n))*A106400(k-j) for n > 0, k >= 0.
2*(k+1) divides A(n,k) for n > 0 if (k+1) is a term of A236206.
G.f. for n-th row is f(A070939(n)+1,n) for n > 0 where f(n,k) = (Sum_{(c_0 + c_1 + ... + c_{n-1}) == 2*k (mod 2^n), 0 <= c_i < 2^n, 2^i divides c_i} x^((c_0 + c_1 + ... + c_{n-1} - 2*k)/2^n))/(1-x)^n for n > 0, k >= 0. Similarly, g.f. for n-th row of B(n,k) is f(A070939(n)+1,A053645(n)).
G.f. for n-th row is (Sum_{i=0..L(n)-1} x^i * Sum_{j=0..i} binomial(L(n)+1,j)*A(n,i-j)*(-1)^j)/(1-x)^(L(n)+1) for n > 0 where L(n) = A070939(n).
s(4*n+1) = 1 for n >= 0, s(4*n) = s(4*n+2) = 1 if A010060(n) = 1 for n > 0 where s(n) = A007814(Sum_{k=0..n-1} A(k+1,n-k-1)). (End)

cp's OEIS Frontend

A111830 Triangle P, read by rows, that satisfies [P^7](n,k) = P(n+1,k+1) for n>=k>=0, also [P^(7*m)](n,k) = [P^m](n+1,k+1) for all m, where [P^m](n,k) denotes the element at row n, column k, of the matrix power m of P, with P(0,k)=1 and P(k,k)=1 for all k>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A111835 Triangle P, read by rows, that satisfies [P^8](n,k) = P(n+1,k+1) for n>=k>=0, also [P^(8*m)](n,k) = [P^m](n+1,k+1) for all m, where [P^m](n,k) denotes the element at row n, column k, of the matrix power m of P, with P(0,k)=1 and P(k,k)=1 for all k>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A089177 Triangle read by rows: T(n,k) (n >= 0, 0 <= k <= 1+log_2(floor(n))) giving number of non-squashing partitions of n into k parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A078123 Square of infinite lower triangular matrix A078122.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A125799 Antidiagonal sums of table A125790.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A381810 Array read by downward antidiagonals: A(n,k) is a generalization of odd columns of A125790 defined in Comments for n > 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

Formula