A064641 -id:A064641 - cp's OEIS frontend

A064642 Triangle defined in A064641 read by rows.

1, 1, 2, 1, 5, 7, 1, 8, 22, 29, 1, 11, 46, 104, 133, 1, 14, 79, 251, 517, 650, 1, 17, 121, 497, 1369, 2669, 3319, 1, 20, 172, 869, 2986, 7541, 14179, 17498, 1, 23, 232, 1394, 5746, 17642, 42031, 77027, 94525, 1, 26, 301, 2099, 10108, 36482, 103696, 236933

Offset: 0

Floor van Lamoen, Oct 03 2001

Or, Dziemianczuk's array P(i,j) read by antidiagonals:
2   7  29  133   650   3319   17498 ...
5  22 104  517  2669  14179   77027 ...
8  46 251 1369  7541  42031  236933 ...
11  79 497 2986 17642 103696  609428 ...
14 121 869 5746 36482 226768 1393637 ...
...

			Triangle begins
  1;
  1, 2;
  1, 5,  7;
  1, 8, 22, 29;
  ...

Peter Kagey, Table of n, a(n) for n = 0..10010 (first 141 rows, flattened)
M. Dziemianczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013, Volume 30, Issue 6, pp 1427-1452.

Cf. A064641, A232972.

A038764 a(n) = (9n^2 + 3n + 2)/2.

Original entry on oeis.org

1, 7, 22, 46, 79, 121, 172, 232, 301, 379, 466, 562, 667, 781, 904, 1036, 1177, 1327, 1486, 1654, 1831, 2017, 2212, 2416, 2629, 2851, 3082, 3322, 3571, 3829, 4096, 4372, 4657, 4951, 5254, 5566, 5887, 6217, 6556, 6904, 7261, 7627, 8002, 8386, 8779, 9181

Offset: 0

N. J. A. Sloane, May 03 2000

Coefficients of x^2 of certain rook polynomials (for n>=1; see p. 18 of the Riordan paper). - Emeric Deutsch, Mar 08 2004

a(n) is also the least weight of self-conjugate partitions having n+1 different parts such that each part is congruent to 1 modulo 3. The first such self-conjugate partitions, corresponding to a(n) = 0, 1, 2, 3, are 1, 4+3, 7+4+4+4+3, 10+7+7+7+4+4+4+3. - Augustine O. Munagi, Dec 18 2008

J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.

Colin Barker, Table of n, a(n) for n = 0..1000
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Unbranched catacondensed polygonal systems containing hexagons and tetragons, Croatica Chem. Acta, 69 (1996), 757-774.
A. O. Munagi, Pairing conjugate partitions by residue classes, Discrete Math., 308 (2008), 2492-2501.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Reflection of A060544 in A081272.
Second column of A024462. Also = A064641(n+1, 2).
Shallow diagonal of triangular spiral in A051682.
Cf. A027468, A080855, A283394.
Partial sums of A122709.

LinearRecurrence[{3, -3, 1}, {1, 7, 22}, 50] (* Paolo Xausa, Jul 03 2025 *)

a(n)=n*(9*n+3)/2+1 \\ Charles R Greathouse IV, Jun 17 2017

Vec((1 + 2*x)^2 / (1 - x)^3 + O(x^60)) \\ Colin Barker, Jan 22 2018

a = lambda n: hypergeometric([-n, -2], [1], 3)
print([simplify(a(n)) for n in range(46)]) # Peter Luschny, Nov 19 2014

a(n) = binomial(n,0) + 6*binomial(n,1) + 9*binomial(n,2).
From Paul Barry, Mar 15 2003: (Start)
G.f.: (1 + 2*x)^2/(1 - x)^3.
Binomial transform of (1, 6, 9, 0, 0, 0, ...). (End)
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>2. -  Colin Barker, Jan 22 2018
a(n) = a(n-1) + 3*(3*n-1) for n>0, a(0)=1. - Vincenzo Librandi, Nov 17 2010
a(n) = hypergeometric([-n, -2], [1], 3). - Peter Luschny, Nov 19 2014
E.g.f.: exp(x)*(2 + 12*x + 9*x^2)/2. - Stefano Spezia, Mar 07 2023

More terms from James Sellers, May 03 2000

Entry revised by N. J. A. Sloane, Jan 23 2018

A063020 Reversion of y - y^2 - y^3 + y^4.

Original entry on oeis.org

0, 1, 1, 3, 9, 32, 119, 466, 1881, 7788, 32868, 140907, 611871, 2685732, 11896906, 53115412, 238767737, 1079780412, 4909067468, 22424085244, 102865595140, 473678981820, 2188774576575, 10145798119530, 47165267330415, 219839845852692, 1027183096151244, 4810235214490986

Offset: 0

Olivier Gérard, Jul 05 2001

Seems to be the inverse of A007858. Can someone prove this?

a(n+1) counts paths from (0,0) to (n,n) which do not go above the line y=x, using steps (1,0) and (2k,1), where k ranges over the nonnegative integers. For example, the 9 paths from (0,0) to (3,3) are the 5 Catalan paths, as well as DNEN, DENN, EDNN and ENDN. Here E=(1,0), N=(0,1), D=(2,1). - Brian Drake, Sep 20 2007

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
Elżbieta Liszewska and Wojciech Młotkowski, Some relatives of the Catalan sequence, arXiv:1907.10725 [math.CO], 2019.
A. Mironov and A. Morozov, Algebra of quantum C-polynomials, arXiv:2009.11641 [hep-th], 2020.
Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.
Index entries for reversions of series

Cf. A007848, A052709, A064641, A348410.

A:= series(RootOf(Z-_Z^2-_Z^3+_Z^4-x), x, 21): seq(coeff(A,x,i), i=0..20); # _Brian Drake, Sep 20 2007

CoefficientList[InverseSeries[Series[y - y^2 - y^3 + y^4, {y, 0, 30}], x], x]

a(n):=sum((sum(binomial(j,n-3*k+2*j-1)*(-1)^(j-k)*binomial(k,j),j,0,k))*binomial(n+k-1,n-1),k,0,n-1)/n; /* Vladimir Kruchinin, Oct 11 2011 */

a(n):=sum((-1)^(i)*binomial(n+i-1,i)*binomial(3*n-i-2,n-i-1),i,0,n-1)/n; /* Vladimir Kruchinin, Feb 13 2014 */

x='x+O('x^66); concat([0],Vec(serreverse(x-x^2-x^3+x^4))) \\ Joerg Arndt, May 28 2013

def b(n):
    h = binomial(3*n + 1, n) * hypergeometric([-n, n + 1], [-3*n - 1], -1) / (n + 1)
    return simplify(h)
print([0] + [b(n) for n in range(27)])  # Peter Luschny, Sep 21 2023

a(n) = (1/n)*Sum_{k=0..n-1} binomial(n+k-1,n-1) * Sum_{j=0..k} binomial(j,n-3*k+2*j-1)*(-1)^(j-k)*binomial(k,j). - Vladimir Kruchinin, Oct 11 2011
a(n) = (1/n)*Sum_{i=0..n-1} (-1)^(i)*binomial(n+i-1,i)*binomial(3*n-i-2,n-i-1), n > 0. - Vladimir Kruchinin, Feb 13 2014
Recurrence: 16*(n-1)*n*(2*n-1)*(17*n-27)*a(n) = (n-1)*(1819*n^3 - 6527*n^2 + 7350*n - 2520)*a(n-1) + 8*(2*n-3)*(4*n-9)*(4*n-7)*(17*n-10)*a(n-2). - Vaclav Kotesovec, Feb 13 2014
a(n) ~ sqrt(11-3/sqrt(17))/16 * (107+51*sqrt(17))^n / (sqrt(Pi) * n^(3/2) * 2^(6*n)). - Vaclav Kotesovec, Feb 13 2014
The g.f. A(x) satisfies x*A'(x)/A(x) = 1 + x + 5*x^2 + 19*x^3 + 85*x^4 + ..., the g.f. of A348410. - Peter Bala, Feb 22 2022

A201159 Irregular triangle read by rows: number of {0,1,2}-shifted Schroeder paths of length n and area k.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 2, 4, 5, 5, 5, 3, 1, 1, 1, 2, 2, 4, 5, 8, 10, 12, 13, 15, 17, 16, 13, 9, 4, 1, 1, 1, 2, 2, 4, 5, 8, 10, 15, 18, 23, 27, 34, 40, 47, 52, 56, 57, 57, 56, 50, 39, 26, 14, 5, 1, 1, 1, 2, 2, 4, 5, 8, 10, 15, 18, 26, 32, 42, 50, 63

Offset: 0

N. J. A. Sloane, Nov 27 2011

			Triangle begins
1
1 1
1 1 2 2 1
1 1 2 2 4 5 5 5 3 1
1 1 2 2 4 5 8 10 12 13 15 17 16 13 9 4 1
...

Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953. See Example 4.

Row sums are A064641.

Cf. S-shifted Schroeder paths for various S: A201075 {0,1}, A201076 {0,2}, A201079 {0,2,4,6...}, A201080 {0,1,3,5...}.

gf = Expand /@ FixedPoint[1 + x # + q x (1 + q x) # (Normal@# /. {x :> q^2 x}) + O[x]^7 &, 0];
Flatten[Reverse[CoefficientList[#, q]] & /@ CoefficientList[gf, x]] (* Andrey Zabolotskiy, Jan 03 2024 *)

More terms from Andrey Zabolotskiy, Jan 03 2024

A133656 Number of below-diagonal paths from (0,0) to (n,n) using steps (1,0), (0,1) and (2k-1,1), k a positive integer.

Original entry on oeis.org

1, 2, 6, 23, 99, 456, 2199, 10962, 56033, 292094, 1546885, 8299058, 45010492, 246377362, 1359339710, 7551689783, 42206697209, 237156951618, 1338917298708, 7591380528489, 43207023511013, 246773061257046, 1413889039642479, 8124356140582768, 46807462792903984

Offset: 0

Brian Drake, Sep 20 2007

			a(4) = 99 since there are 90 Schroeder paths (A006318) from (0,0) to (4,4) plus DNNEN, DNENN, DENNN, DdNN, DNdN, DNNd, EDNNN, ENDNN and dDNN, where E=(1,0), N=(0,1), D=(3,1) and d=(1,1).

Alois P. Heinz, Table of n, a(n) for n = 0..1276 (first 51 terms from Brian Drake)
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.

Cf. A006318, A064641, A052709, A063020, A348474.

Row sums of A201080.

A:=series(RootOf(1+_Z*(x-1)+_Z^2*(x-x^2)+_Z^3*x^2-_Z^4*x^3), x, 21): seq(coeff(A,x,i), i=0..20);

a[n_] := Sum[Binomial[n+k, n] * Sum[Binomial[j, -n - 3k + 2j - 2]* (-1)^(n+k-j+1) * Binomial[n+k+1, j], {j, 0, k+n+1}], {k, 0, n}]/(n+1);
a /@ Range[0, 24] (* Jean-François Alcover, Oct 06 2019, after Vladimir Kruchinin *)

a(n):=sum(binomial(n+k,n)*sum(binomial(j,-n-3*k+2*j-2)*(-1)^(n+k-j+1) *binomial(n+k+1,j),j,0,k+n+1),k,0,n)/(n+1); /* Vladimir Kruchinin, Oct 11 2011 */

G.f. g(x) satisfies: g(x) = 1 + x*g(x)^2+x*g(x)/(1-x^2*g(x)^2).
a(n) = sum(k=0..n, binomial(n+k,n)*sum(j=0..k+n+1, binomial(j,-n-3*k+2*j-2) *(-1)^(n+k-j+1)*binomial(n+k+1,j)))/(n+1). - Vladimir Kruchinin, Oct 11 2011
From Peter Bala, Feb 22 2022: (Start)
G.f. g(x) = (1/x)*series reversion of x*(1 + x)*(1 - x)^2/(1 + x - x^2).
It appears that 1 + x*g'(x)/g(x) = 1 + 2*x + 8*x^2 + 41*x^3 + 220*x^4 + ... is the g.f. of A348474. (End)

A260774 Certain directed lattice paths.

Original entry on oeis.org

1, 6, 33, 189, 1107, 6588, 39663, 240894, 1473147, 9058554, 55954395, 346934745, 2157989445, 13459891500, 84152389833, 527224251861, 3309194474451, 20804569738218, 130987600581699, 825796890644895, 5212349717906889, 32935490120006604, 208316726580941037

Offset: 0

N. J. A. Sloane, Jul 30 2015

nonn

See Dziemianczuk (2014) for precise definition.

Alois P. Heinz, Table of n, a(n) for n = 0..1235 (first 101 terms from Lars Blomberg)
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.

Cf. A122868, A064641, A156016.

Cf. A006139, A179191, A052709, A025227.

b:= proc(x, y) option remember; `if`([x, y]=[0$2], 1,
      `if`(x>0, add(b(x-1, y+j), j=-1..1), 0)+
      `if`(y>0, b(x, y-1), 0)+`if`(y<0, b(x, y+1), 0))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..23);  # Alois P. Heinz, Sep 21 2021

b[x_, y_] := b[x, y] = If[{x, y} == {0, 0}, 1,
     If[x > 0, Sum[b[x - 1, y + j], {j, -1, 1}], 0] +
     If[y > 0, b[x, y - 1], 0] + If[y < 0, b[x, y + 1], 0]];
a[n_] := b[n, 1];
Table[a[n], {n, 0, 23}] (* Jean-François Alcover, May 02 2022, after Alois P. Heinz *)

See Dziemianczuk (2014) Equation (33a) with m=1.
From Vaclav Kotesovec, Jul 15 2022: (Start)
Recurrence: (n+1)*(4*n - 3)*a(n) = 6*(4*n^2 - n - 1)*a(n-1) + 3*(n-1)*(4*n + 1)*a(n-2).
a(n) ~ (3 + 2*sqrt(3))^(n+1) / sqrt(6*Pi*n). (End)

More terms from Lars Blomberg, Aug 01 2015

A064643 Bidirectional 'Delannoy' variation of the Boustrophedon transform applied to all 1's sequence: Fill an triangular array in alternating directions. Let the first element of each row in that direction be equal to 1. Each next entry is given by T(n,k) = T(n,k +/- 1) + T(n-1,k-1) + T(n-1,k) + T(n-2,k-1), where the +/- depends on which is the previous element in the direction one is filling in the row. The final number of row n gives a(n).

Original entry on oeis.org

1, 2, 6, 22, 105, 631, 4603, 39469, 388870, 4327322, 53670985, 734069672, 10975379510, 178080287645, 3116286236549, 58502460526469

Offset: 0

Floor van Lamoen, Oct 03 2001

nonn

Index entries for sequences related to boustrophedon transform

Cf. A064641. Table: A064644, Delannoy numbers A008288.

A223092 Triangle read by rows: let T(n,k) (for n >= 0, 0 <= k <= n) be the number of walks from (0,0) to (n,k) using steps (1,1), (1,0), (1,-1) and (0,-1); n-th row of triangle gives T(n,n), T(n,n-1), ..., T(n,0).

Original entry on oeis.org

1, 1, 2, 1, 4, 7, 1, 6, 18, 29, 1, 8, 33, 86, 133, 1, 10, 52, 179, 431, 650, 1, 12, 75, 316, 978, 2238, 3319, 1, 14, 102, 505, 1874, 5406, 11941, 17498, 1, 16, 133, 754, 3235, 11020, 30241, 65086, 94525, 1, 18, 168, 1071, 5193, 20202, 64698, 171045, 360897, 520508, 1, 20, 207, 1464, 7896, 34362, 124455, 380400, 977040, 2029490, 2910895

Offset: 0

N. J. A. Sloane, Mar 29 2013

			Triangle begins:
[1]
[1, 2]
[1, 4, 7]
[1, 6, 18, 29]
[1, 8, 33, 86, 133]
[1, 10, 52, 179, 431, 650]
[1, 12, 75, 316, 978, 2238, 3319]
...
The T(n,k) array begins:
4:  0  0  0  0   1  10 ...
3:  0  0  0  1   8  52 ...
2:  0  0  1  6  33 179 ...
1:  0  1  4 18  86 431 ...
0:  1  2  7 29 133 650 ...
-------------------------
k/n:0  1  2  3   4   5 ...
T(5,2) = T(5,3) + T(4,3) + T(4,2) + T(4,1) = 52 + 8 + 33 + 86 = 179.- _Philippe Deléham_, Mar 29 2013
This is also Dziemianczuk's array N(-i,i+j) read by antidiagonals:
1,2,7,29,133,650,3319,17498, ...
1,4,18,86,431,2238,11941,65086, ...
1,6,33,179,978,5406,30241,171045, ...
1,8,52,316,1874,11020,64698,380400, ...
1,10,75,505,3235,20202,124455,761160, ...
... - _N. J. A. Sloane_, Dec 05 2013

Alois P. Heinz, Rows n = 0..140, flattened
M. Dziemianczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013
N. J. A. Sloane, Illustration of initial terms of A223092 and A064641

Cf. A064641 (T(n,0)), A071943, A052709.

T:= proc(n, k) option remember; `if`(n=0 and k=0, 1,
      `if`(n<0 or k<0 or k>n, 0, add(T(n-l[1], k-l[2]),
       l=[[1, 1], [1, 0], [1, -1], [0, -1]]) ))
    end:
seq(seq(T(n, n-j), j=0..n), n=0..10);  # Alois P. Heinz, Apr 08 2013

max = 10; T[0, 0] = 1; T[n_ /; n >= 0, k_ /; 0 <= k <= max] := T[n, k] = T[n, k+1]+T[n-1, k+1]+T[n-1, k]+T[n-1, k-1]; T[n_, k_] = 0; Table[Table[T[n, k], {k, n, 0, -1}], {n, 0, max}] // Flatten (* Jean-François Alcover, Mar 07 2014, after Philippe Deléham *)

T(n,k) = T(n,k+1) + T(n-1,k+1) + T(n-1,k) + T(n-1,k-1). - Philippe Deléham, Mar 29 2013

A260772 Certain directed lattice paths.

Original entry on oeis.org

1, 3, 10, 41, 190, 946, 4940, 26693, 147990, 837102, 4811860, 28027210, 165057100, 981177060, 5879570200, 35478788269, 215398416870, 1314794380374, 8064119033220, 49673222082782, 307163049317540, 1906066361809148, 11865666767361960, 74081851132379426

Offset: 0

N. J. A. Sloane, Jul 30 2015

nonn

See Dziemianczuk (2014) for precise definition.

Lars Blomberg, Table of n, a(n) for n = 0..100
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, Discrete Mathematics, Volume 339, Issue 3, 6 March 2016, Pages 1116-1139.
Heba Bou KaedBey, Mark van Hoeij, and Man Cheung Tsui, Solving Third Order Linear Difference Equations in Terms of Second Order Equations, arXiv:2402.11121 [math.AC], 2024. See p. 3.

Cf. A122868, A260774, A064641, A156016.

Cf. A006139, A179191, A052709, A025227.

# A260772 satisfies a 4th-order recurrence that can be reduced
# to a 2nd-order recurrence given in this program t:
t := proc(n) options remember;
if n <= 1 then
    [-1/2, 0, 1, 4][2*n+2]
  else
    (16*(n-2)*(2*n-3)*(5*n-2)*t(n-2) + (440*n^3-1056*n^2+724*n-144)*t(n-1))
       /( n*(2*n+1)*(5*n-7) )
  fi
end:
A260772 := proc(n)
t(n/2) + ( (2-2*n)*t((n-1)/2)+(n+2)*t((n+1)/2) ) / (1+5*n)
end:
seq(A260772(i),i=0..100);
# Mark van Hoeij, Jul 14 2022

a(n):=if n=0 then 1 else sum((-1)^j*binomial(n,j)*binomial(3*n-4*j,n-4*j+1),j,0,(n+1)/4)/n; /* Vladimir Kruchinin, Apr 04 2019 */

a(n) = if (n==0, 1, sum(j=0, (n+1)/4, (-1)^j*binomial(n,j)*binomial(3*n-4*j, n-4*j+1))/n); \\ Michel Marcus, Apr 05 2019

G.f.: P1(x) = (2*(1-x)/3)/x - ((2*sqrt(1-5*x-2*x^2)/3)/x)*sin((Pi/6 + arccos(((20*x^3-6*x^2+15*x-2)/2)/(1-5*x-2*x^2)^(3/2))/3)). - See Dziemianczuk (2014), Proposition 11.
a(n) = (1/n)*Sum_{j=0..(n+1)/4} (-1)^j*C(n,j)*C(3*n-4*j,n-4*j+1), a(0)=1. - Vladimir Kruchinin, Apr 04 2019
n*(n+1)*(25*n^2-70*n+21)*a(n) - 30*(7*n-15)*n*a(n-1) + (-1100*n^4+5280*n^3-6424*n^2-1188*n+3816)*a(n-2) + 120*(n+2)*(n-3)*a(n-3) - 16*(n-3)*(n-4)*(25*n^2-20*n-24)*a(n-4) = 0. - Mark van Hoeij, Jul 14 2022
a(n) ~ 2^(n - 1/2) * phi^((10*n - 1)/4) / (sqrt(Pi) * 5^(1/4) * sqrt(phi^(3/2) - 2) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Jul 15 2022

More terms from Lars Blomberg, Aug 01 2015

A232972 Main diagonal of array P(i,j) mentioned in A064642.

Original entry on oeis.org

1, 5, 46, 497, 5746, 68948, 846889, 10570001

Offset: 0

N. J. A. Sloane, Dec 05 2013

Cf. A064642, A064641.

cp's OEIS Frontend

A064642 Triangle defined in A064641 read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A038764 a(n) = (9*n^2 + 3*n + 2)/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Sage

Formula

Extensions

A063020 Reversion of y - y^2 - y^3 + y^4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Maxima

PARI

SageMath

Formula

A201159 Irregular triangle read by rows: number of {0,1,2}-shifted Schroeder paths of length n and area k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A133656 Number of below-diagonal paths from (0,0) to (n,n) using steps (1,0), (0,1) and (2k-1,1), k a positive integer.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A260774 Certain directed lattice paths.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

Views

Author

Keywords

Links

Crossrefs

A223092 Triangle read by rows: let T(n,k) (for n >= 0, 0 <= k <= n) be the number of walks from (0,0) to (n,k) using steps (1,1), (1,0), (1,-1) and (0,-1); n-th row of triangle gives T(n,n), T(n,n-1), ..., T(n,0).

Views

A038764 a(n) = (9n^2 + 3n + 2)/2.