A071945 -id:A071945 - cp's OEIS frontend

A108075 Triangle in A071945 with rows reversed.

1, 1, 1, 3, 3, 1, 9, 9, 5, 1, 31, 31, 19, 7, 1, 113, 113, 73, 33, 9, 1, 431, 431, 287, 143, 51, 11, 1, 1697, 1697, 1153, 609, 249, 73, 13, 1, 6847, 6847, 4719, 2591, 1151, 399, 99, 15, 1, 28161, 28161, 19617, 11073, 5201, 2001, 601, 129, 17, 1, 117631, 117631, 82623

Offset: 0

N. J. A. Sloane, Jun 05 2005

			Triangle begins:
   1;
   1,  1;
   3,  3,  1;
   9,  9,  5, 1;
  31, 31, 19, 7, 1;
  ...

D. Baccherini, D. Merlini and R. Sprugnoli, Level generating trees and proper Riordan arrays, Applicable Analysis and Discrete Mathematics, 2, 2008, 69-91 (see p. 88). [From _Emeric Deutsch_, Sep 21 2008]

Row sums yield A052705. Column 0 yields A052709.

q:=sqrt(1-4*z-4*z^2): G:=(1-q)/z/(1+z)/(2-t+t*q): Gser:=simplify(series(G,z=0,13)): P[0]:=1: for n from 1 to 10 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 10 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form - Emeric Deutsch, Jun 06 2005

G.f.: (1-q)/(z(1+z)(2-t+tq)), where q = sqrt(1 - 4z - 4z^2). - Emeric Deutsch, Jun 06 2005

T(n,k) = T(n-1,k-1) + T(n-2,k-1) + T(n,k+1), T(0,0)=1. - Philippe Deléham, Nov 18 2009

More terms from Emeric Deutsch, Jun 06 2005

A052709 Expansion of g.f. (1-sqrt(1-4x-4x^2))/(2*(1+x)).

Original entry on oeis.org

0, 1, 1, 3, 9, 31, 113, 431, 1697, 6847, 28161, 117631, 497665, 2128127, 9183489, 39940863, 174897665, 770452479, 3411959809, 15181264895, 67833868289, 304256253951, 1369404661761, 6182858317823, 27995941060609, 127100310290431, 578433619525633, 2638370120138751

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

A simple context-free grammar.
Number of lattice paths from (0,0) to (2n-2,0) that stay (weakly) in the first quadrant and such that each step is either U=(1,1), D=(1,-1), or L=(3,1). Equivalently, underdiagonal lattice paths from (0,0) to (n-1,n-1) and such that each step is either (1,0), (0,1), or (2,1). E.g., a(4)=9 because in addition to the five Dyck paths from (0,0) to (6,0) [UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD] we have LDUD, LUDD, ULDD and UDLD. - Emeric Deutsch, Dec 21 2003
Hankel transform of a(n+1) is A006125(n+1). - Paul Barry, Apr 01 2007
Also, a(n+1) is the number of walks from (0,0) to (n,0) using steps (1,1), (1,-1) and (0,-1). See the U(n,k) array in A071943, where A052709(n+1) = U(n,0). - N. J. A. Sloane, Mar 29 2013
Diagonal sums of triangle in A085880. - Philippe Deléham, Nov 15 2013
From Gus Wiseman, Jun 17 2021: (Start)
Conjecture: For n > 0, also the number of sequences of length n - 1 covering an initial interval of positive integers and avoiding three terms (..., x, ..., y, ..., z, ...) such that x <= y <= z. The version avoiding the strict pattern (1,2,3) is A226316. Sequences covering an initial interval are counted by A000670. The a(1) = 1 through a(4) = 9 sequences are:
  ()  (1)  (1,1)  (1,2,1)
           (1,2)  (1,3,2)
           (2,1)  (2,1,1)
                  (2,1,2)
                  (2,1,3)
                  (2,2,1)
                  (2,3,1)
                  (3,1,2)
                  (3,2,1)
(End)

N. J. A. Sloane, Table of n, a(n) for n = 0..499
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Ascending runs in permutations and valued Dyck paths, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 445-463.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.
Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.
Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, and Michael D. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, arXiv:1602.03550 [math.CO], 2016.
Xiang-Ke Chang, X.-B. Hu, H. Lei, and Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
James East and Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.
L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math., 271 (2003), 29-50.
Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 664
J. P. S. Kung and A. de Mier, Catalan lattice paths with rook, bishop and spider steps, Journal of Combinatorial Theory, Series A 120 (2013) 379-389. - _N. J. A. Sloane_, Dec 27 2012
D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.

Diagonal entries of A071943 and A071945.
Cf. A000108, A000670, A025227, A052709, A056986, A071943, A085880.
Cf. A102726, A117434, A158005, A226316, A333217, A335479.

[0] cat [(&+[Binomial(n,k+1)*Binomial(2*k,n-1): k in [0..n-1]])/n: n in [1..30]]; // G. C. Greubel, May 30 2022

spec := [S,{C=Prod(B,Z),S=Union(B,C,Z),B=Prod(S,S)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

InverseSeries[Series[(y-y^2)/(1+y^2), {y, 0, 24}], x] (* then A(x)= y(x) *) (* Len Smiley, Apr 12 2000 *)
CoefficientList[Series[(1 -Sqrt[1 -4x -4x^2])/(2(1+x)), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 12 2016 *)

a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x),n)

[sum(binomial(k, n-k-1)*catalan_number(k) for k in (0..n-1)) for n in (0..30)] # G. C. Greubel, May 30 2022

a(n) + a(n-1) = A025227(n).
a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-2-2*k)!/(k!*(n-k)!*(n-1-2*k)!). - Emeric Deutsch, Nov 14 2001
D-finite with recurrence: n*a(n) = (3*n-6)*a(n-1) + (8*n-18)*a(n-2) + (4*n-12)*a(n-3), n>2. a(1)=a(2)=1.
a(n) = b(1)*a(n-1) + b(2)*a(n-2) + ... + b(n-1)*a(1) for n>1 where b(n)=A025227(n).
G.f.: A(x) = x/(1-(1+x)*A(x)). - Paul D. Hanna, Aug 16 2002
G.f.: A(x) = x/(1-z/(1-z/(1-z/(...)))) where z=x+x^2 (continued fraction). - Paul D. Hanna, Aug 16 2002; revised by Joerg Arndt, Mar 18 2011
a(n+1) = Sum_{k=0..n} Catalan(k)*binomial(k, n-k). - Paul Barry, Feb 22 2005
From Paul Barry, Mar 14 2006: (Start)
G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108.
Row sums of A117434. (End)
a(n+1) = (1/(2*Pi))*Integral_{x=2-2*sqrt(2)..2+2*sqrt(2)} x^n*(4+4x-x^2)/(2*(1+x)). - Paul Barry, Apr 01 2007
From Gary W. Adamson, Jul 22 2011: (Start)
For n>0, a(n) is the upper left term in M^(n-1), where M is an infinite square production matrix as follows:
  1, 1, 0, 0, 0, 0, ...
  2, 1, 1, 0, 0, 0, ...
  2, 2, 1, 1, 0, 0, ...
  2, 2, 2, 1, 1, 0, ...
  2, 2, 2, 2, 1, 1, ...
  ... (End)
G.f.: x*Q(0), where Q(k) = 1 + (4*k+1)*x*(1+x)/(k+1 - x*(1+x)*(2*k+2)*(4*k+3)/(2*x*(1+x)*(4*k+3) + (2*k+3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
a(n) ~ sqrt(2-sqrt(2))*2^(n-1/2)*(1+sqrt(2))^(n-1)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Jun 29 2013
a(n+1) = Sum_{k=0..floor(n/2)} A085880(n-k,k). - Philippe Deléham, Nov 15 2013

Better g.f. and recurrence from Michael Somos, Aug 03 2000

More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000

A052705 Expansion of 2x^2/(1 - 2x - 2x^2 + sqrt(1 - 4x - 4*x^2)).

Original entry on oeis.org

0, 0, 1, 2, 7, 24, 89, 342, 1355, 5492, 22669, 94962, 402703, 1725424, 7458065, 32482798, 142414867, 628037612, 2783922197, 12397342698, 55436525591, 248819728360, 1120584933401, 5062273384422, 22933667676187

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Number of underdiagonal paths from (0,0) to the line x=n-2, using only steps R=(1,0), V=(0,1) and D=(2,1). E.g., a(4)=7 because we have RR, RRV, RVR, D, RVRV, RRVV and DV. - Emeric Deutsch, Dec 21 2003

Muniru A Asiru, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 660
C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Can. J. Math., 49 (2) (1997) 301-310.

Row sums of A071945, cf. A000108.

spec := [S,{S=Prod(B,B),C=Prod(S,Z),B=Union(S,C,Z)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

CoefficientList[Series[(2x^2)/(1-2x-2x^2+Sqrt[1-4x-4x^2]),{x,0,30}],x] (* Harvey P. Dale, Dec 16 2014 *)
Join[{0,0},Table[(Binomial[2(m-1),m]HypergeometricPFQ[{(2-m)/2,(3-m)/2,-m},{3/2-m,2-m},-1])/(m-1),{m,2,20}]] (* Benedict W. J. Irwin, Sep 13 2016 *)

a(n):=(sum(binomial(2*n-2*j,n)*binomial(n,j-1)/(n-j),j,1,n/2)); /* Vladimir Kruchinin, Jan 16 2015 */

D-finite with recurrence: a(1)=0, a(2)=1, a(3)=2, 4*(n+1)*a(n) + (10+8*n)*a(n+1) + (2+3*n)*a(n+2) + (-n-3)*a(n+3) = 0.
a(n+2) = Sum_{k=0..n} Sum_{j=0..n} C(j,n-j)*A001263(j,k). - Paul Barry, Jun 30 2009
a(n) = Sum_{j=1..floor(n/2)} C(2*n-2*j,n)*C(n,j-1)/(n-j). - Vladimir Kruchinin, Jan 16 2015
G.f.: A(x) satisfies A(x) = C(x*(1+A(x)))^2, where x*C(x) is g.f. of Catalan numbers. - Vladimir Kruchinin, Jan 16 2015
a(n) = C(2*n-2,n)*3F2((2-n)/2,(3-n)/2,-n;3/2-n,2-n;-1)/(n-1), n>1. - Benedict W. J. Irwin, Sep 13 2016
a(n) ~ 2^(n + 3/4) * (1 + sqrt(2))^(n - 5/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 03 2019

More terms from Emeric Deutsch, Mar 07 2004

A071943 Triangle T(n,k) (n>=0, 0 <= k <= n) read by rows giving number of underdiagonal lattice paths from (0,0) to (n,k) using only steps R=(1,0), V=(0,1) and D=(1,2).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 7, 9, 1, 4, 12, 24, 31, 1, 5, 18, 46, 89, 113, 1, 6, 25, 76, 183, 342, 431, 1, 7, 33, 115, 323, 741, 1355, 1697, 1, 8, 42, 164, 520, 1376, 3054, 5492, 6847, 1, 9, 52, 224, 786, 2326, 5900, 12768, 22669, 28161, 1, 10, 63, 296, 1134, 3684, 10370

Offset: 0

N. J. A. Sloane, Jun 15 2002

For another interpretation of this array see the Example section.

			T(3,2)=7 because we have RRRVV, RRVRV, RRVVR, RVRRV, RVRVR, RRD and RDR.
Array begins:
1,
1, 1,
1, 2, 3,
1, 3, 7, 9,
1, 4, 12, 24, 31,
1, 5, 18, 46, 89, 113,
1, 6, 25, 76, 183, 342, 431,
1, 7, 33, 115, 323, 741, 1355, 1697,
...
Equivalently, let U(n,k) (for n >= 0, 0 <= k <= n) be the number of walks from (0,0) to (n,k) using steps (1,1), (1,-1) and (0,-1). Then U(n,n-k) = T(n,k). The U(n,k) array begins:
4:  0  0  0  0  1  5 ...
3:  0  0  0  1  4 18 ...
2:  0  0  1  3 12 46 ...
1:  0  1  2  7 24 89 ...
0:  1  1  3  9 31 113 ...
-------------------------
k/n:0  1  2  3  4  5 ...
The recurrence for this version is: U(0,0)=1, U(n,k)=0 for k>n or k<0; U(n,k) = U(n,k+1) + U(n-1,k+1) + U(n,k-1). E.g. 46 = 18 + 4 + 24. Also U(n,0) = A052709(n-1).

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150, flattened)
James East, Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018.
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad J. Math., 49 (1997), 301-320.
N. J. A. Sloane, Rows 0 through 100
N. J. A. Sloane, Illustration of the initial terms of the U(n,k) array

Diagonal entries yield A052709. Row sums are A071356.

Related arrays: A071944, A071945, A071946.

U:=proc(n,k) option remember;
if (n < 0) then RETURN(0);
elif (n=0) then
   if (k=0) then RETURN(1); else RETURN(0); fi;
elif (k>n or k<0) then RETURN(0);
else RETURN(U(n,k+1)+U(n-1,k+1)+U(n-1,k-1));
fi;
end;
for n from 0 to 20 do
lprint( [seq(U(n,n-i),i=0..n)] );
od:

t[0, 0] = 1; t[n_, k_] /; k<0 || k>n = 0; t[n_, k_] := t[n, k] = t[n, k-1] + t[n-1, k] + t[n-1, k-2]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 07 2014, after N. J. A. Sloane *)

G.f.=(1-q)/[z(2t+2t^2z-1+q)], where q=sqrt(1-4tz-4t^2z^2).

Define T(0,0)=1 and T(n,k)=0 for k<0 and k >n. Then the array is generated by the recurrence T(n,k) = T(n,k-1) + T(n-1,k) + T(n-1,k-2). For example, T(5,3) = 46 = T(5,2) + T(4,3) + T(4,1) = 18 + 24 + 4. - N. J. A. Sloane, Mar 28 2013

Edited by Emeric Deutsch, Dec 21 2003

Edited by N. J. A. Sloane, Mar 28 2013

A071946 Triangle T(n,k) read by rows giving number of underdiagonal lattice paths from (0,0) to (n,k) using only steps R = (1,0), V = (0,1) and D = (3,1).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 4, 6, 6, 1, 6, 13, 19, 19, 1, 8, 23, 44, 63, 63, 1, 10, 37, 87, 156, 219, 219, 1, 12, 55, 155, 330, 568, 787, 787, 1, 14, 77, 255, 629, 1260, 2110, 2897, 2897, 1, 16, 103, 395, 1111, 2527, 4856, 7972, 10869, 10869, 1, 18, 133, 583, 1849, 4706, 10130, 18889, 30545, 41414, 41414

Offset: 0

N. J. A. Sloane, Jun 15 2002

			Triangle T(n,k) begins:
  1;
  1, 1;
  1, 2,  2;
  1, 4,  6,  6;
  1, 6, 13, 19, 19;
  ...

Alois P. Heinz, Rows n = 0..150, flattened
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad J. Math., 49 (1997), 301-320.

Related arrays: A071943, A071944, A071945.

A108076 is the reverse, A119254 is the row sums and A071969 is the last (largest) number in each row.

T:= proc(n, k) option remember; `if`(n=0 and k=0, 1,
     `if`(k<0 or nAlois P. Heinz, May 05 2023

T[n_, k_] := T[n, k] = If[n == 0 && k == 0, 1,
   If[k < 0 || n < k, 0, T[n-1, k] + T[n, k-1] + T[n-3, k-1]]];
Table[Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 25 2025, after Alois P. Heinz *)

More terms from Joshua Zucker, May 10 2006

A334016 Table read by antidiagonals upward: T(n,k) is the number of ways to move a chess queen from (1,1) to (n,k) in the first quadrant using only right, diagonal up-right, and diagonal up-left moves.

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 4, 10, 21, 35, 8, 25, 65, 139, 237, 16, 60, 179, 451, 978, 1684, 32, 140, 470, 1337, 3339, 7239, 12557, 64, 320, 1189, 3725, 10325, 25559, 55423, 96605, 128, 720, 2926, 9958, 30018, 81716, 200922, 435550, 761938, 256, 1600, 7048, 25802, 83518

Offset: 1

Peter Kagey, Apr 12 2020

			Table begins:
n\k|   1    2     3      4       5        6         7          8
---+------------------------------------------------------------
  1|   1    1     6     35     237     1684     12557      96605
  2|   1    4    21    139     978     7239     55423     435550
  3|   2   10    65    451    3339    25559    200922    1611624
  4|   4   25   179   1337   10325    81716    658918    5394051
  5|   8   60   470   3725   30018   245220   2027447   16935981
  6|  16  140  1189   9958   83518   703635   5961973   50811786
  7|  32  320  2926  25802  224831  1951587  16938814  147261146
  8|  64  720  7048  65241  589701  5269220  46826316  415175289
For example, the T(2,2) = 4 valid sequences of moves from (1,1) to (2,2) are:
(1,1) -> (2,1) -> (1,2) -> (2,2),
(1,1) -> (2,1) -> (3,1) -> (2,2),
(1,1) -> (2,2), and
(1,1) -> (3,1) -> (2,2).

Peter Kagey, Table of n, a(n) for n = 1..10011 (first 141 antidiagonals)
Peter Kagey, Parity bitmap of first 2048 rows and 1024 columns. (Even and odd entries and represented by black and white pixels respectively.)

Cf. A035002 (up, right), A059450 (right, up-left), A132439 (up, right, up-right), A279212 (up, right, up-right, up-left), A334017 (up, right, up-left).

A071945 is the analog for king moves. For both king and queen moves, A094727 is the length of the longest sequence of moves.

T(n,k) = Sum_{i=1..k-1} T(n+i, k-i) + Sum_{i=1..min(n,k)-1} T(n-i, k-i) + Sum_{i=1..n-1} T(n-i, k).

cp's OEIS Frontend

A108075 Triangle in A071945 with rows reversed.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A052709 Expansion of g.f. (1-sqrt(1-4*x-4*x^2))/(2*(1+x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A052705 Expansion of 2*x^2/(1 - 2*x - 2*x^2 + sqrt(1 - 4*x - 4*x^2)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

Extensions

A071943 Triangle T(n,k) (n>=0, 0 <= k <= n) read by rows giving number of underdiagonal lattice paths from (0,0) to (n,k) using only steps R=(1,0), V=(0,1) and D=(1,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A071946 Triangle T(n,k) read by rows giving number of underdiagonal lattice paths from (0,0) to (n,k) using only steps R = (1,0), V = (0,1) and D = (3,1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A334016 Table read by antidiagonals upward: T(n,k) is the number of ways to move a chess queen from (1,1) to (n,k) in the first quadrant using only right, diagonal up-right, and diagonal up-left moves.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A052709 Expansion of g.f. (1-sqrt(1-4x-4x^2))/(2*(1+x)).

A052705 Expansion of 2x^2/(1 - 2x - 2x^2 + sqrt(1 - 4x - 4*x^2)).