A097712 -id:A097712 - cp's OEIS frontend

A125860 Rectangular table where column k equals row sums of matrix power A097712^k, read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 17, 12, 4, 1, 1, 86, 69, 22, 5, 1, 1, 698, 612, 178, 35, 6, 1, 1, 9551, 8853, 2251, 365, 51, 7, 1, 1, 226592, 217041, 46663, 5990, 651, 70, 8, 1, 1, 9471845, 9245253, 1640572, 161525, 13131, 1057, 92, 9, 1, 1, 705154187

Offset: 0

Paul D. Hanna, Dec 13 2006

Triangle A097712 satisfies: A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1) for n > 0, k > 0, with A097712(n,0)=A097712(n,n)=1 for n >= 0. Column 1 equals A016121, which counts the sequences (a_1, a_2, ..., a_n) of length n with a_1 = 1 satisfying a_i <= a_{i+1} <= 2*a_i.

T(2, n) = (n+1)*A005408(n) - Sum_{i=0..n} A001477(i) = (n+1)*(2*n+1) - A000217(n) = (n+1)*(3*n+2)/2; T(3, n) = (n+1)*A001106(n+1) - Sum_{i=0..n} A001477(i) = (n+1)*((n+1)*(7*n+2)/2) - A000217(n) = (n+1)*(7*n^2 + 8*n + 2)/2. - Bruno Berselli, Apr 25 2010

			Recurrence is illustrated by:
  T(4,1) = T(3,1) + T(3,2) = 17 + 69 = 86;
  T(4,2) = T(3,2) + T(3,3) + T(3,4) = 69 + 178 + 365 = 612;
  T(4,3) = T(3,3) + T(3,4) + T(3,5) + T(3,6) = 178 + 365 + 651 + 1057 = 2251.
Rows of this table begin:
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,...;
  1, 5, 12, 22, 35, 51, 70, 92, 117, 145, 176, 210, 247, 287, 330, ...;
  1, 17, 69, 178, 365, 651, 1057, 1604, 2313, 3205, 4301, 5622, 7189,..;
  1, 86, 612, 2251, 5990, 13131, 25291, 44402, 72711, 112780, 167486,..;
  1, 698, 8853, 46663, 161525, 435801, 996583, 2025458, 3768273, ...;
  1, 9551, 217041, 1640572, 7387640, 24530016, 66593821, 156664796, ...;
  1, 226592, 9245253, 100152049, 586285040, 2394413286, 7713533212, ...;
  1, 9471845, 695682342, 10794383587, 82090572095, 412135908606, ...;
  1, 705154187, 93580638024, 2079805452133, 20540291522675, ...;
  1, 94285792211, 22713677612832, 723492192295786, 9278896006526795,...;
  1, 22807963405043, 10025101876435413, 458149292979837523, ...;
  ...
where column k equals the row sums of matrix power A097712^k for k >= 0.
Triangle A097712 begins:
  1;
  1,      1;
  1,      3,       1;
  1,      8,       7,       1;
  1,     25,      44,      15,       1;
  1,    111,     346,     208,      31,      1;
  1,    809,    4045,    3720,     912,     63,     1;
  1,  10360,   77351,   99776,   35136,   3840,   127,   1;
  1, 236952, 2535715, 4341249, 2032888, 308976, 15808, 255; ...
where A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1);
e.g., A097712(5,2) = A097712(4,2) + [A097712^2](4,1) = 44 + 302 = 346.
Matrix square A097712^2 begins:
     1;
     2,     1;
     5,     6,     1;
    17,    37,    14,     1;
    86,   302,   193,    30,    1;
   698,  3699,  3512,   881,   62,   1;
  9551, 73306, 96056, 34224, 3777, 126, 1; ...
Matrix cube A097712^3 begins:
       1;
       3,      1;
      12,      9,      1;
      69,     87,     21,      1;
     612,   1146,    447,     45,    1;
    8853,  22944,  12753,   2019,   93,   1;
  217041, 744486, 549453, 120807, 8595, 189, 1; ...

Olivier Danvy, Summa Summarum: Moessner's Theorem without Dynamic Programming, arXiv:2412.03127 [cs.DM], 2024. See p. 16.

Cf. A097712; columns: A016121, A125862, A125863, A125864, A125865; A125861 (diagonal), A125859 (antidiagonal sums). Variants: A125790, A125800.

Cf. for recursive method [Ar(m) is the m-th term of a sequence in the OEIS] a(n) = n*Ar(n) - A000217(n-1) or a(n) = (n+1)*Ar(n+1) - A000217(n) and similar: A081436, A005920, A005945, A006003. - Bruno Berselli, Apr 25 2010

T[n_, k_] := T[n, k] = If[Or[n == 0, k == 0], 1, Sum[T[n - 1, j + k], {j, 0, k}]];
Table[T[#, k] &[n - k + 1], {n, 0, 9}, {k, 0, n + 1}] (* Michael De Vlieger, Dec 10 2024, after PARI *)

T(n,k)=if(n==0 || k==0,1,sum(j=0,k,T(n-1,j+k)))

T(n,k) = Sum_{j=0..k} T(n-1, j+k) for n > 0, with T(0,n)=T(n,0)=1 for n >= 0.

A125862 Column 2 of table A125860; also equals row sums of matrix power A097712^2.

Original entry on oeis.org

1, 3, 12, 69, 612, 8853, 217041, 9245253, 695682342, 93580638024, 22713677612832, 10025101876435413, 8100572528598910191, 12054728928174188426943, 33214476295395054879355617, 170255688895444623691322464599

Offset: 0

Paul D. Hanna, Dec 13 2006

nonn

Equals column 0 of matrix power A097712^3, where triangle A097712 satisfies recurrence: A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1).

Cf. A125860; A097712; other columns: A016121, A125863, A125864, A125865; A125861 (diagonal), A125859 (antidiagonal sums).

A125863 Column 3 of table A125860; also equals row sums of matrix power A097712^3.

Original entry on oeis.org

1, 4, 22, 178, 2251, 46663, 1640572, 100152049, 10794383587, 2079805452133, 723492192295786, 458149292979837523, 531871667833026397222, 1138955362720160687114704, 4523369812874327770490887837

Offset: 0

Paul D. Hanna, Dec 13 2006

nonn

Equals column 0 of matrix power A097712^4, where triangle A097712 satisfies recurrence: A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1).

Cf. A125860; A097712; other columns: A016121, A125862, A125864, A125865; A125861 (diagonal), A125859 (antidiagonal sums).

A125864 Column 4 of table A125860; also equals row sums of matrix power A097712^4.

Original entry on oeis.org

1, 5, 35, 365, 5990, 161525, 7387640, 586285040, 82090572095, 20540291522675, 9278896006526795, 7632398133742637255, 11514756687812563119530, 32063466203746720003813970, 165699104606274900865952221145

Offset: 0

Paul D. Hanna, Dec 13 2006

nonn

Equals column 0 of matrix power A097712^5, where triangle A097712 satisfies recurrence: A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1).

Cf. A125860; A097712; other columns: A016121, A125862, A125863, A125865; A125861 (diagonal), A125859 (antidiagonal sums).

A125865 Column 5 of table A125860; also equals row sums of matrix power A097712^5.

Original entry on oeis.org

1, 6, 51, 651, 13131, 435801, 24530016, 2394413286, 412135908606, 126722253316281, 70336222713070656, 71088278975389204986, 131802456226253519662956, 451158681817567800972000111

Offset: 0

Paul D. Hanna, Dec 13 2006

nonn

Equals column 0 of matrix power A097712^6, where triangle A097712 satisfies recurrence: A097712(n,k) = A097712(n-1,k) + [A097712^2](n-1,k-1).

Cf. A125860; A097712; other columns: A016121, A125862, A125863, A125864; A125861 (diagonal), A125859 (antidiagonal sums).

A097713 Column 1 of triangle A097712.

Original entry on oeis.org

1, 3, 8, 25, 111, 809, 10360, 236952, 9708797, 714862984, 95000655195, 22902964060238, 10070812803900694, 8120691251242651341, 12070960239863869828931, 33238610095183531376362138

Offset: 0

Paul D. Hanna, Aug 24 2004

nonn

Partial sums of A016121.

The row sums of triangle A097712 give A016121.

G. C. Greubel, Table of n, a(n) for n = 0..85

Cf. A016121, A097712.

T[n_, k_]:= T[n, k]= If[n<0 || k>n, 0, If[k==0 || k==n, 1, T[n-1,k] + Sum[T[n-1,j]*T[j,k-1], {j,0,n-1}] ]]; (* T=A097712 *)
A097713[n_]:= T[n,1];
Table[A097713[n], {n,30}] (* G. C. Greubel, Feb 22 2024 *)

@CachedFunction
def T(n, k): # T = A097712
    if k<0 or k>n: return 0
    elif k==0 or k==n: return 1
    else: return T(n-1, k) + sum(T(n-1, j)*T(j, k-1) for j in range(n))
def A097713(n): return T(n,1)
[A097713(n) for n in range(1,31)] # G. C. Greubel, Feb 22 2024

a(n) = Sum_{k=0..n} A016121(k).

A016121 Number of sequences (a_1, a_2, ..., a_n) of length n with a_1 = 1 satisfying a_i <= a_{i+1} <= 2*a_i.

Original entry on oeis.org

1, 2, 5, 17, 86, 698, 9551, 226592, 9471845, 705154187, 94285792211, 22807963405043, 10047909839840456, 8110620438438750647, 12062839548612627177590, 33226539134943667506533207, 170288915434579567358828997806, 1630770670148598007261992936663653

Offset: 0

Jeffrey Shallit

nonn

Number of n X n binary symmetric matrices with rows, considered as binary numbers, in nondecreasing order. - R. H. Hardin, May 30 2008

Also, number of (n+1) X (n+1) binary symmetric matrices with zero main diagonal and rows, considered as binary numbers, in nondecreasing order. - Max Alekseyev, Feb 06 2022

Alois P. Heinz, Table of n, a(n) for n = 0..50

Cf. A008934, A060690, A089006, A351157, A351158, A351287, A351288.

Row sums of triangle A097712.

T[n_, k_] := T[n, k] = If[n < 0 || k > n, 0, If[n == k, 1, If[k == 0, 1, T[n - 1, k] + Sum[T[n - 1, j] T[j, k - 1], {j, 0, n - 1}]]]];
a[n_] := Sum[T[n, k], {k, 0, n}];
a /@ Range[0, 20] (* Jean-François Alcover, Oct 02 2019 *)

@CachedFunction
def T(n, k): # T = A097712
    if k<0 or k>n: return 0
    elif k==0 or k==n: return 1
    else: return T(n-1, k) + sum(T(n-1, j)*T(j, k-1) for j in range(n))
def A016121(n): return sum(T(n,k) for k in range(n+1))
[A016121(n) for n in range(31)] # G. C. Greubel, Feb 21 2024

a(n) = Sum_{k=0..n} A097712(n, k). - Paul D. Hanna, Aug 24 2004

Equals the binomial transform of A008934 (number of tournament sequences): a(n) = Sum_{k=0..n} C(n, k)*A008934(k). - Paul D. Hanna, Sep 18 2005

A097710 Lower triangular matrix T, read by rows, such that row (n) is formed from the sums of adjacent terms in row (n-1) of the matrix square T^2, with T(0,0)=1.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 7, 13, 7, 1, 41, 88, 61, 15, 1, 397, 951, 781, 257, 31, 1, 6377, 16691, 15566, 6231, 1041, 63, 1, 171886, 484490, 500057, 231721, 48303, 4161, 127, 1, 7892642, 23701698, 26604323, 13843968, 3406505, 374127, 16577, 255, 1

Offset: 0

Paul D. Hanna, Aug 22 2004

Column 0 is equal to sequence A008934, which is the number of tournament sequences.

This triangle has the same row sums and first column terms as in rows 2^n, for n>=0, of triangle A093654.

			Rows of this triangle T begin:
       1;
       1,      1;
       2,      3,      1;
       7,     13,      7,      1;
      41,     88,     61,     15,     1;
     397,    951,    781,    257,    31,    1;
    6377,  16691,  15566,   6231,  1041,   63,   1;
  171886, 484490, 500057, 231721, 48303, 4161, 127, 1;
Rows of T^2 begin:
        1;
        2,        1;
        7,        6,        1;
       41,       47,       14,       1;
      397,      554,      227,      30,      1;
     6377,    10314,     5252,     979,     62,     1;
   171886,   312604,   187453,   44268,   4035,   126,   1;
  7892642, 15809056, 10795267, 3048701, 357804, 16323, 254, 1;
The sums of adjacent terms in row (n) of T^2 forms row (n+1) of T:
  T(5,0) = T^2(4,0) = 397;
  T(5,1) = T^2(4,0) + T^2(4,1) = 397 + 554 = 951;
  T(5,2) = T^2(4,1) + T^2(4,2) = 554 + 227 = 781.
Rows of matrix inverse T^(-1) begins:
   1;
  -1,     1;
   1,    -3,      1;
  -1,     8,     -7,     1;
   1,   -25,     44,   -15,      1;
  -1,   111,   -346,   208,    -31,    1;
   1,  -809,   4045, -3720,    912,  -63,    1;
  -1, 10360, -77351, 99776, -35136, 3840, -127, 1; ...
which is a signed version of A097712.

Paul D. Hanna, Table of n, a(n) for n = 0..495, of rows 0..30 of triangle in flattened form.

Cf. A000007, A000225, A093654, A097712.

Cf. A008934 (column k=0), A093657 (row sums), A097711 (column k=1).

T[n_, k_] := T[n, k] = Which[n<0 || k>n, 0, n == k, 1, k == 0, Sum[T[n-1, j]*T[j, 0], {j, 0, n-1}], True, Sum[T[n-1, j]*T[j, k-1], {j, 0, n-1}] + Sum[T[n-1, j]*T[j, k], {j, 0, n-1}]]; Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Nov 23 2016, adapted from PARI *)

/* Using Recurrence relation: */
{T(n,k) = if(n<0||k>n, 0, if(n==k,1, if(k==0, sum(j=0,n-1, T(n-1,j)*T(j,0)),  sum(j=0,n-1, T(n-1,j)*T(j,k-1)) + sum(j=0,n-1, T(n-1,j)*T(j,k));)))}
for(n=0,8, for(k=0,n, print1(T(n,k),", "));print(""))

/* Faster: using Matrix generating method: */
{T(n,k) = my(M=matrix(2,2,r,c,if(r>=c,1))); for(i=1,n,
N=matrix(#M+1,#M+1,r,c, if(r>=c, if(r<=#M,M[r,c], if(c>1,(M^2)[r-1,c-1]) + if(c<=#M,(M^2)[r-1,c])) ));
M=N;); M[n+1,k+1]}
for(n=0,10,for(k=0,n,print1(T(n,k),", "));print("")) \\ Paul D. Hanna, Nov 27 2016

@CachedFunction
def T(n, k): # T = A097710
    if n< 0 or k<0 or k>n: return 0
    elif k==n: return 1
    elif k==0: return sum(T(n-1,j)*T(j,0) for j in range(n))
    else: return sum(T(n-1, j)*(T(j, k-1)+T(j,k)) for j in range(n))
flatten([[T(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Feb 21 2024

T(n, k) = T^2(n-1, k-1) + T^2(n-1, k) for n>=1 and k>1, with T(n, 1) = T^2(n-1, 1) and T(n,n) = 1 for n>=0, where T^2 is the matrix square of this triangle T.
T(n, k) = Sum_{j=0..n-1} T(n-1, j)*(T(j, k-1) + T(j,k)), with T(n, 0) = Sum_{j=0..n-1} T(n-1,j)*T(j,0), and T(n, n) = 1.
T(n, 0) = A008934(n).
T(n, 1) = A097711(n).
Sum_{k=0..n} T(n, k) = A093657(n+1) (row sums).
From G. C. Greubel, Feb 21 2024: (Start)
T(n, n-1) = A000225(n).
Sum_{k=0..n} (-1)^k*T(n, k) = A000007(n). (End)

A125861 Main diagonal of table A125860.

Original entry on oeis.org

1, 2, 12, 178, 5990, 435801, 66593821, 20997402098, 13512727916532, 17629371074833300, 46432767742317108086, 246240366959004185679198, 2624854986865673643625591411, 56179604057909797695704800461149

Offset: 0

Paul D. Hanna, Dec 13 2006

nonn

Cf. A125860; A097712; columns: A016121, A125862, A125863, A125864, A125865; A125859 (antidiagonal sums).

cp's OEIS Frontend

A125860 Rectangular table where column k equals row sums of matrix power A097712^k, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A125862 Column 2 of table A125860; also equals row sums of matrix power A097712^2.

Views

Author

Keywords

Comments

Crossrefs

A125863 Column 3 of table A125860; also equals row sums of matrix power A097712^3.

Views

Author

Keywords

Comments

Crossrefs

A125864 Column 4 of table A125860; also equals row sums of matrix power A097712^4.

Views

Author

Keywords

Comments

Crossrefs

A125865 Column 5 of table A125860; also equals row sums of matrix power A097712^5.

Views

Author

Keywords

Comments

Crossrefs

A097713 Column 1 of triangle A097712.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

SageMath

Formula

A016121 Number of sequences (a_1, a_2, ..., a_n) of length n with a_1 = 1 satisfying a_i <= a_{i+1} <= 2*a_i.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

SageMath

Formula

A097710 Lower triangular matrix T, read by rows, such that row (n) is formed from the sums of adjacent terms in row (n-1) of the matrix square T^2, with T(0,0)=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

SageMath

Formula

A125861 Main diagonal of table A125860.

Views

Author

Keywords

Crossrefs