A098539 -id:A098539 - cp's OEIS frontend

A111811 Column 0 of the matrix logarithm (A111810) of triangle A098539, which shifts columns left and up under matrix square; these terms are the result of multiplying the element in row n by n!.

0, 1, 2, 10, 88, 1096, 11856, -402480, -1891968, 36024603264, 359905478400, -53686393014816000, -644141701131494400, 1790653231402788752593920, 25068910772059830672353280, -1280832036591718248285105113241600

Offset: 0

Paul D. Hanna, Aug 22 2005

sign

Let q=2; the g.f. of column k of A098539^m (matrix power m) is: 1 + Sum_{n>=1} (m*q^k)^n/n! * Product_{j=0..n-1} A(q^j*x).

			A(x) = x + 2/2!*x^2 + 10/3!*x^3 + 88/4!*x^4 + 1096/5!*x^5 +...
where e.g.f. A(x) satisfies:
x = A(x) - A(x)*A(2*x)/2! + A(x)*A(2*x)*A(2^2*x)/3! - A(x)*A(2*x)*A(2^2*x)*A(2^3*x)/4! + ...
also:
x/(1+x) = A(x) - 2*A(x)*A(2*x)/2! + 2^2*A(x)*A(2*x)*A(2^2*x)/3! - 2^3*A(x)*A(2*x)*A(2^2*x)*A(2^3*x)/4! +...
Let G(x) be the g.f. of A002449 (column 1 of A098539), then
(G(x)-1)/x = 1 + 2*x + 6*x^2 + 26*x^3 + 166*x^4 + 1626*x^5 +...
= 1 + 2*A(x) + 2^2*A(x)*A(2*x)/2! + 2^3*A(x)*A(2*x)*A(2^2*x)/3! + 2^4*A(x)*A(2*x)*A(2^2*x)*A(2^3*x)/4! +...

Cf. A111810 (matrix log), A098539 (triangle), A002449, A111814 (variant), A111941 (q=-1), A111843 (q=3), A111848 (q=4).

{a(n,q=2)=local(A=x+x*O(x^n));for(i=1,n, A=x/(1+sum(j=1,n,prod(k=1,j,-subst(A,x,q^k*x))/(j+1)!))); return(n!*polcoeff(A,n))}

E.g.f. satisfies: x = -Sum_{n>=1} Prod_{j=0..n-1} -A(2^j*x)/(j+1), also: x/(1+x) = Sum_{n>=1} (-2)^(n-1)*Prod_{j=0..n-1} A(2^j*x)/(j+1).

A111810 Matrix log of triangle A098539, which shifts columns left and up under matrix square; these terms are the result of multiplying each element in row n and column k by (n-k)!.

Original entry on oeis.org

0, 1, 0, 2, 2, 0, 10, 4, 4, 0, 88, 20, 8, 8, 0, 1096, 176, 40, 16, 16, 0, 11856, 2192, 352, 80, 32, 32, 0, -402480, 23712, 4384, 704, 160, 64, 64, 0, -1891968, -804960, 47424, 8768, 1408, 320, 128, 128, 0, 36024603264, -3783936, -1609920, 94848, 17536, 2816, 640, 256, 256, 0

Offset: 0

Paul D. Hanna, Aug 22 2005

Column k equals 2^k times column 0 (A111811) when ignoring zeros above the diagonal.

			Matrix log of A098539, with factorial denominators, begins:
0;
1/1!, 0;
2/2!, 2/1!, 0;
10/3!, 4/2!, 4/1!, 0;
88/4!, 20/3!, 8/2!, 8/1!, 0;
1096/5!, 176/4!, 40/3!, 16/2!, 16/1!, 0;
11856/6!, 2192/5!, 352/4!, 80/3!, 32/2!, 32/1!, 0; ...

Cf. A098539 (triangle), A111811 (column 0), A111813 (variant), A111941 (q=-1), A111843 (q=3), A111848 (q=4).

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

T(n, k) = 2^k*T(n-k, 0) = 2^k*A111811(n-k) for n>=k>=0.

A098540 Row sums of triangle A098539, which shifts left one column under the matrix square.

Original entry on oeis.org

1, 2, 5, 17, 81, 561, 5905, 98673, 2715025, 126550129, 10211715985, 1450856148081, 367849450783633, 168250359224212593, 140078954639877776273, 213886080203739816320113, 602782564524824650717471633

Offset: 0

Paul D. Hanna, Sep 13 2004

nonn

Cf. A098539, A098541.

a(n)=local(A,B,C,m);A=matrix(1,1);A[1,1]=1; for(m=2,n+1,B=A^2;C=matrix(m,m);for(j=1,m, for(k=1,j, if(j<3 || k==j || k>m-1,C[j,k]=1,if(k==1,C[j,k]=B[j-1,1],C[j,k]=B[j-1,k-1])); ));A=C);sum(i=1,n+1,A[n+1,i])

A098541 Column 2 of triangle A098539, which shifts left one column under the matrix square.

Original entry on oeis.org

1, 4, 20, 140, 1460, 23884, 639156, 28895052, 2260707508, 311748794188, 76846781851828, 34240231941576524, 27825184844063467700, 41547951604100714698572, 114705005843089453002549428

Offset: 0

Paul D. Hanna, Sep 13 2004

nonn

Cf. A098539, A098540.

a(n)=local(A,B,C,m);A=matrix(1,1);A[1,1]=1; for(m=2,n+3,B=A^2;C=matrix(m,m);for(j=1,m, for(k=1,j, if(j<3 || k==j || k>m-1,C[j,k]=1,if(k==1,C[j,k]=B[j-1,1],C[j,k]=B[j-1,k-1])); ));A=C);A[n+3,3]

A111812 Column 3 of triangle A098539, which shifts columns left and up under matrix square.

Original entry on oeis.org

1, 8, 72, 888, 16392, 479736, 23196168, 1909718520, 273790460424, 69532461669880, 31699923943776776, 26220200137673186808, 39689067731528646091272, 110732781183212424923225592

Offset: 0

Paul D. Hanna, Aug 22 2005

nonn

			A(x) = 1 + 8*x + 72*x^2 + 888*x^3 + 16392*x^4 + 479736*x^5 +...

Cf. A098539, A111811.

{a(n,q=2)=local(A=Mat(1),B);if(n<0,0, for(m=1,n+4,B=matrix(m,m);for(i=1,m, for(j=1,i, if(j==i,B[i,j]=1,if(j==1,B[i,j]=(A^q)[i-1,1], B[i,j]=(A^q)[i-1,j-1]));));A=B);return(A[n+4,4]))}

G.f.: A(x) = 1 + Sum_{n>=1} 8^n/n!*Product_{j=0..n-1} L(2^j*x) where L(x) = e.g.f. of A111811 (column 0 of matrix log of A098539) satisfies: x = L(x) - L(x)*L(2*x)/2! + L(x)*L(2*x)*L(2^2*x)/3! - L(x)*L(2*x)*L(2^2*x)*L(2^3*x)/4! + ...

A002449 Number of different types of binary trees of height n.

Original entry on oeis.org

1, 1, 2, 6, 26, 166, 1626, 25510, 664666, 29559718, 2290267226, 314039061414, 77160820913242, 34317392762489766, 27859502236825957466, 41575811106337540656038, 114746581654195790543205466, 588765612737696531880325270438, 5642056933026209681424588087899226

Offset: 0

N. J. A. Sloane

Two trees have the same type if they have the same number of nodes at each level. - Chams Lahlou, Jan 26 2019

Equals the number of partitions of 2^n-1 into powers of 2 (cf. A018819). a(n) = A018819(2^n-1) = binary partitions of 2^n-1. - Paul D. Hanna, Sep 22 2004

			G.f. = 1 + x + 2*x^2 + 6*x^3 + 26*x^4 + 166*x^5 + 1626*x^6 + 25510*x^7 + ...

George E. Andrews, Peter Paule, Axel Riese and Volker Strehl, "MacMahon's Partition Analysis V: Bijections, recursions and magic squares," in Algebraic Combinatorics and Applications, edited by Anton Betten, Axel Kohnert, Reinhard Laue and Alfred Wassermann [Proceedings of ALCOMA, September 1999] (Springer, 2001), 1-39.
A. Cayley, "On a problem in the partition of numbers," Philosophical Magazine (4) 13 (1857), 245-248; reprinted in his Collected Math. Papers, Vol. 3, pp. 247-249. - Don Knuth, Aug 17 2001
R. F. Churchhouse, Congruence properties of the binary partition function. Proc. Cambridge Philos. Soc. 66 1969 371-376.
R. F. Churchhouse, Binary partitions, pp. 397-400 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.
D. E. Knuth, Selected Papers on Analysis of Algorithms, p. 75 (gives asymptotic formula and lower bound).
H. Minc, The free commutative entropic logarithmetic. Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).
T. K. Moon (tmoon(AT)artemis.ece.usu.edu), Enumerations of binary trees, types of trees and the number of reversible variable length codes, submitted to Discrete Applied Mathematics, 2000.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..50
A. Cayley, On a problem in the partition of numbers, Philosophical Magazine (4) 13 (1857), 245-248; reprinted in his Collected Math. Papers, Vol. 3, pp. 247-249.
M. Cook and M. Kleber, Tournament sequences and Meeussen sequences, Electronic J. Comb. 7 (2000), #R44.
Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See pp. 31, 33, 34.
Chams Lahlou, A formula for some integer sequences that can be described by generating trees

Cf. A001699, A056207, A098539, A018819.

d := proc(n) option remember; if n<1 then 1 else sum(d(n-1),k=1..2*k) fi end; A002449 := n -> eval(d(n-1),k=1); # Michael Kleber, Dec 05 2000

lim = 16; p[0] = p[1] = 1; Do[If[OddQ[n], p[n] = p[n - 1], p[n] = p[n - 1] + p[n/2]], {n, 1, 2^lim - 1}]; a[n_] := p[2^n - 1]; Table[a[n], {n, 0, lim}] (* Jean-François Alcover, Sep 20 2011, after Paul D. Hanna *)

a(n)=local(A,B,C,m);A=matrix(1,1);A[1,1]=1; for(m=2,n+1,B=A^2;C=matrix(m,m);for(j=1,m, for(k=1,j, if(j<3 || k==j || k>m-1,C[j,k]=1,if(k==1,C[j,k]=B[j-1,1],C[j,k]=B[j-1,k-1])); ));A=C);A[n+1,1] \\ Paul D. Hanna

a(n)=polcoeff(1/prod(k=0,n,1-x^(2^k)+O(x^(2^n))),2^n-1)

{a(n, k=2) = if(n<2, n>=0, sum(i=1, k, a(n-1, 2*i)))}; /* Michael Somos, Nov 24 2016 */

a(n) = A098539(n, 1). - Paul D. Hanna, Sep 13 2004
G.f. A(x) = F(x,1) where F(x,n) satisfies: F(x,n) = F(x,n-1) + xF(x,2n) for n>0 with F(x,0)=1. - Paul D. Hanna, Apr 16 2007
From Benedict W. J. Irwin, Nov 16 2016: (Start)
Conjecture: a(n+2) = Sum_{i_1=1..2}Sum_{i_2=1..2*i_1}...Sum_{i_n=1..2*i_(n-1)} (2*i_n). For example:
a(3) = Sum_{i=1..2} 2*i.
a(4) = Sum_{i=1..2}Sum_{j=1..2*i} 2*j.
a(5) = Sum_{i=1..2}Sum_{j=1..2*i}Sum_{k=1..2*j} 2*k. (End)
The conjecture is true: see Links. - Chams Lahlou, Jan 26 2019

Recurrence and more terms from Michael Kleber, Dec 05 2000

A111975 Triangle P, read by rows, that satisfies [P^2](n,k) = P(n+1,k+1) for n>=k>=0, also [P^(2*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(k,k)=1 and P(k+2,2)=P(k+2,0) for k>=0.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 4, 4, 4, 1, 16, 16, 16, 8, 1, 96, 96, 96, 64, 16, 1, 896, 896, 896, 704, 256, 32, 1, 13568, 13568, 13568, 11776, 5504, 1024, 64, 1, 345088, 345088, 345088, 317952, 178176, 43776, 4096, 128, 1, 15112192, 15112192, 15112192, 14422016

Offset: 0

Paul D. Hanna, Aug 24 2005

Terms of column 0, column 1 and column 2 in row n are equal for n>2.

			Triangle P begins:
1;
1,1;
1,2,1;
4,4,4,1;
16,16,16,8,1;
96,96,96,64,16,1;
896,896,896,704,256,32,1;
13568,13568,13568,11776,5504,1024,64,1;
345088,345088,345088,317952,178176,43776,4096,128,1; ...
where P^2 shifts columns left and up one place:
1;
2,1;
4,4,1;
16,16,8,1;
96,96,64,16,1; ...
The matrix inverse, P^-1, equals signed P:
1;
-1,1;
1,-2,1;
-4,4,-4,1;
16,-16,16,-8,1; ...

Cf. A111976 (column 0), A111977 (row sums), A111978 (matrix log), A098539 (variant), A078536 (variant).

P(n,k,q=2)=local(A=Mat(1),B);if(n2,(A^q)[i-1,2],1), B[i,j]=(A^q)[i-1,j-1]));));A=B);return(A[n+1,k+1]))

The g.f. of column k of P^m (ignoring leading zeros) equals: 1 + Sum_{n>=1} (m*2^k)^n/n! * Product_{j=0..n-1} L(2^j*x) where L(x) is the g.f. of column 0 of the matrix log of P (A111979) and satisfies: x-x^2 = Sum_{j>=1}(1-2^j*x)*Prod_{i=0..j-1}L(2^i*x).

A098542 Triangle T, read by rows, such that the matrix square shifts T left one column and up one row, with T(0,0)=T(1,0)=1 and T(n,0)=0 for n>1 and T(n,n)=1 for n>=0.

Original entry on oeis.org

1, 1, 1, 0, 2, 1, 0, 2, 4, 1, 0, 2, 12, 8, 1, 0, 2, 44, 56, 16, 1, 0, 2, 236, 504, 240, 32, 1, 0, 2, 2028, 6776, 4720, 992, 64, 1, 0, 2, 29164, 146552, 139120, 40672, 4032, 128, 1, 0, 2, 719340, 5314680, 6583152, 2500832, 337344, 16256, 256, 1, 0, 2, 30943724

Offset: 0

Paul D. Hanna, Sep 16 2004

Column 2 forms A098543. Row sums form A098544. The absolute value of the matrix inverse equals A098539.

			Rows of T begin:
[1],
[1,1],
[0,2,1],
[0,2,4,1],
[0,2,12,8,1],
[0,2,44,56,16,1],
[0,2,236,504,240,32,1],
[0,2,2028,6776,4720,992,64,1],
[0,2,29164,146552,139120,40672,4032,128,1],
[0,2,719340,5314680,6583152,2500832,337344,16256,256,1],...
Rows of T^2 begin:
[1],
[2,1],
[2,4,1],
[2,12,8,1],
[2,44,56,16,1],
[2,236,504,240,32,1],...
showing that T shifts left and up under matrix square.
The matrix inverse of T begins:
[1],
[ -1,1],
[2,-2,1],
[ -6,6,-4,1],
[26,-26,20,-8,1],
[ -166,166,-140,72,-16,1],...
the absolute value of which equals triangle A098539.

Cf. A098543, A098544, A098539 (absolute inverse).

T(n,k)=local(A,B);A=matrix(1,1);A[1,1]=1;for(m=2,n+1,B=matrix(m,m); for(i=1,m, for(j=1,i,if(i<3 || j==i || j>m-1,B[i,j]=1,if(j==1, B[i,j]=(A^0)[i-1,1],B[i,j]=(A^2)[i-1,j-1]));));A=B);A[n+1,k+1]

T(n+1, 1) = 2 for n>0; T(n+1, n) = 2^n, T(n+2, n) = 4^n - 2^n for n>=0. Matrix square: [T^2](n, k) = T(n+1, k+1). Matrix inverse: [T^-1](n, k) = (-1)^(n-k)*A098539(n, k). Matrix square inverse: [T^-2](n, k) = (-1)^(n-k)*A098539(n+1, k+1).

cp's OEIS Frontend

A111811 Column 0 of the matrix logarithm (A111810) of triangle A098539, which shifts columns left and up under matrix square; these terms are the result of multiplying the element in row n by n!.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A111810 Matrix log of triangle A098539, which shifts columns left and up under matrix square; these terms are the result of multiplying each element in row n and column k by (n-k)!.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A098540 Row sums of triangle A098539, which shifts left one column under the matrix square.

Views

Author

Keywords

Crossrefs

Programs

PARI

A098541 Column 2 of triangle A098539, which shifts left one column under the matrix square.

Views

Author

Keywords

Crossrefs

Programs

PARI

A111812 Column 3 of triangle A098539, which shifts columns left and up under matrix square.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula

A002449 Number of different types of binary trees of height n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

Extensions

A111975 Triangle P, read by rows, that satisfies [P^2](n,k) = P(n+1,k+1) for n>=k>=0, also [P^(2*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(k,k)=1 and P(k+2,2)=P(k+2,0) for k>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A098542 Triangle T, read by rows, such that the matrix square shifts T left one column and up one row, with T(0,0)=T(1,0)=1 and T(n,0)=0 for n>1 and T(n,n)=1 for n>=0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI