A107354 -id:A107354 - cp's OEIS frontend

A355576 Number A(n,k) of n-tuples (p_1, p_2, ..., p_n) of positive integers such that p_{i-1} <= p_i <= k^(i-1); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 3, 7, 1, 0, 1, 1, 4, 24, 44, 1, 0, 1, 1, 5, 58, 541, 516, 1, 0, 1, 1, 6, 115, 3236, 35649, 11622, 1, 0, 1, 1, 7, 201, 12885, 713727, 6979689, 512022, 1, 0, 1, 1, 8, 322, 39656, 7173370, 627642640, 4085743032, 44588536, 1, 0

Offset: 0

Alois P. Heinz, Jul 07 2022

			A(2,3) = 3: (1,1), (1,2), (1,3).
A(3,2) = 7: (1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,2,2), (1,2,3), (1,2,4).
A(3,3) = 24: (1,1,1), (1,1,2), (1,1,3), (1,1,4), (1,1,5), (1,1,6), (1,1,7), (1,1,8), (1,1,9), (1,2,2), (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,2,7), (1,2,8), (1,2,9), (1,3,3), (1,3,4), (1,3,5), (1,3,6), (1,3,7), (1,3,8), (1,3,9).
Square array A(n,k) begins:
  1, 1,     1,       1,         1,           1,            1, ...
  1, 1,     1,       1,         1,           1,            1, ...
  0, 1,     2,       3,         4,           5,            6, ...
  0, 1,     7,      24,        58,         115,          201, ...
  0, 1,    44,     541,      3236,       12885,        39656, ...
  0, 1,   516,   35649,    713727,     7173370,     46769781, ...
  0, 1, 11622, 6979689, 627642640, 19940684251, 330736663032, ...

Alois P. Heinz, Antidiagonals n = 0..43, flattened

Columns k=1-9 give: A000012, A107354, A109055, A109056, A109057, A109058, A109059, A109060, A109061.
Rows n=1-4 give: A000012, A001477, A081436(k-1) for k>0, A354608.
Main diagonal gives A355561.

A:= proc(n, k) option remember; `if`(n=0, 1, -add(
      A(j, k)*(-1)^(n-j)*binomial(k^j, n-j), j=0..n-1))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

A[n_, k_] := A[n, k] = If[n==0, 1, -Sum[A[j, k]*(-1)^(n-j)*Binomial[If[j==0, 1, k^j], n-j], {j, 0, n-1}]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Sep 21 2022, after Alois P. Heinz *)

A109055 To compute a(n) we first write down 3^n 1's in a row. Each row takes the rightmost 3rd part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 3rd part. The single element in the last row is a(n).

Original entry on oeis.org

1, 1, 3, 24, 541, 35649, 6979689, 4085743032, 7166723910237, 37698139930450365, 594816080266215640710, 28154472624850002001979592, 3997853576535778666975681355079, 1703042427700923785323670557504832751, 2176429411666209822350337722381643148477248

Offset: 0

Augustine O. Munagi, Jun 17 2005

nonn

Comment from Franklin T. Adams-Watters, Jul 13 2006: This is the number of subpartitions of the sequence 3^n-1. As such it can also be computed adding forward, with 3^n terms in the n-th line:
..........................................................................
1 1.......................................................................
2.3.3..3..3..3..3..3......................................................
3.6.9.12.15.18.21.24.24.24.24.24.24.24.24.24.24.24.24.24.24.24.24.24.24.24

			For example, for n=3 the array looks like this:
1..1..1..1..1........1..1..1..1..1..1..1..1..1..1
........................1..2..3..4..5..6..7..8..9
..........................................7.15.24
...............................................24
Therefore a(3)=24.

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

Cf. A107354, A109056, A109057, A109058, A109059, A109060, A109061, A109062.
Cf. A115728, A115729.
Column k=3 of A355576.

proc(n::nonnegint) local f,a; if n=0 or n=1 then return 1; end if; f:=L->[seq(add(L[i],i=2*nops(L)/3+1..j),j=2*nops(L)/3+1..nops(L))]; a:=f([seq(1,j=1..3^n)]); while nops(a)>3 do a:=f(a) end do; a[3]; end proc;

A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[A[j, k]*(-1)^(n - j)*Binomial[If[j == 0, 1, k^j], n - j], {j, 0, n - 1}]];
a[n_] := A[n, 3];
Table[a[n], {n, 0, 14}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A355576 *)

More terms from Paul D. Hanna

A109061 To compute a(n) we first write down 9^n 1's in a row. Each row takes the rightmost 9th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 9th part. The single element in the last row is a(n).

Original entry on oeis.org

