A116701 -id:A116701 - cp's OEIS frontend

A080853 Square array of generalized polygonal numbers, read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 9, 7, 1, 1, 5, 16, 19, 11, 1, 1, 6, 25, 37, 33, 16, 1, 1, 7, 36, 61, 67, 51, 22, 1, 1, 8, 49, 91, 113, 106, 73, 29, 1, 1, 9, 64, 127, 171, 181, 154, 99, 37, 1, 1, 10, 81, 169, 241, 276, 265, 211, 129, 46, 1, 1, 11, 100, 217, 323, 391, 406, 365, 277

Offset: 0

Paul Barry, Feb 23 2003

			Rows begin with n>=0, k>=0
1 1 1 1 1 ...
1 2 4 7 11 ...
1 3 9 19 33 ...
1 4 16 37 67 ...
1 5 25 61 113 ...

Rows include A000124, A058331, A080855, A080856, A080857, A080919.

Columns include A000290, A003215, A003215, A080859, A080860, A080861.

A080853 := proc(n,k)
    binomial(k,0)+n*binomial(k,1)+n^2*binomial(k,2) ;
end proc:
seq( seq(A080853(d-k,k),k=0..d),d=0..12) ; # R. J. Mathar, Oct 01 2021

T(n, k)=C(k, 0)+C(k, 1)n+C(k, 2)n^2=(n^2*k^2-(n^2-2n)*k+2)/2 =(k(k-1)*n^2+2k*n+2)/2
Row n has g.f. (1+(n-2)x+(n^2-n+1)x^2)/(1-x)^3.
Column k has g.f. (C(k-1, 0)+(C(k+1, 2)-2)*x+C(k-1, 2)*x^2)/(1-x)^3.
Diagonals are given by (n^4+(2k-1)*n^3+((k-1)^2+1)*n^2+(1-(k-1)^2)*n+2)/2.
Antidiagonal sums are 1, 2, 4, 9, 22, 53, 119,... = (d+1)*(2*d^4-7*d^3+27*d^2-22*d+120)/120 = sum_{k=0..d} T(d-k,k), first differences in  A116701, d>=0. - R. J. Mathar, Oct 01 2021

A084569 Partial sums of A084570.

Original entry on oeis.org

1, 3, 9, 21, 44, 82, 142, 230, 355, 525, 751, 1043, 1414, 1876, 2444, 3132, 3957, 4935, 6085, 7425, 8976, 10758, 12794, 15106, 17719, 20657, 23947, 27615, 31690, 36200, 41176, 46648, 52649, 59211, 66369, 74157, 82612, 91770, 101670, 112350, 123851

Offset: 0

Paul Barry, May 31 2003

Conjecture: a(n) is the number of perimeter-magic (hollow) squares of order 3 with magic sum n+3. Order 3 means each of the 4 edges has 3 elements >=1; the square has 8 elements. The elements do not need to be distinct, and squares obtained by rotations are counted only once. The square (read ccw) for magic sum 3 has elements 1 1 1 1 1 1 1 1. The 3 squares with magic sum 4 are 1 1 2 1 1 1 2 1, 1 1 2 1 1 2 1 2 and 1 2 1 2 1 2 1 2. - R. J. Mathar, Mar 08 2025

R. J. Mathar, Generating perimeter-magic polygons, C++ (2025)
Index entries for linear recurrences with constant coefficients, signature (4,-5,0,5,-4,1).

Cf. A116701.

Accumulate[LinearRecurrence[{3,-2,-2,3,-1},{1,2,6,12,23},50]] (* or *) LinearRecurrence[{4,-5,0,5,-4,1},{1,3,9,21,44,82},50] (* Harvey P. Dale, Nov 12 2014 *)

a(n) = (-1)^n/8 + (n^4 + 6*n^3 + 17*n^2 + 30*n + 21)/24.
a(n) = Sum_{k=0..n} Sum_{j=0..k} Sum_{i=0..j} (i + (-1)^i).
G.f.: ( -1+x-2*x^2 ) / ( (1+x)*(x-1)^5 ). - R. J. Mathar, Mar 08 2025
a(n)+a(n+1) = A116701(n+3)-1. - R. J. Mathar, Mar 08 2025

A349740 Number of partitions of set [n] in a set of <= k noncrossing subsets. Number of Dyck n-paths with at most k peaks. Both with 0 <= k <= n, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 1, 4, 5, 0, 1, 7, 13, 14, 0, 1, 11, 31, 41, 42, 0, 1, 16, 66, 116, 131, 132, 0, 1, 22, 127, 302, 407, 428, 429, 0, 1, 29, 225, 715, 1205, 1401, 1429, 1430, 0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862, 0, 1, 46, 586, 3106, 8398, 13690, 16210, 16750, 16795, 16796

Offset: 0

Ron L.J. van den Burg, Nov 28 2021

Given a partition P of the set {1,2,...,n}, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a block, and b, d are together in a different block. A noncrossing partition is a partition with no crossings.

			For n=4 the T(4,3)=13 partitions are {{1,2,3,4}}, {{1,2,3},{4}}, {{1,2,4},{3}}, {{1,3,4},{2}}, {{2,3,4},{1}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,2},{3},{4}}, {{1,3},{2},{4}}, {{1,4},{2},{3}}, {{1},{2,3},{4}}, {{1},{2,4},{3}}, {{1},{2},{3,4}}.
The set of sets {{1,3},{2,4}} is missing because it is crossing. If you add the set of 4 sets, {{1},{2},{3},{4}}, you get T(4, 4) = 14 = A000108(4), the 4th Catalan number.
Triangle begins:
  1;
  0, 1;
  0, 1,  2;
  0, 1,  4,   5;
  0, 1,  7,  13,   14;
  0, 1, 11,  31,   41,   42;
  0, 1, 16,  66,  116,  131,  132;
  0, 1, 22, 127,  302,  407,  428,  429;
  0, 1, 29, 225,  715, 1205, 1401, 1429, 1430;
  0, 1, 37, 373, 1549, 3313, 4489, 4825, 4861, 4862;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
David Callan, Sets, Lists and Noncrossing Partitions, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3; also on arXiv, arXiv:0711.4841 [math.CO], 2007-2008.

Columns k=0-4 give (for n>=k): A000007, A000012, A000124(n-1), A116701, A116844.
Partial sums of A090181 per row.
Main diagonal is A000108.
Row sums give A088218.
T(2*n,n) gives A065097.
T(n,n-1) gives A001453 for n >= 2.
Cf. A106396, A137940.

b:= proc(x, y, t) option remember; expand(`if`(y<0
      or y>x, 0, `if`(x=0, 1, add(b(x-1, y+j, j)*
     `if`(t=1 and j<1, z, 1), j=[-1, 1]))))
    end:
T:= proc(n, k) option remember; `if`(k<0, 0,
      T(n, k-1)+coeff(b(2*n, 0$2), z, k))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Nov 28 2021

T[n_, k_] := If[n == 0, 1, Sum[j Binomial[n, j]^2 / (n - j + 1), {j, 0, k}] / n];
Table[T[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Peter Luschny, Nov 29 2021 *)

T(n,k) = Sum_{j=0..k} A090181(n,j), the partial sum of the Narayana numbers.
T(n,n) = A000108(n), the n-th Catalan number.
G.f.: (1 + x - x*y - sqrt((1-x*(1+y))^2 - 4*y*x^2))/(2*x*(1-y)).
T(n,k) = (1/n)*Sum_{j=0..k} j*binomial(n,j)^2 / (n-j+1) for n >= 1. - Peter Luschny, Nov 29 2021

A179257 Number of permutations of length n which avoid the patterns 321 and 1324.

Original entry on oeis.org

1, 1, 2, 5, 13, 32, 72, 148, 281, 499, 838, 1343, 2069, 3082, 4460, 6294, 8689, 11765, 15658, 20521, 26525, 33860, 42736, 53384, 66057, 81031, 98606, 119107, 142885, 170318, 201812, 237802, 278753, 325161, 377554, 436493, 502573, 576424, 658712, 750140, 851449

Offset: 0

Vincent Vatter, Jul 05 2010

			There are 13 permutations of length 4 which avoid these two patterns, so a(4)=13.

M. D. Atkinson, Restricted permutations, Discrete Math., 195 (1999), 27-38.
Christian Bean, Bjarki Gudmundsson, Henning Ulfarsson, Automatic discovery of structural rules of permutation classes, arXiv:1705.04109 [math.CO], 2017.
J. West, Generating trees and forbidden subsequences, Discrete Math., 157 (1996), 363-374.
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A116699, A116701, A116702, A088921, A005183, A116703, A001519.

LinearRecurrence[{6,-15,20,-15,6,-1},{1,1,2,5,13,32},50] (* Harvey P. Dale, May 19 2024 *)

a(n) = 1+binomial(n,2)+binomial(n+2,5).
G.f.: 1-x*(x^5-4*x^4+7*x^3-8*x^2+4*x-1)/(x-1)^6. - Colin Barker, Aug 02 2012
a(n) = 1+A027658(n-2). - R. J. Mathar, Aug 19 2022

a(0)=1 prepended by Alois P. Heinz, Jul 05 2018

cp's OEIS Frontend

A080853 Square array of generalized polygonal numbers, read by antidiagonals.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Formula

A084569 Partial sums of A084570.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A349740 Number of partitions of set [n] in a set of <= k noncrossing subsets. Number of Dyck n-paths with at most k peaks. Both with 0 <= k <= n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A179257 Number of permutations of length n which avoid the patterns 321 and 1324.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions