A016121 -id:A016121 - cp's OEIS frontend

A097712 Lower triangular matrix T, read by rows, such that T(n,0) = 1 and T(n,k) = T(n-1,k) + T^2(n-1,k-1) for k>0, where T^2 is the matrix square of T.

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, 1, 1, 9708797, 145895764, 319822055, 189724354, 37329584, 2608864, 64256, 511, 1

Offset: 0

Paul D. Hanna, Aug 24 2004

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

			T(5,1) = T(4,1) + T^2(4,0) = 25 + 86 = 111.
T(5,2) = T(4,2) + T^2(4,1) = 44 + 302 = 346.
T(5,3) = T(4,3) + T^2(4,2) = 15 + 193 = 208.
Rows of T begin:
  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, 1;
Rows of T^2 begin:
       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;
  226592, 2458364, 4241473, 1997752, 305136, 15681, 254, 1;
Column 0 of T^2 forms A016121.
Row sums of T^2 form the first differences of A016121.

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A016121 (row sums), A093662, A097710, A097713.

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}]]]];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 02 2019 *)

T(n,k)=if(n<0 || k>n,0,if(n==k,1,if(k==0,1, T(n-1,k)+sum(j=0,n-1,T(n-1,j)*T(j,k-1));)))

@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))
flatten([[T(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Feb 20 2024

T(n, k) = T(n-1, k) + Sum_{j=0..n-1} T(n-1, j)*T(j, k-1), with T(n, 0) = T(n, n) = 1.
T(n, 1) = A097713(n-1), n >= 1.
Sum_{k=0..n} T(n, k) = A016121(n) (row sums).

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

Original entry on oeis.org

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.

A125859 Antidiagonal sums of table A125860.

Original entry on oeis.org

1, 2, 4, 10, 35, 184, 1531, 21080, 497017, 20533486, 1508839043, 199272672334, 47686000150774, 20817464210086523, 16678749474397158418, 24657143458135746104239, 67591557017940565183386368

Offset: 0

Paul D. Hanna, Dec 13 2006

nonn

Cf. A125860; A016121, A125862, A125863, A125864, A125865, A125861.

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

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

A093662 Lower triangular matrix, read by rows, defined as the convergent of the concatenation of matrices using the iteration: M(n+1) = [[M(n),0*M(n)],[M(n),M(n)^2]], with M(0) = [1].

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 2, 1, 1, 0, 1, 0, 2, 0, 1, 1, 1, 2, 1, 5, 2, 4, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 2, 1, 1, 0, 1, 0, 0, 0, 0, 0, 2, 0, 1, 1, 1, 2, 1, 0, 0, 0, 0, 5, 2, 4, 1, 1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 1, 1, 1, 0, 0, 2, 1, 0, 0, 5, 2, 0, 0, 4, 1

Offset: 1

Paul D. Hanna, Apr 08 2004

Row sums form A093663, where A093663(2^n) = A016121(n) for n>=0. The 2^n-th row converges to A093664, where A093664(2^n+1) = A016121(n) for n>=0.

			Let M(n) be the lower triangular matrix formed from the first 2^n rows.
To generate M(3) from M(2), obtain the matrix square of M(2):
[1,0,0,0]^2=[1,0,0,0]
[1,1,0,0]...[2,1,0,0]
[1,0,1,0]...[2,0,1,0]
[1,1,2,1]...[5,2,4,1],
then M(3) is formed by starting with M(2) and appending M(2) to the bottom left and M(2)^2 to the bottom right:
[1],
[1,1],
[1,0,1],
[1,1,2,1],
..........
[1,0,0,0],[1],
[1,1,0,0],[2,1],
[1,0,1,0],[2,0,1],
[1,1,2,1],[5,2,4,1].
Repeating this process converges to triangle A093662.

Cf. A016121, A093655, A093658, A093663, A093664.

A351287 Number of symmetric 0-1 matrices with zero main diagonal and nondecreasing number of ones in the rows.

Original entry on oeis.org

1, 2, 4, 16, 84, 936, 16758, 602544, 37693734, 4588585904, 1016082688298, 436137488655846, 348748058993750616, 538461898813943437676

Offset: 1

Max Alekseyev, Feb 06 2022

Also, number of graphs with vertices labeled 1, 2, ..., n such that their degrees are nondecreasing.

Cf. A016121, A351157, A351288.

\\ See link in A295193 for GraphsByDegreeSeq.
a(n)={my(M=GraphsByDegreeSeq(n,n,(p,r)->1)); sum(i=1, matsize(M)[1], my(u=Vec(M[i,1])); prod(j=1, #u, u[j]!)*M[i,2]/n!)} \\ Andrew Howroyd, Feb 06 2022

def a351287(n): return sum(prod(factorial(e) for e in Partition((d+1 for d in G.degree_sequence())).to_exp()) // G.automorphism_group(return_group=False, order=True) for G in graphs(n))

a(11)-a(14) from Andrew Howroyd, Feb 06 2022

cp's OEIS Frontend

A097712 Lower triangular matrix T, read by rows, such that T(n,0) = 1 and T(n,k) = T(n-1,k) + T^2(n-1,k-1) for k>0, where T^2 is the matrix square of T.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

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

A125859 Antidiagonal sums of table A125860.

Views

Author

Keywords

Crossrefs

A125861 Main diagonal of table A125860.

Views

Author

Keywords

Crossrefs

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

A093662 Lower triangular matrix, read by rows, defined as the convergent of the concatenation of matrices using the iteration: M(n+1) = [[M(n),0*M(n)],[M(n),M(n)^2]], with M(0) = [1].

Views

Author

Keywords

Comments

Examples

Crossrefs

A351287 Number of symmetric 0-1 matrices with zero main diagonal and nondecreasing number of ones in the rows.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Sage

Extensions