A101483 -id:A101483 - cp's OEIS frontend

A101479 Triangular matrix T, read by rows, where row n equals row (n-1) of T^(n-1) after appending '1' for the main diagonal.

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 19, 9, 3, 1, 1, 191, 70, 18, 4, 1, 1, 2646, 795, 170, 30, 5, 1, 1, 46737, 11961, 2220, 335, 45, 6, 1, 1, 1003150, 224504, 37149, 4984, 581, 63, 7, 1, 1, 25330125, 5051866, 758814, 92652, 9730, 924, 84, 8, 1, 1, 735180292, 132523155, 18301950, 2065146, 199692, 17226, 1380, 108, 9, 1, 1

Offset: 0

Paul D. Hanna, Jan 21 2005, Jul 26 2006, May 27 2007

Remarkably, T equals the product of these triangular matrices: T = A107867*A107862^-1 = A107870*A107867^-1 = A107873*A107870^-1; reversing the order of these products yields triangle A107876.

			Triangle begins:
1;
1, 1;
1, 1, 1;
3, 2, 1, 1;
19, 9, 3, 1, 1;
191, 70, 18, 4, 1, 1;
2646, 795, 170, 30, 5, 1, 1;
46737, 11961, 2220, 335, 45, 6, 1, 1;
1003150, 224504, 37149, 4984, 581, 63, 7, 1, 1;
25330125, 5051866, 758814, 92652, 9730, 924, 84, 8, 1, 1;
735180292, 132523155, 18301950, 2065146, 199692, 17226, 1380, 108, 9, 1, 1; ...
Row 4 starts with row 3 of T^3 which begins:
1;
3, 1;
6, 3, 1;
19, 9, 3, 1; ...
row 5 starts with row 4 of T^4 which begins:
1;
4, 1;
10, 4, 1;
34, 14, 4, 1;
191, 70, 18, 4, 1; ...
An ALTERNATE GENERATING METHOD is illustrated as follows.
For row 4:
Start with a '1' and append 2 zeros,
take partial sums and append 1 zero,
take partial sums thrice more, resulting in:
1, 0, 0;
1, 1, 1, 0;
1, 2, 3, 3;
1, 3, 6, 9;
1, 4,10,19.
Final nonzero terms form row 4: [19,9,3,1,1].
For row 5:
Start with a '1' and append 3 zeros,
take partial sums and append 2 zeros,
take partial sums and append 1 zero,
take partial sums thrice more, resulting in:
1, 0, 0, 0;
1, 1, 1, 1, 0,  0;
1, 2, 3, 4, 4,  4,  0;
1, 3, 6,10,14, 18, 18;
1, 4,10,20,34, 52, 70;
1, 5,15,35,69,121,191;
where the final nonzero terms form row 5: [191,70,18,4,1,1].
Likewise, for row 6:
1, 0, 0, 0,  0;
1, 1, 1, 1,  1,  0,  0,  0;
1, 2, 3, 4,  5,  5,  5,  5,   0,   0;
1, 3, 6,10, 15, 20, 25, 30,  30,  30,   0;
1, 4,10,20, 35, 55, 80,110, 140, 170, 170;
1, 5,15,35, 70,125,205,315, 455, 625, 795;
1, 6,21,56,126,251,456,771,1226,1851,2646;
where the final nonzero terms form row 6: [2646,795,170,30,5,1,1].
Continuing in this way generates all rows of this triangle.

Alois P. Heinz, Rows n = 0..140, flattened (first 31 rows from Paul D. Hanna)

Columns are A101481, A101482, A101483, row sums form A101484.
Cf. A107876 (dual triangle).
Cf. A304184, A304185, A304186, A304187.

b:= proc(n) option remember;
      Matrix(n, (i,j)-> T(i-1,j-1))^(n-1)
    end:
T:= proc(n,k) option remember;
     `if`(n=k, 1, `if`(k>n, 0, b(n)[n,k+1]))
    end:
seq(seq(T(n,k), k=0..n), n=0..10);  # Alois P. Heinz, Apr 13 2020

b[n_] := b[n] = MatrixPower[Table[T[i-1, j-1], {i, n}, {j, n}], n-1];
T[n_, k_] := T[n, k] = If[n == k, 1, If[k > n, 0, b[n][[n, k+1]]]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Apr 25 2020, after Alois P. Heinz *)

