A001453 -id:A001453 - cp's OEIS frontend

A132892 Square array T(m,n) read by antidiagonals; T(m,n) is the number of equivalence classes in the set of sequences of n nonnegative integers that sum to m, generated by the equivalence relation defined in the following manner: we write a sequence in the form a[1]0a[2]0...0a[p], where each a[i] is a (possibly empty) sequence of positive integers; two sequences in this form, a[1]0a[2]0...0a[p] and b[1]0b[2]0...0b[q] are said to be equivalent if p=q and b[1],b[2],...,b[q] is a cyclic permutation of a[1],a[2],...a[p].

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 3, 1, 1, 5, 9, 7, 4, 1, 1, 6, 13, 14, 10, 4, 1, 1, 7, 19, 25, 22, 12, 5, 1, 1, 8, 25, 41, 42, 30, 15, 5, 1, 1, 9, 33, 63, 79, 66, 43, 19, 6, 1, 1, 10, 41, 92, 131, 132, 99, 55, 22, 6, 1, 1, 11, 51, 129, 213, 245, 217, 143, 73, 26, 7, 1, 1, 12, 61, 175, 325, 428, 429, 335, 201, 91, 31, 7, 1

Offset: 1

Emeric Deutsch and Ira M. Gessel, Oct 02 2007

T(n,n) = A000108(n) (the Catalan numbers; see R. P. Stanley, Catalan addendum, problem starting "Equivalence classes of the equivalence relation ..."). T(m,m+1) = A007595(m+1); T(m,m+2) = A003441(m+1); T(m,m+3) = A003444(m+3); T(n+2,n) = A001453(n+1) (Catalan numbers - 1); T(m,1)=1; T(m,2)=m; T(m,3) = A080827(m) = A099392(m+1); T(m,4) = A004006(m).

			T(2,4) = 3 because we have {2000, 0200, 0020, 0002}, {1100, 0110, 0011} and {1010, 0101, 1001}.
T(4,2) = 4 because we have {40, 04}, {31}, {13} and {22}.
The square array starts:
  1....1.....1.....1......1.....1.....1...
  1....2.....3.....3......4.....4.....5...
  1....3.....5.....7.....10....12....15...
  1....4.....9....14.....22....30....43...
  1....5....13....25.....42....66....99...

Alois P. Heinz, antidiagonals n = 1..200, flattened
Emeric Deutsch and Ira Gessel, Equivalence Classes and Cyclic Arrangements:Problem 10525, Amer. Math. Monthly, 105, No. 8, 1998, 774-775 (published solution by D. Beckwith).
R. P. Stanley, Catalan addendum. See the interpretation (www, "Vertices of height n-1 of the tree T ...").

Cf. A000108, A007595, A003441, A003444, A001453, A080827, A099392, A004006.

with(numtheory): T:=proc(m,n) local r, div, N: r:=igcd(m,n+1): div:=divisors(r): N:=nops(div): (sum(phi(div[j])*(binomial((m+n+1)/div[j]-1,(n+1)/div[j]-1) -binomial(m/div[j]-1,(n+1)/div[j]-1)),j=1..N))/(n+1) end proc: for m to 12 do seq(T(m, n),n=1..12) end do; # yields the upper left 12 by 12 block of the infinite matrix T(m,n)
# second Maple program:
T:= proc(m, n) uses numtheory; (C-> add(phi(d)*(C((m+n+1)/d-1, (n+1)/d-1)
      -C(m/d-1, (n+1)/d-1))/(n+1), d=divisors(igcd(m, n+1))))(binomial)
    end:
seq(seq(T(1+d-n, n), n=1..d), d=1..14);  # Alois P. Heinz, Jan 28 2025

T[m_, n_] := Module[{r, div, N}, r = GCD[m, n + 1]; div = Divisors[r]; N = Length[div]; (Sum[EulerPhi[div[[j]]]*(Binomial[(m + n + 1)/div[[j]] - 1, (n + 1)/div[[j]] - 1] - Binomial[m/div[[j]] - 1, (n + 1)/div[[j]] - 1]), {j, 1, N}])/(n + 1)];
Table[T[m - n + 1, n], {m, 1, 13}, {n, 1, m}] // Flatten (* Jean-François Alcover, Sep 01 2024, after Maple program *)

T(m,n) = Sum_{d | gcd(m,n+1)} phi(d)*(C((m+n+1)/d-1, (n+1)/d-1) - C(m/d-1, (n+1)/d-1))/(n+1). [corrected by Jason Yuen, Jan 28 2025]

A276986 Numbers n for which there is a permutation p of (1,2,3,...,n) such that k+p(k) is a Catalan number for 1<=k<=n.

Original entry on oeis.org

0, 1, 3, 4, 9, 10, 12, 13, 28, 29, 31, 32, 37, 38, 40, 41, 90, 91, 93, 94, 99, 100, 102, 103, 118, 119, 121, 122, 127, 128, 130, 131, 297, 298, 300, 301, 306, 307, 309, 310, 325, 326, 328, 329, 334, 335, 337, 338, 387, 388, 390, 391, 396, 397, 399, 400, 415, 416

Offset: 1

Gary E. Davis, Sep 24 2016

nonn

A001453 is a subsequence. - Altug Alkan, Sep 29 2016

n>=1 is in the sequence if and only if there is a Catalan number c such that c/2 <= n < c and c-n-1 is in the sequence. - Robert Israel, Nov 20 2016

			3 is in the sequence because the permutation (1,3,2) added termwise to (1,2,3) yields (2,5,5) and both 2 and 5 are Catalan numbers.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A000108, A073364.

S:= {0}:
for i from 1 to 8 do
  c:= binomial(2*i,i)/(i+1);
  S:= S union map(t -> c - t - 1, S);
od:
sort(convert(S,list)); # Robert Israel, Nov 20 2016

CatalanTo[n0_] :=
Module[{n = n0}, k = 1; L = {};
  While[CatalanNumber[k] <= 2*n, L = {L, CatalanNumber[k]}; k++];
  L = Flatten[L]]
perms[n0_] := Module[{n = n0, S, func, T, T2},
  func[k_] := Cases[CatalanTo[n], x_ /; 1 <= x - k <= n] - k;
  T = Tuples[Table[func[k], {k, 1, n}]];
  T2 = Cases[T, x_ /; Length[Union[x]] == Length[x]];
  Length[T2]]
Select[Range[41], perms[#] > 0 &]

a(i) + a(2^n+1-i) = A000108(n+1)-1 for 1<=i<=2^n. - Robert Israel, Nov 20 2016

More terms from Alois P. Heinz, Sep 28 2016

a(23)-a(58) from Robert Israel, Nov 18 2016

A283054 Triangle read by rows: T(n,k) = T(n,k-1) + T(n-1,k), T(n,0)=1, T(n,n) = T(n,n-1) + 1.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 4, 8, 9, 1, 5, 13, 22, 23, 1, 6, 19, 41, 64, 65, 1, 7, 26, 67, 131, 196, 197, 1, 8, 34, 101, 232, 428, 625, 626, 1, 9, 43, 144, 376, 804, 1429, 2055, 2056, 1, 10, 53, 197, 573, 1377, 2806, 4861, 6917, 6918, 1, 11, 64, 261, 834, 2211, 5017, 9878, 16795, 23713, 23714, 1, 12, 76, 337, 1171, 3382, 8399, 18277, 35072, 58785, 82499, 82500

Offset: 0

Ely Golden, Feb 27 2017

The left diagonals form polynomial sequences. This is due to the observation that diagonal 0 D_0(x) = 1, and D_n(x) = D_n(x-1)+D_(n-1)(x+1), with D_n(-1) = 1 which is a recurrence that can be solved.
These polynomials begin 1, x+2, (x(x+7)+8)/2, (x(x(x+15)+62)+54)/6, (x(x(x(x+26)+227)+730)+552)/24, etc., the first 3 of which correspond to A000012(n), A000027(n+2), and A034856(n+2), respectively.
The rightmost diagonal appears to follow A014137(n). The second rightmost appears to follow A014138(n+1), the third appears to follow A001453(n+2), the fourth appears to follow A114277(n), and the fifth appears to follow A143955(n+3).
A closed-form formula for T(n,k) would be very desirable.

			First 7 rows:
  1;
  1,   2;
  1,   3,   4;
  1,   4,   8,   9;
  1,   5,  13,  22,  23;
  1,   6,  19,  41,  64,  65;
  1,   7,  26,  67, 131, 196, 197;

Ely Golden, Rows n = 0..124 of triangle, flattened
Ely Golden, Java program for generating the triangle
Ely Golden, Sage program for computing the polynomial of the n-th left diagonal

T[0, 0] = 1; T[n_, k_] := T[n, k] = Which[k == 0, 1, k == n, T[n, n - 1] + 1, True, T[n, k - 1] + T[n - 1, k]]; Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Michael De Vlieger, Feb 27 2017 *)

T(n,k)=if(k==0,return(1));if(k==n,return(T(n,n-1)+1));T(n,k-1)+T(n-1,k)
for(n=0,10,for(k=0,n,print1(T(n,k),", "))) \\ Derek Orr, Feb 28 2017

def sideTriangleAt(a,b):
    if(b==0): return 1
    elif(b==a): return sideTriangleAt(a,b-1)+1
    else: return sideTriangleAt(a,b-1)+sideTriangleAt(a-1,b)
def sideTriangle(size):
    li=[]
    for c in range(size):
        for d in range(c+1):
            if(d==0): li.append([1])
            elif(d==c): li[c].append(li[c][d-1]+1)
            else: li[c].append(li[c][d-1]+li[c-1][d])
    return li
trig=sideTriangle(125)
for c in range(len(trig)):
    print(str(trig[c])[1:-1].replace(",",""))

A247502 Triangle read by rows: coefficients of polynomials related to the exponential generating function of sequences generated by Narayana polynomials evaluated at the integers; n>=1, 0<=k

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 13, 9, 1, 1, 41, 57, 16, 1, 1, 131, 320, 165, 25, 1, 1, 428, 1711, 1420, 380, 36, 1, 1, 1429, 8967, 11151, 4620, 756, 49, 1, 1, 4861, 46663, 83202, 49665, 12306, 1358, 64, 1, 1, 16795, 242634, 602407, 495327, 172893, 28476, 2262, 81, 1

Offset: 1

Peter Luschny, Nov 18 2014

Definition: Let N(n,x) = Sum_{j=0..n-1} x^j*C(n,j)^2*(n-j)/(n*(j+1)) for n>0 and N(0,x) = 1, further let p(n,x) be implicitly defined by N(n,k) = k!*[x^k](exp(x)*p(n,x)), then T(n,k) = [x^k] p(n,x).

			Triangle T(n,k) begins:
[n\k][0,    1,     2,     3,     4,     5,    6,  8, 9]
[1]   1,
[2]   1,    1,
[3]   1,    4,     1,
[4]   1,   13,     9,     1,
[5]   1,   41,    57,    16,     1,
[6]   1,  131,   320,   165,    25,     1,
[7]   1,  428,  1711,  1420,   380,    36,    1,
[8]   1, 1429,  8967, 11151,  4620,   756,   49,  1,
[9]   1, 4861, 46663, 83202, 49665, 12306, 1358, 64, 1.
.
The sequence N(7,k) = 1 + 21*k + 105*k^2 + 175*k^3 + 105*k^4 + 21*k^5 + k^6 = 1, 429, 4279, 20071, 65445, ... = A090200(k) has the exponential generating function exp(x)*(1 + 428*x + 1711*x^2 + 1420*x^3 + 380*x^4 + 36*x^5 + x^6). Thus T(7,3) = 1420.

Cf. A243631 and the crossreferences given there.

T(n, 0) = T(n, n-1) = 1.
T(n, 1) = A001453(n) = A000108(n) - 1 for n>=2.
T(n, n-2) = (n-1)^2 for n>=2.

A262494 Triangle read by rows: T(n,k) (n>=1, 0<=k

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 13, 8, 2, 1, 41, 49, 23, 6, 1, 131, 276, 198, 90, 24, 1, 428, 1509, 1556, 982, 444, 120, 1, 1429, 8184, 11812, 9678, 5856, 2640, 720, 1, 4861, 44473, 88566, 91959, 68820, 40800, 18360, 5040, 1, 16795, 243334, 662732, 863296, 775134, 555828, 325200, 146160, 40320

Offset: 1

Christian Stump, Sep 24 2015

It appears that no recurrence or g.f. is known. - N. J. A. Sloane, Oct 13 2015

			Triangle begins:
  1;
  1,    1;
  1,    4,     1;
  1,   13,     8,     2;
  1,   41,    49,    23,     6;
  1,  131,   276,   198,    90,    24;
  1,  428,  1509,  1556,   982,   444,   120;
  1, 1429,  8184, 11812,  9678,  5856,  2640,   720;
  1, 4861, 44473, 88566, 91959, 68820, 40800, 18360, 5040;
  ...

FindStat - Combinatorial Statistic Finder, The number of stack-sorts needed to sort a permutation
Julian West, Permutations with forbidden subsequences; and, stack-sortable permutations, Ph.D. thesis, Massachusetts Institute of Technology, Dept. of Mathematics, 1990. See p. 76.

Columns k=0-1 give: A000012, A001453.
Row sums give A000142.
Cf. A000108.

T(n,0) = 1, T(n,1) = A000108(n) - 1. - Joerg Arndt, Sep 27 2015

Definition edited by N. J. A. Sloane, Oct 13 2015
More terms from Christian Stump, Oct 19 2015
Rows n=7-10 from Julian West's thesis added by Alois P. Heinz, Jun 27 2023

A373744 Triangle read by rows: the almost-Riordan array ( 1/(1-x) | 2/((1-x)(1+sqrt(1-4x))), (1-2x-sqrt(1-4x))/(2*x) ).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 9, 13, 6, 1, 1, 23, 41, 26, 8, 1, 1, 65, 131, 101, 43, 10, 1, 1, 197, 428, 376, 197, 64, 12, 1, 1, 626, 1429, 1377, 834, 337, 89, 14, 1, 1, 2056, 4861, 5017, 3382, 1597, 529, 118, 16, 1, 1, 6918, 16795, 18277, 13378, 7105, 2773, 781, 151, 18, 1

Offset: 0

Stefano Spezia, Jun 16 2024

			The triangle begins as:
  1;
  1,   1;
  1,   2,   1;
  1,   4,   4,   1;
  1,   9,  13,   6,   1;
  1,  23,  41,  26,   8,  1;
  1,  65, 131, 101,  43, 10,  1;
  1, 197, 428, 376, 197, 64, 12, 1;
  ...

Tian-Xiao He and Roksana Słowik, Total Positivity of Almost-Riordan Arrays, arXiv:2406.03774 [math.CO], 2024. See pp. 16-17.

Cf. A000012 (k=0 and n=k), A001453 (k=2), A004275 (subdiagonal), A014137, A091823, A143955 (k=3).

T[n_, 0]:=1; T[n_, k_]:=SeriesCoefficient[2/((1-x)(1+Sqrt[1-4x]))((1-2x-Sqrt[1-4x])/(2x))^(k-1), {x, 0, n-1}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}]//Flatten

T(n,1) = A014137(n-1).

T(n,n-2) = A091823(n-1) for n > 2.

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A276986 Numbers n for which there is a permutation p of (1,2,3,...,n) such that k+p(k) is a Catalan number for 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A283054 Triangle read by rows: T(n,k) = T(n,k-1) + T(n-1,k), T(n,0)=1, T(n,n) = T(n,n-1) + 1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

SageMath

A247502 Triangle read by rows: coefficients of polynomials related to the exponential generating function of sequences generated by Narayana polynomials evaluated at the integers; n>=1, 0<=k

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A262494 Triangle read by rows: T(n,k) (n>=1, 0<=k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A373744 Triangle read by rows: the almost-Riordan array ( 1/(1-x) | 2/((1-x)*(1+sqrt(1-4*x))), (1-2*x-sqrt(1-4*x))/(2*x) ).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A373744 Triangle read by rows: the almost-Riordan array ( 1/(1-x) | 2/((1-x)(1+sqrt(1-4x))), (1-2x-sqrt(1-4x))/(2*x) ).