1, 1, 9, 693, 476121, 2940705927, 163444130390781, 81756588582353417271, 368059416198072536171078649, 14912674110246473369128526689667934, 5437955149300119215042866669813503145575607, 17846712348533391270843269203829434120473501691723788

Offset: 0

Augustine O. Munagi, Jun 17 2005

nonn

			For example, for n=3 the array, from 2nd row, follows:
1..2..3.....70..71..72..73..74..75..76..77..78..79..80..81
........................73.147.222.298.375.453.532.612.693
.......................................................693
Therefore a(3)=693.

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

Cf. A107354, A109055, A109056, A109057, A109058, A109059, A109060, A109062.

Column k=9 of A355576.

proc(n::nonnegint) local f,a; if n=0 or n=1 then return 1; end if; f:=L->[seq(add(L[i],i=8*nops(L)/9+1..j),j=8*nops(L)/9+1..nops(L))]; a:=f([seq(1,j=1..9^n)]); while nops(a)>9 do a:=f(a) end do; a[9]; end proc;

A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[A[j, k]*(-1)^(n - j)* Binomial[If[j == 0, 1, k^j], n - j], {j, 0, n - 1}]];
a[n_] := A[n, 9];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A355576 *)

More terms from Alois P. Heinz, Jul 06 2022

A109056 To compute a(n) we first write down 4^n 1's in a row. Each row takes the rightmost 4th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 4th part. The single element in the last row is a(n).

Original entry on oeis.org

1, 1, 4, 58, 3236, 713727, 627642640, 2205897096672, 31004442653082720, 1743005531132374350208, 391947224244531572312436328, 352545281714327012273215572739472, 1268416358395092955994185170741834144224, 18254446075150458724007419019753847268167282688

Offset: 0

Augustine O. Munagi, Jun 17 2005

nonn

			For example, for n=3 the array looks like this:
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
...............................................13.27.42.58
........................................................58
Therefore a(4)=58.

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

Cf. A107354, A109055, A109057, A109058, A109059, A109060, A109061.

Column k=4 of A355576.

proc(n::nonnegint) local f,a; if n=0 or n=1 then return 1; end if; f:=L->[seq(add(L[i],i=3*nops(L)/4+1..j),j=3*nops(L)/4+1..nops(L))]; a:=f([seq(1,j=1..4^n)]); while nops(a)>4 do a:=f(a) end do; a[4]; end proc;

A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[A[j, k]*(-1)^(n - j)* Binomial[If[j == 0, 1, k^j], n - j], {j, 0, n - 1}]];
a[n_] := A[n, 4];
Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A355576 *)

More terms from Alois P. Heinz, Jul 06 2022

A109057 To compute a(n) we first write down 5^n 1's in a row. Each row takes the rightmost 5th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 5th part. The single element in the last row is a(n).

Original entry on oeis.org

1, 1, 5, 115, 12885, 7173370, 19940684251, 277078842941900, 19249144351745111125, 6686277384080730564862875, 11612516024884420913314995604000, 100841213012622614260440382077516990500, 4378443591626306255827149380635713364079323075

Offset: 0

Augustine O. Munagi, Jun 17 2005

nonn

			For example, for n=3 the array, from 2nd row, follows:
1..2..3.....14..15..16..17..18..19..20..21..22..23..24..25
........................................21..43..66..90.115
.......................................................115
Therefore a(3)=115.

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

Cf. A107354, A109055, A109056, A109058, A109059, A109060, A109061, A109062.

Column k=5 of A355576.

proc(n::nonnegint) local f,a; if n=0 or n=1 then return 1; end if; f:=L->[seq(add(L[i],i=4*nops(L)/5+1..j),j=4*nops(L)/5+1..nops(L))]; a:=f([seq(1,j=1..5^n)]); while nops(a)>5 do a:=f(a) end do; a[5]; end proc;

A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[A[j, k]*(-1)^(n - j)* Binomial[If[j == 0, 1, k^j], n - j], {j, 0, n - 1}]];
a[n_] := A[n, 5];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 02 2024, after Alois P. Heinz in A355576 *)

More terms from Alois P. Heinz, Jul 06 2022

A109058 To compute a(n) we first write down 6^n 1's in a row. Each row takes the rightmost 6th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 6th part. The single element in the last row is a(n).

Original entry on oeis.org

1, 1, 6, 201, 39656, 46769781, 330736663032, 14031372754200653, 3571582237574150514024, 5454701025672508908169570740, 49984143782624329482858175943128416, 2748177454593265010973723857947479180947553, 906585004703475512437226615670665677815744239819376

Offset: 0

Augustine O. Munagi, Jun 17 2005

nonn

			For example, for n=3 the array, from 2nd row, follows:
1..2..3.....25..26..27..28..29..30..31..32..33..34..35..36
....................................31..63..96.130.165.201
.......................................................201
Therefore a(3)=201.

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

Cf. A107354, A109055, A109056, A109057, A109059, A109060, A109061, A109062.

Column k=6 of A355576.

proc(n::nonnegint) local f,a; if n=0 or n=1 then return 1; end if; f:=L->[seq(add(L[i],i=5*nops(L)/6+1..j),j=5*nops(L)/6+1..nops(L))]; a:=f([seq(1,j=1..6^n)]); while nops(a)>6 do a:=f(a) end do; a[6]; end proc;

A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[A[j, k]*(-1)^(n - j)* Binomial[If[j == 0, 1, k^j], n - j], {j, 0, n - 1}]];
a[n_] := A[n, 6];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A355576 *)

More terms from Alois P. Heinz, Jul 06 2022

A109059 To compute a(n) we first write down 7^n 1's in a row. Each row takes the rightmost 7th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 7th part. The single element in the last row is a(n).

Original entry on oeis.org

1, 1, 7, 322, 102249, 226742516, 3518406903403, 382149784071841422, 290546585470549214822793, 1546306129153609960601346281449, 57606719909341067627899562630623352149, 15022729501707009545842655841005666468590455864, 27423481304702360472157221630747597794702587610760693525

Offset: 0

Augustine O. Munagi, Jun 17 2005

nonn

			For example, for n=3 the array, from 2nd row, follows:
1..2..3.....38..39..40..41..42..43..44..45..46..47..48..49
................................43..87.132.178.225.273.322
.......................................................322
Therefore a(3)=322.

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

Cf. A107354, A109055, A109056, A109057, A109058, A109060, A109061, A109062.

Column k=7 of A355576.

proc(n::nonnegint) local f,a; if n=0 or n=1 then return 1; end if; f:=L->[seq(add(L[i],i=6*nops(L)/7+1..j),j=6*nops(L)/7+1..nops(L))]; a:=f([seq(1,j=1..7^n)]); while nops(a)>7 do a:=f(a) end do; a[7]; end proc;

A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[A[j, k]*(-1)^(n - j)* Binomial[If[j == 0, 1, k^j], n - j], {j, 0, n - 1}]];
a[n_] := A[n, 7];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 01 2024, after_Alois P. Heinz_ in A355576 *)

More terms from Alois P. Heinz, Jul 06 2022

A109060 To compute a(n) we first write down 8^n 1's in a row. Each row takes the rightmost 8th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 8th part. The single element in the last row is a(n).

Original entry on oeis.org

1, 1, 8, 484, 231736, 886208954, 27106585594040, 6632714300472863716, 12983632019302863224103688, 203325054125533158416534341556735, 25472733809776289439071490656049076425792, 25529963965104465687252347321830255523307055463168

Offset: 0

Augustine O. Munagi, Jun 17 2005

nonn

			For example, for n=3 the array, from 2nd row, follows:
1..2..3.....53..54..55..56..57..58..59..60..61..62..63..64
............................57.115.174.234.295.357.420.484
.......................................................484
Therefore a(3)=484.

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

Cf. A107354, A109055, A109056, A109057, A109058, A109059, A109061, A109062.

Column k=8 of A355576.

proc(n::nonnegint) local f,a; if n=0 or n=1 then return 1; end if; f:=L->[seq(add(L[i],i=7*nops(L)/8+1..j),j=7*nops(L)/8+1..nops(L))]; a:=f([seq(1,j=1..8^n)]); while nops(a)>8 do a:=f(a) end do; a[8]; end proc;

A[n_, k_] := A[n, k] = If[n == 0, 1, -Sum[A[j, k]*(-1)^(n - j)* Binomial[If[j == 0, 1, k^j], n - j], {j, 0, n - 1}]];
a[n_] := A[n, 8];
Table[a[n], {n, 0, 12}] (* Jean-François Alcover, Apr 01 2024, after Alois P. Heinz in A355576 *)

More terms from Alois P. Heinz, Jul 06 2022

A136502 Matrix inverse of triangle A136501, read by rows.

Original entry on oeis.org

1, -1, 1, 2, -2, 1, -7, 7, -4, 1, 44, -44, 26, -8, 1, -516, 516, -308, 100, -16, 1, 11622, -11622, 6959, -2296, 392, -32, 1, -512022, 512022, -306888, 101754, -17712, 1552, -64, 1, 44588536, -44588536, 26732904, -8877272, 1554404, -139104, 6176, -128, 1

Offset: 0

Paul D. Hanna, Jan 01 2008

			Triangle begins:
1;
-1, 1;
2, -2, 1;
-7, 7, -4, 1;
44, -44, 26, -8, 1;
-516, 516, -308, 100, -16, 1;
11622, -11622, 6959, -2296, 392, -32, 1;
-512022, 512022, -306888, 101754, -17712, 1552, -64, 1;
44588536, -44588536, 26732904, -8877272, 1554404, -139104, 6176, -128, 1;

Cf. A107354 (column 0), A136503 (column 2), A136504 (row sums) ; A136501 (matrix inverse).

{T(n,k)=local(M=matrix(n+1,n+1,r,c,binomial(2^(c-1),r-c)));(M^-1)[n+1,k+1]}

G.f. for column k: 1 = Sum_{n>=0} T(n+k,k)*x^n*(1+x)^(2^(n+k)).

A355519 Number of valid brackets in an n-round tournament.

Original entry on oeis.org

1, 2, 5, 19, 123, 1457, 32924, 1452015, 126487061, 21898598245, 7558601003617, 5209629536999054, 7175576970776253311, 19758953061561609438197, 108796404018098314291373545, 1197986411771818785507163602609, 26381385902615283298043180284145933

Offset: 0

John P. D'Angelo, Jul 05 2022

nonn

a(n) is the number of nonnegative n-tuples (x_1, ..., x_n) satisfying the inequalities x_1 <= 2^(n-1) and x_{j+1} <= min(x_j, 2^(n-j-1)) for all j.

			For n=1, we have a(n)=2, because the only 1-tuples are 0 and 1.
For n=2, we have a(2)=5, as the possible 2-tuples are (2,1), (2,0), (1,1), (1,0), (0,0).
For n=3, there are 19 possibilities: (4,2,1), (4,2,0), (4,1,1), (4,1,0), (4,0,0), (3,2,1), (3,2,0), (3,1,1), (3,1,0), (3,0,0), (2,2,1), (2,2,0), (2,1,1), (2,1,0), (2,0,0), (1,1,0), (1,0,0), (0,0,0).

John P. D'Angelo, Counting Bracket Tournaments, to appear in Journal of Integer Sequences. [The first 26 terms appear there together with a method for computing them.]

Alois P. Heinz, Table of n, a(n) for n = 0..82
John P. D'Angelo and Jiri Lebl, Integer Sequences and Output Arrays, arXiv:2208.09544 [math.NT], 2022.
John P. D'Angelo, Counting Tournament Brackets, J. Int. Seq., Vol. 25 (2022), Article 22.6.8.

Cf. A000108, A107354.

b:= proc(n, i) option remember; `if`(n=0, 1,
      add(b(n-1, j), j=0..min(i, 2^(n-1))))
    end:
a:= n-> b(n, infinity):
seq(a(n), n=0..14);  # Alois P. Heinz, Jul 05 2022
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, -add(a(j)
      *(-1)^(n-j)*binomial(1+ 2^j, n-j), j=0..n-1))
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Jul 08 2022

a[n_] := a[n] = If[n == 0, 1, -Sum[a[j]*(-1)^(n-j)*Binomial[1+2^j, n-j], {j, 0, n-1}]];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Jul 01 2025, after Alois P. Heinz *)

from functools import cache
@cache
def b(n, i): return 1 if n==0 else sum(b(n-1, j) for j in range(min(i, 2**(n-1))+1))
def a(n): return b(n, float('inf'))
print([a(n) for n in range(15)]) # Michael S. Branicky, Jul 05 2022 after Alois P. Heinz

a(n) = Sum_{j=0..n-1} a(j)*(-1)^(n-j+1)*binomial(2^j+1,n-j) with a(0) = 1. - Alois P. Heinz, Jul 08 2022

cp's OEIS Frontend

A355576 Number A(n,k) of n-tuples (p_1, p_2, ..., p_n) of positive integers such that p_{i-1} <= p_i <= k^(i-1); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A109055 To compute a(n) we first write down 3^n 1's in a row. Each row takes the rightmost 3rd part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 3rd part. The single element in the last row is a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A109061 To compute a(n) we first write down 9^n 1's in a row. Each row takes the rightmost 9th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 9th part. The single element in the last row is a(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A109056 To compute a(n) we first write down 4^n 1's in a row. Each row takes the rightmost 4th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 4th part. The single element in the last row is a(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A109057 To compute a(n) we first write down 5^n 1's in a row. Each row takes the rightmost 5th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 5th part. The single element in the last row is a(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A109058 To compute a(n) we first write down 6^n 1's in a row. Each row takes the rightmost 6th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 6th part. The single element in the last row is a(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A109059 To compute a(n) we first write down 7^n 1's in a row. Each row takes the rightmost 7th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 7th part. The single element in the last row is a(n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A109060 To compute a(n) we first write down 8^n 1's in a row. Each row takes the rightmost 8th part of the previous row and each element in it equals sum of the elements of the previous row starting with the first of the rightmost 8th part. The single element in the last row is a(n).

Views