{T(n,k) = my(A=Mat(1),B); for(m=1,n+1, B=matrix(m,m); for(i=1,m, for(j=1,i, if(j==i,B[i,j]=1, B[i,j] = (A^(i-2))[i-1,j]);)); A=B); return(A[n+1,k+1])}
for(n=0,10, for(k=0,n, print1(T(n,k),", ")); print(""))

{T(n,k) = my(A=vector(n+1),p); A[1]=1; for(j=1,n-k-1, p=(n-1)*(n-2)/2-(n-j-1)*(n-j-2)/2; A = Vec((Polrev(A)+x*O(x^p))/(1-x))); A = Vec((Polrev(A) +x*O(x^p)) / (1-x) ); A[p+1]}
for(n=0,10, for(k=0,n, print1(T(n,k),", ")); print(""))

A121418 Column 0 of triangle A121416.

Original entry on oeis.org

1, 2, 7, 43, 403, 5188, 85569, 1725291, 41145705, 1133047596, 35377360292, 1234796503280, 47636225803285, 2012509471127885, 92398547122062997, 4580472438441602301, 243822925502110419105, 13870297863425823346284

Offset: 0

Paul D. Hanna, Aug 22 2006, Jan 19 2008

nonn

Also column 1 of square array A136733.

A121416 is the matrix square of triangle A121412; row n of triangle T=A121412 equals row (n-1) of T^(n+1) with an appended '1'.

Cf. A121416 (triangle); other columns: A121418, A121419.

Cf. A136733; A101483, A121421; A121425.

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

Edited by N. J. A. Sloane, Oct 30 2008 at the suggestion of R. J. Mathar

A121413 Column 1 of triangle A121412, in which row n of T equals row (n-1) of T^(n+1) with an appended '1'.

Original entry on oeis.org

1, 1, 4, 30, 335, 4984, 92652, 2065146, 53636520, 1589752230, 52926799310, 1954793723688, 79297921097850, 3504206787532290, 167533486104374420, 8615231103973721610, 474145710046504872894, 27806642356199323970739

Offset: 0

Paul D. Hanna, Aug 22 2006

nonn

Also equals column 3 of triangle A101479.

Cf. A121412 (triangle); other columns: A101483, A121414, A121415; A101479 (triangle).

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

A101481 Column 0 of triangular matrix T=A101479, in which row n equals row (n-1) of T^(n-1) followed by '1'.

Original entry on oeis.org

1, 1, 1, 3, 19, 191, 2646, 46737, 1003150, 25330125, 735180292, 24103027865, 880627477269, 35469795883964, 1561107221731851, 74528004538789830, 3835467005270307663, 211648845813188932595, 12465477924609075602136

Offset: 0

Paul D. Hanna, Jan 21 2005

nonn

From Gerhard Kirchner, Apr 20 2017: (Start)
Also: Let U(n,i,k), k<=i<=n, be a triangular matrix with elements selected as "0" or "1" such that the partial sum of the first m rows is s(m)<=m for 1<=mA101481(n+1) is the number of possible selections.
U(n,i,k)  has r(n) = n*(n+1)/2 elements. There are c(n) = binomial(r(n), n) ways to select n elements, some of which, however, are forbidden, see example. This yields the estimation a(n+1) < c(n).
Derivation of the recurrence:
s(m-1) <= m-1, say s(m-1)= j with 0 <= j <= m-1. Let f(m-1, j) be the number of associated submatrices. In order to determine f(m, k), k>=j, we have to distribute "1" k-j times among the m elements of row number m. There are binomial(m, k-j) ways to do that. The distribution must be repeated for each j. The recurrence describes this procedure. (End)

			G.f. = 1 + x + x^2 + 3*x^3 + 19*x^4 + 191*x^5 + 2646*x^6 + 46737*x^7 + ...
This sequence can also be generated in the following manner.
Start a table with the all 1's sequence in row 0; from then on, row n+1 can be formed from row n by dropping the initial n-1 terms of row n and taking partial sums of the remaining terms to obtain row n+1.
The table below illustrates this method:
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, ...;
[1], 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, ...;
[3, 9], 19, 34, 55, 83, 119, 164, 219, 285, 363, 454, ...;
[19, 53, 108], 191, 310, 474, 693, 978, 1341, 1795, 2354, ...;
[191, 501, 975, 1668], 2646, 3987, 5782, 8136, 11169, 15017, ...;
[2646, 6633, 12415, 20551, 31720], 46737, 66570, 92358, ...; ...;
In the above table, drop the initial n-1 terms in row n (enclosed in square brackets) and then take partial sums to obtain row n+1 for n>=1;
this sequence then forms the first column of the resultant table.
Note: column k of the above table equals column 0 of matrix power T^(k+1) where T=A101479, for k>=0.
From _Gerhard Kirchner_, Apr 20 2017: (Start)
n=3: 0         0        1       forbidden: 1
     0 0       1 0      0 1                1 1
     1 1 1     0 1 1    1 0 1              0 0 0
     s(2)=0    s(2)=1   s(2)=2             s(2)=3>2
c(3) = binomial(6,3) = 20. There is only one forbidden matrix.
Thus: a(n+1) = a(4) = 19
Using the recurrence:
f(2,0) = f(1,0) = 1
f(2,1) = 2*f(1,0) + f(1,1) = 3
a(3) = f(2,2) = f(1,0) + 2*f(1,1) = 3
a(4) = f(3,3) = f(2,0) + 3*f(2,1) + 3*f(2,2) = 19
(End)

Vaclav Kotesovec, Table of n, a(n) for n = 0..300

Cf. A101479, A101482, A101483, A226775.

a[ n_, k_: 1] := a[n, k] = If[ n < 2, Boole[n >= 0], Sum[a[n - 1, i], {i, n + k - 2}]]; (* Michael Somos, Nov 29 2016 *)
f[m_, k_] := f[m, k] = If[(m == 0 && k == 0) || (m == 0 && k == 1) || (m == 1 && k == 0) || (m == 1 && k == 1), 1, Sum[f[m-1, j]*Binomial[m, k-j], {j, 0, m-1}]]; Flatten[{1, Table[f[n-1, n-1], {n, 1, 20}]}] (* Vaclav Kotesovec, Apr 20 2017 after Gerhard Kirchner *)

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

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

From Benedict W. J. Irwin, Nov 29 2016: (Start)
Conjecture: a(n) is described by a series of nested sums,
a(2) = Sum_{i=1..1} 1,
a(3) = Sum_{i=1..1+1}Sum_{j=1..i} 1,
a(4) = Sum_{i=1..1+2}Sum_{j=1..i+1}Sum_{k=1..j} 1,
a(5) = Sum_{i=1..1+3}Sum_{j=1..i+2}Sum_{k=1..j+1}Sum_{l=1..k} 1,
(End)
From Gerhard Kirchner, Apr 20 2017: (Start)
Recurrence: f(m,k) = Sum_{j=0..m-1} f(m-1,j)*binomial(m,k-j) with f(1,0) = f(1,1)= 1. a(n+1) = f(n,n). (End)
a(n) ~ c * exp(n) * n^(n-3/2) / 2^n, where c = (2 + LambertW(-2*exp(-2))) / (exp(2) * sqrt(2*Pi)) = 0.08604131405842589281435... - Vaclav Kotesovec, Apr 20 2017, updated Dec 03 2017

A101482 Column 1 of triangular matrix T=A101479, in which row n equals row (n-1) of T^(n-1) followed by '1'.

Original entry on oeis.org

1, 1, 2, 9, 70, 795, 11961, 224504, 5051866, 132523155, 3969912160, 133678842902, 4997280555576, 205320100093953, 9195224163850830, 445775353262707365, 23255990676521697670, 1299028117862237432959, 77348967890083608924045

Offset: 0

Paul D. Hanna, Jan 21 2005

nonn

Number of Dyck paths whose ascent lengths are exactly {n, n-1, .. 1}, for example the a(2) = 2 paths are uududd and uuddud. - David Scambler, May 30 2012

			This sequence can also be generated in the following manner.
Start a table with the all 1's sequence in row 0; from then on, row n+1 can be formed from row n by dropping the initial n terms of row n and taking partial sums of the remaining terms to obtain row n+1.
The following table (A136730) illustrates this method:
  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, ...;
  [2, 5], 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104, ...;
  [9, 23, 43], 70, 105, 149, 203, 268, 345, 435, 539, 658, ...;
  [70, 175, 324, 527], 795, 1140, 1575, 2114, 2772, 3565, ...;
  [795, 1935, 3510, 5624, 8396], 11961, 16471, 22096, 29025, ...;
  [11961, 28432, 50528, 79553, 117020, 164672], 224504, ...; ...
In the above table, drop the initial n terms in row n (enclosed in square brackets) and then take partial sums to obtain row n+1 for n>=0;
this sequence then forms the first column of the resultant table.
Note: column k of the above table equals column 1 of matrix power T^(k+1) where T=A101479, for k>=0.

Cf. A101479, A101481, A101483, A136730.

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

Equals column 0 of array A136730.

A121421 Column 0 of triangle A121420.

Original entry on oeis.org

1, 3, 12, 76, 711, 9054, 147471, 2938176, 69328365, 1891371807, 58575539361, 2030011517685, 77827890696820, 3270046577551695, 149407542447596319, 7374639622066056408, 391044078030333899385, 22168014954558449549349

Offset: 0

Paul D. Hanna, Aug 23 2006

nonn

Also column 2 of square array A136733.

A121420 is the matrix cube of triangle A121412; row n of triangle T=A121412 equals row (n-1) of T^(n+1) with an appended '1'.

Cf. A121420 (triangle); other columns: A121422, A121423.

Cf. A136733; A101483, A121418; A121425.

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

Edited by N. J. A. Sloane, Oct 30 2008 at the suggestion of R. J. Mathar

A121414 Column 2 of triangle A121412, in which row n of T=A121412 equals row (n-1) of T^(n+1) with an appended '1'.

Original entry on oeis.org

1, 1, 5, 45, 581, 9730, 199692, 4843125, 135345925, 4278317373, 150818840250, 5863215069621, 249105031449435, 11480173020040450, 570303168053225908, 30375972794764190385, 1726700205634807475115, 104332294453480284687895

Offset: 0

Paul D. Hanna, Aug 22 2006

nonn

Also equals column 4 of triangle A101479.

Cf. A121412 (triangle); other columns: A101483, A121413, A121415; A101479 (triangle).

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

A121425 Main diagonal of rectangular table A121424.

Original entry on oeis.org

1, 2, 12, 118, 1605, 27816, 585046, 14459138, 410368743, 13146830110, 469123986529, 18447791712945, 792514583941223, 36925394368325295, 1854525584914459755, 99872579714406393286, 5740977285851988017769

Offset: 0

Paul D. Hanna, Aug 26 2006

nonn

Also main diagonal of square array A136733.

Cf. A121424, A121412.

Cf. A136733; A101483, A121418, A121421.

{a(n)=local(H=Mat(1), B); for(m=1, n+1, B=matrix(m, m); for(i=1, m, for(j=1, i, if(j==i, B[i, j]=1, B[i, j]=(H^i)[i-1, j]); )); H=B); return((H^(n+1))[n+1, 1])}

a(n) = [A121412^(n+1)](n,0) for n>=0; i.e., (n+1)-th term of column 0 in matrix power A121412^(n+1).

Edited by N. J. A. Sloane, Oct 30 2008 at the suggestion of R. J. Mathar

A121424 Rectangular table, read by antidiagonals, where row n is equal to column 0 of matrix power A121412^(n+1) for n>=0.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 7, 18, 1, 4, 12, 43, 170, 1, 5, 18, 76, 403, 2220, 1, 6, 25, 118, 711, 5188, 37149, 1, 7, 33, 170, 1107, 9054, 85569, 758814, 1, 8, 42, 233, 1605, 13986, 147471, 1725291, 18301950, 1, 9, 52, 308, 2220, 20171, 225363, 2938176, 41145705

Offset: 0

Paul D. Hanna, Aug 26 2006

			Table of column 0 in matrix powers of triangle H=A121412 begins:
H^1: 1, 1, 3, 18, 170, 2220, 37149, 758814, 18301950,...
H^2: 1, 2, 7, 43, 403, 5188, 85569, 1725291, 41145705,...
H^3: 1, 3, 12, 76, 711, 9054, 147471, 2938176, 69328365,...
H^4: 1, 4, 18, 118, 1107, 13986, 225363, 4441557, 103755660,...
H^5: 1, 5, 25, 170, 1605, 20171, 322075, 6285390, 145453290,...
H^6: 1, 6, 33, 233, 2220, 27816, 440785, 8526057, 195579123,...
H^7: 1, 7, 42, 308, 2968, 37149, 585046, 11226958, 255436293,...
H^8: 1, 8, 52, 396, 3866, 48420, 758814, 14459138, 326487241,...
H^9: 1, 9, 63, 498, 4932, 61902, 966477, 18301950, 410368743,...
Rearrangement of the upper half of the table forms A121430, which is
the number of subpartitions of partition [0,1,1,2,2,2,3,3,3,3,4,...]:
1, 1,2, 3,7,12, 18,43,76,118, 170,403,711,1107,1605, 2220,...

Cf. A121425 (diagonal), A121430; rows: A101483, A121418, A121421; related tables: A121426, A121428; related triangles: A121412, A121416, A121420.

{T(n,k)=local(H=Mat(1), B); for(m=1, k+1, B=matrix(m, m); for(i=1, m, for(j=1, i, if(j==i, B[i, j]=1, B[i, j]=(H^i)[i-1, j]); )); H=B); return((H^(n+1))[k+1, 1])}

A136733 Square array, read by antidiagonals, where T(n,k) = T(n,k-1) + T(n-1,k+n) for n>0, k>0, such that T(n,0) = T(n-1,n) for n>0 with T(0,k)=1 for k>=0.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 18, 7, 3, 1, 170, 43, 12, 4, 1, 2220, 403, 76, 18, 5, 1, 37149, 5188, 711, 118, 25, 6, 1, 758814, 85569, 9054, 1107, 170, 33, 7, 1, 18301950, 1725291, 147471, 13986, 1605, 233, 42, 8, 1, 508907970, 41145705, 2938176, 225363, 20171, 2220, 308

Offset: 0

Paul D. Hanna, Jan 19 2008

			Square array begins:
(1), 1, 1,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,20,21,22,23,24,...;
(3,7,12), 18, 25,33,42,52,63,75,88,102,117,133,150,168,187,207,228,...;
(18,43,76,118), 170, 233,308,396,498,615,748,898,1066,1253,1460,...;
(170,403,711,1107,1605), 2220, 2968,3866,4932,6185,7645,9333,11271,...;
(2220,5188,9054,13986,20171,27816), 37149, 48420,61902,77892,96712,...;
(37149,85569,147471,225363,322075,440785,585046), 758814, 966477,...;
(758814,1725291,2938176,4441557,6285390,8526057,11226958,14459138), ...;
where the rows are generated as follows.
Start row 0 with all 1's; from then on,
remove the first n+1 terms (shown in parenthesis) from row n
and then take partial sums to yield row n+1.
Note the first upper diagonal forms column 0 and equals A101483:
[1,1,3,18,170,2220,37149,758814,18301950,508907970,16023271660,...]
which equals column 2 of triangle A101479:
1;
1, 1;
1, 1, 1;
3, 2, 1, 1;
19, 9, 3, 1, 1;
191, 70, 18, 4, 1, 1;
2646, 795, 170, 30, 5, 1, 1;
46737, 11961, 2220, 335, 45, 6, 1, 1;
1003150, 224504, 37149, 4984, 581, 63, 7, 1, 1; ...
where row n equals row (n-1) of T^(n-1) with appended '1'.

Cf. A101479; columns: A101483, A121418, A121421; A121425 (main diagonal); variants: A136730, A136737.

{T(n,k)=if(k<0,0,if(n==0,1,T(n,k-1) + T(n-1,k+n)))}

cp's OEIS Frontend

A101479 Triangular matrix T, read by rows, where row n equals row (n-1) of T^(n-1) after appending '1' for the main diagonal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

A121418 Column 0 of triangle A121416.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A121413 Column 1 of triangle A121412, in which row n of T equals row (n-1) of T^(n+1) with an appended '1'.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A101481 Column 0 of triangular matrix T=A101479, in which row n equals row (n-1) of T^(n-1) followed by '1'.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A101482 Column 1 of triangular matrix T=A101479, in which row n equals row (n-1) of T^(n-1) followed by '1'.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A121421 Column 0 of triangle A121420.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Extensions

A121414 Column 2 of triangle A121412, in which row n of T=A121412 equals row (n-1) of T^(n+1) with an appended '1'.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A121425 Main diagonal of rectangular table A121424.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula