A059450 -id:A059450 - cp's OEIS frontend

A086871 Row sums of A059450.

1, 2, 10, 58, 370, 2514, 17850, 130890, 983650, 7536418, 58648810, 462306266, 3683602130, 29620138994, 240059315610, 1958940281322, 16081662931650, 132723191430210, 1100568370427850, 9164925012016506, 76612776253995570

Offset: 0

N. J. A. Sloane, Sep 16 2003

Hankel transform is A165928. - Paul Barry, Sep 30 2009

Number of skew Dyck paths of semilength n with the down steps coming in two colors. - David Scambler, Jun 21 2013

			G.f. = 1 + 2*x + 10*x^2 + 58*x^3 + 370*x^4 + 2514*x^5 + 17850*x^6 + 130890*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200
C. Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28.
J. Machacek, Lattice walks ending on a coordinate hyperlane avoiding backtracking and repeats, arXiv:2105.02417 [math.CO], 2021. See Thm. 4.4 G(x,E^1).

Table[SeriesCoefficient[2/(1+Sqrt[(1-9*x)/(1-x)]),{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, Oct 14 2012 *)

{a(n) = if( n<0, 0, polcoeff( 2 / (1 + sqrt((1 - 9*x) / (1 - x) + x * O(x^n))), n))}; /* Michael Somos, Mar 06 2004 */

{a(n) = if( n<1, n==0, n++; 2 * polcoeff( serreverse( x * (1 - 4*x) / (1 - 3*x) + x * O(x^n)), n))}; /* Michael Somos, Mar 06 2004 */

a(n) = 2*A059231(n), if n>0.
G.f.: (1 - x - sqrt((1 - x) * (1 - 9*x))) / (4*x) = 2 / (1 + sqrt((1 - 9*x) / (1 - x))) =: y satisfies 0 = (1 - x) * (1 - y) + 2*x*y^2. - Michael Somos, Mar 06 2004
Moment representation: a(n) = (1/(4*Pi))*Integral_{x=1..9} x^n*sqrt(-x^2+10x-9)/x+(1/2)*0^n. - Paul Barry, Sep 30 2009
D-finite with recurrence Recurrence: (n+1)*a(n) = 5*(2*n-1)*a(n-1) - 9*(n-2)*a(n-2). - Vaclav Kotesovec, Oct 14 2012
a(n) ~ 3^(2*n+1)/(2*sqrt(2*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 14 2012
G.f.: 1/(2*x) - 1/2 + G(0)  where G(k) = 1 - 1/(x + x/(1 + 1/G(k+1) )) ; (continued fraction,3-step). - Sergei N. Gladkovskii, Nov 29 2012

More terms from Ray Chandler, Sep 17 2003

A086866 Third column of A059450.

Original entry on oeis.org

0, 0, 5, 17, 50, 136, 352, 880, 2144, 5120, 12032, 27904, 64000, 145408, 327680, 733184, 1630208, 3604480, 7929856, 17367040, 37879808, 82313216, 178257920, 384827392, 828375040, 1778384896, 3808428032, 8136949760, 17347641344

Offset: 0

N. J. A. Sloane, Sep 16 2003

Harvey P. Dale, Table of n, a(n) for n = 0..1000
C. Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28.
Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

LinearRecurrence[{6,-12,8},{0,0,5,17,50},30] (* Harvey P. Dale, Jun 13 2016 *)

For n>1, a(n) = (n^2+9n-2)*2^(n-4). - Ralf Stephan, May 10 2004

More terms from Ray Chandler, Sep 17 2003

A368773 Antidiagonal sums of A059450.

Original entry on oeis.org

1, 1, 3, 7, 21, 53, 159, 419, 1257, 3401, 10203, 28095, 84285, 235005, 705015, 1984155, 5952465, 16873745, 50621235, 144327287, 432981861, 1240296773, 3720890319, 10700364691, 32101094073, 92619680089, 277859040267, 803956981807, 2411870945421, 6995553520653, 20986660561959, 61001041404555

Offset: 0

Joerg Arndt, Jan 05 2024

nonn

Cf. A059450.

A368773 := proc(n)
    add(A059450(n-j,j), j=0..floor(n/2)) ;
end proc:
seq(A368773(n),n=0..40) ; # R. J. Mathar, Mar 25 2024

N=32;  M=matrix(N+1, N+1);  M[1,1] = 1;
T(n,k)= return( M[n+1,k+1] );
{ \\ A059450
 for (n=1, N,
  for (k=0, n,
    v = sum(y=0, n-1, T(y, k) ); \\ vert sum from top
    h = sum(y=0, n-1, T(n, y) ); \\ horiz sum from left
    s = v + h;
    M[ n+1, k+1 ] = s;
    );
); }
\\ antidiagonal sums:
for (n=0, N, my(r=n,c=0, s=0); while( c<=r, s+=T(r,c); r-=1; c+=1 ); print1(s,", "));

Apparent g.f.: (-b-sqrt(b^2-4*a*c))/(2*a) where a=(6*x^2 - 2*x), b=(-3*x^2 + 4*x - 1), and c=(-x + 1). [determined with Pari's seralgdep()]

Conjecture: D-finite with recurrence +(n+1)*a(n) +3*(-1)*a(n-1) +(-10*n+11)*a(n-2) +3*a(n-3) +9*(n-4)*a(n-4)=0. - R. J. Mathar, Mar 25 2024

A059231 Number of different lattice paths running from (0,0) to (n,0) using steps from S = {(k,k) or (k,-k): k positive integer} that never go below the x-axis.

Original entry on oeis.org

1, 1, 5, 29, 185, 1257, 8925, 65445, 491825, 3768209, 29324405, 231153133, 1841801065, 14810069497, 120029657805, 979470140661, 8040831465825, 66361595715105, 550284185213925, 4582462506008253, 38306388126997785, 321327658068506121, 2703925940081270205

Offset: 0

Wenjin Woan, Jan 20 2001

If y = x*A(x) then 4*y^2 - (1 + 3*x)*y + x = 0 and x = y*(1 - 4*y) / (1 - 3*y). - Michael Somos, Sep 28 2003
a(n) = A059450(n, n). - Michael Somos, Mar 06 2004
The Hankel transform of this sequence is 4^binomial(n+1,2). - Philippe Deléham, Oct 29 2007
a(n) is the number of Schroder paths of semilength n in which there are no (2,0)-steps at level 0 and at a higher level they come in 3 colors. Example: a(2)=5 because we have UDUD, UUDD, UBD, UGD, and URD, where U=(1,1), D=(1,-1), while B, G, and R are, respectively, blue, green, and red (2,0)-steps. - Emeric Deutsch, May 02 2011
Shifts left when INVERT transform applied four times. - Benedict W. J. Irwin, Feb 02 2016

			a(3) = 29 since the top row of Q^2 = (5, 8, 16, 0, 0, 0, ...), and 5 + 8 + 16 = 29.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.
Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.
Zhi Chen and Hao Pan, Identities involving weighted Catalan, Schroder and Motzkin paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=1, b=4.
Curtis Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28 (the sequence d_n).
Curtis Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.
Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
Joseph P. S. Kung and Anna de Mier, Catalan lattice paths with rook, bishop and spider steps, J. Comb. Theor., Series A (2013) Vol. 120, Issue 2, 379-389.
Gregory J. Morrow, Laws relating runs and steps in gambler’s ruin, Stochastic Proc. Appl. (2024) Vol. 125, Issue 5, 2010-2025.
Gregory Morrow, Some probability distributions and integer sequences related to rook paths, Univ. Colorado Springs (2024). See pp. 1, 4, 15, 22. DOI
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.
Paveł Szabłowski, Beta distributions whose moment sequences are related to integer sequences listed in the OEIS, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
Wen-jin Woan, Diagonal lattice paths, Congr. Numer. 151 (2001) 173-178.

Cf. A000108, A001003, A007564, A127846.
Row sums of A086873.
Column k=2 of A227578. - Alois P. Heinz, Jul 17 2013

gf := (1+3*x-sqrt(9*x^2-10*x+1))/(8*x): s := series(gf, x, 100): for i from 0 to 50 do printf(`%d,`,coeff(s, x, i)) od:
A059231_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := a[w-1]+4*add(a[j]*a[w-j-1],j=1..w-1) od;
convert(a, list) end: A059231_list(20); # Peter Luschny, May 19 2011

Join[{1},Table[-I 3^n/2LegendreP[n,-1,5/3],{n,40}]] (* Harvey P. Dale, Jun 09 2011 *)
Table[Hypergeometric2F1[-n, 1 - n, 2, 4], {n, 0, 22}] (* Arkadiusz Wesolowski, Aug 13 2012 *)

{a(n) = if( n<0, 0, polcoeff( (1 + 3*x - sqrt(1 - 10*x + 9*x^2 + x^2 * O(x^n))) / (8*x), n))}; /* Michael Somos, Sep 28 2003 */

{a(n) = if( n<0, 0, n++; polcoeff( serreverse( x * (1 - 4*x) / (1 - 3*x) + x * O(x^n)), n))}; /* Michael Somos, Sep 28 2003 */

# Algorithm of L. Seidel (1877)
def A059231_list(n) :
    D = [0]*(n+2); D[1] = 1
    R = []; b = False; h = 1
    for i in range(2*n) :
        if b :
            for k in range(1, h, 1) : D[k] += 2*D[k+1]
        else :
            for k in range(h, 0, -1) : D[k] += 2*D[k-1]
            h += 1
        b = not b
        if b : R.append(D[1])
    return R
A059231_list(23)  # Peter Luschny, Oct 19 2012

a(n) = Sum_{k=0..n} 4^k*N(n, k) where N(n, k) = (1/n)*binomial(n, k)*binomial(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 10 2003
a(n) = 3^n/2*LegendreP(n, -1, 5/3). - Vladeta Jovovic, Sep 17 2003
G.f.: (1 + 3*x - sqrt(1 - 10*x + 9*x^2)) / (8*x) = 2 / (1 + 3*x + sqrt(1 - 10*x + 9*x^2)). - Michael Somos, Sep 28 2003
a(n) = Sum_{k=0..n} A088617(n, k)*4^k*(-3)^(n-k). - Philippe Deléham, Jan 21 2004
With offset 1: a(1)=1, a(n) = -3*a(n-1) + 4*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004
D-finite with recurrence a(n) = (5(2n-1)a(n-1) - 9(n-2)a(n-2))/(n+1) for n>=2; a(0)=a(1)=1. - Emeric Deutsch, Mar 20 2004
Moment representation: a(n)=(1/(8*Pi))*Int(x^n*sqrt(-x^2+10x-9)/x,x,1,9)+(3/4)*0^n. - Paul Barry, Sep 30 2009
a(n) = upper left term in M^n, M = the production matrix:
  1, 1
  4, 4, 4
  1, 1, 1, 1
  4, 4, 4, 4, 4
  1, 1, 1, 1, 1, 1
  ... - Gary W. Adamson, Jul 08 2011
a(n) is the sum of top row terms of Q^(n-1), where Q = the following infinite square production matrix:
  1, 4, 0, 0, 0, ...
  1, 1, 4, 0, 0, ...
  1, 1, 1, 4, 0, ...
  1, 1, 1, 1, 4, ...
  ... - Gary W. Adamson, Aug 23 2011
G.f.: (1+3*x-sqrt(9*x^2-10*x+1))/(8*x)=(1+3*x -G(0))/(4*x) ; G(k)= 1+x*3-x*4/G(k+1); (continued fraction, 1-step ). - Sergei N. Gladkovskii, Jan 05 2012
a(n) ~ sqrt(2)*3^(2*n+1)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 11 2012
a(n) = A127846(n) for n>0. - Philippe Deléham, Apr 03 2013
0 = a(n)*(+81*a(n+1) - 225*a(n+2) + 36*a(n+3)) + a(n+1)*(+45*a(n+1) + 82*a(n+2) - 25*a(n+3)) + a(n+2)*(+5*a(n+2) + a(n+3)) for all n>=0. - Michael Somos, Aug 25 2014
G.f.: 1/(1 - x/(1 - 4*x/(1 - x/(1 - 4*x/(1 - x/(1 - ...)))))), a continued fraction. - Ilya Gutkovskiy, Aug 10 2017

A279212 Fill an array by antidiagonals upwards; in the top left cell enter a(0)=1; thereafter, in the n-th cell, enter the sum of the entries of those earlier cells that can be seen from that cell.

Original entry on oeis.org

1, 1, 2, 2, 6, 11, 4, 15, 39, 72, 8, 37, 119, 293, 543, 16, 88, 330, 976, 2364, 4403, 32, 204, 870, 2944, 8373, 20072, 37527, 64, 464, 2209, 8334, 26683, 74150, 176609, 331072, 128, 1040, 5454, 22579, 79534, 246035, 673156, 1595909, 2997466, 256, 2304, 13176, 59185, 226106, 762221, 2303159, 6231191, 14721429, 27690124

Offset: 0

N. J. A. Sloane, Dec 24 2016

"That can be seen from" means "that are on the same row, column, diagonal, or antidiagonal as".
Inspired by A279967.
Conjecture: Every column has a finite number of odd entries, and every row and diagonal have an infinite number of odd entries. - Peter Kagey, Mar 28 2020. The conjecture about columns is true, see that attached pdf file from Alec Jones.
The "look" keyword refers to Peter Kagey's bitmap. - N. J. A. Sloane, Mar 29 2020
The number of sequences of queen moves from (1, 1) to (n, k) in the first quadrant moving only up, right, diagonally up-right, or diagonally up-left. - Peter Kagey, Apr 12 2020
Column 0 gives A011782. In the column 1, the only powers of 2 occur at positions A233328(k) with value a(k(k+1)/2 + 1), k >=1 (see A335903). Conjecture: Those are the only multiple occurrences of numbers greater than 1 in this sequence (checked through the first 2000 antidiagonals). - Hartmut F. W. Hoft, Jun 29 2020

			The array begins:
i/j|  0    1    2     3     4      5      6       7       8
-------------------------------------------------------------
0  |  1    2   11    72   543   4403  37527  331072 2997466 ...
1  |  1    6   39   293  2364  20072 176609 1595909 ...
2  |  2   15  119   976  8373  74150 673156 ...
3  |  4   37  330  2944 26683 246035 ...
4  |  8   88  870  8334 79534 ...
5  | 16  204 2209 22579 ...
6  | 32  464 5454 ...
7  | 64 1040 ...
8  |128 ...
  ...
For example, when we get to the antidiagonal that reads 4, 15, 39, ..., the reason for the 39 is that from that cell we can see one cell that has been filled in above it (containing 11), one cell to the northwest (2), two cells to the west (1, 6), and two to the southwest (4, 15), for a total of a(8) = 39.
The next pair of duplicates greater than 2 is 2^20 = 1048576 = a(154) = a(231), located in antidiagonals 17 = A233328(2) and 21, respectively. For additional duplicate numbers in this sequence see A335903.  - _Hartmut F. W. Hoft_, Jun 29 2020

Alois P. Heinz, Antidiagonals n = 0..200, flattened (first 20 antidiagonals from Alec Jones)
Alec Jones, Proof that columns have finitely many odd entries.
Peter Kagey, Bitmap showing parity of first 1024 rows and 512 columns. (Odd values are white; even values are black.)
Peter Kagey, Animated example illustrating the first fifteen terms.

Cf. A064642 is analogous if a cell can only "see" its immediate neighbors.
Cf. A035002, A059450, A132439, A279966, A279967, A279211.
See A280026, A280027 for similar sequences based on a spiral.
Cf. A011782, A335903.

s[0, 0] = 1; s[i_, j_] := s[i, j] = Sum[s[k, j], {k, 0, i-1}] + Sum[s[i, k], {k, 0, j-1}] + Sum[s[i+j-k, k], {k, 0, j-1}] + Sum[s[i-k-1, j-k-1], {k, 0, Min[i, j] - 1}]
aDiag[m_] := Map[s[m-#, #]&, Range[0, m]]
a279212[n_] := Flatten[Map[aDiag, Range[0, n]]]
a279212[9] (* data - 10 antidiagonals;  Hartmut F. W. Hoft, Jun 29 2020 *)

T(0, 0) = 1; T(i, j) = Sum_{k=0..i-1} T(k, j) + Sum_{k=0..j-1} T(i, k) + Sum_{k=0..j-1} T(i+j-k, k) + Sum_{k=0..min(i, j)-1} T(i-k-1, j-k-1), with recursion upwards along antidiagonals. - Hartmut F. W. Hoft, Jun 29 2020

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).

A334017 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 up, right, and diagonal up-left moves.

Original entry on oeis.org

1, 1, 2, 2, 5, 10, 4, 13, 33, 63, 8, 32, 98, 240, 454, 16, 76, 269, 777, 1871, 3539, 32, 176, 702, 2295, 6420, 15314, 29008, 64, 400, 1768, 6393, 19970, 54758, 129825, 246255, 128, 896, 4336, 17088, 58342, 176971, 478662, 1129967, 2145722, 256, 1984, 10416

Offset: 1

Peter Kagey, Apr 12 2020

First row is A175962.

			Table begins:
n\k|  1   2     3      4       5        6         7          8
---+----------------------------------------------------------
  1|  1   2    10     63     454     3539     29008     246255
  2|  1   5    33    240    1871    15314    129825    1129967
  3|  2  13    98    777    6420    54758    478662    4266102
  4|  4  32   269   2295   19970   176971   1593093   14532881
  5|  8  76   702   6393   58342   536080   4965056   46345046
  6| 16 176  1768  17088  163041  1550809  14765863  140982374
  7| 32 400  4336  44280  440602  4332221  42373370  413689403
  8| 64 896 10416 111984 1159580 11771312 118190333 1179448443
For example, the T(2,2) = 5 sequences of permissible queen's moves from (1,1) to (2,2) are:
(1,1) -> (1,2) -> (2,2),
(1,1) -> (2,1) -> (1,2) -> (2,2),
(1,1) -> (2,1) -> (2,2),
(1,1) -> (2,1) -> (3,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 for first 1024 rows and columns. (Even and odd entries and represented by black and white pixels respectively.)

Cf. A175962.
Cf. A035002 (up, right), A059450 (right, up-left), A132439 (up, right, up-right), A279212 (up, right, up-left), A334016 (right, up-right, up-left).
A033877 is the analog for king moves. For both king and queen moves, A094727 is the length of the longest sequence of moves.

cp's OEIS Frontend

A086871 Row sums of A059450.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

PARI

Formula

Extensions

A086866 Third column of A059450.

Views

Author

Keywords

Links

Programs

Mathematica

Formula

Extensions

A368773 Antidiagonal sums of A059450.

Views

Author

Keywords

Crossrefs

Programs

Maple

PARI

Formula

A059231 Number of different lattice paths running from (0,0) to (n,0) using steps from S = {(k,k) or (k,-k): k positive integer} that never go below the x-axis.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Sage

Formula

A279212 Fill an array by antidiagonals upwards; in the top left cell enter a(0)=1; thereafter, in the n-th cell, enter the sum of the entries of those earlier cells that can be seen from that cell.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

A334017 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 up, right, and diagonal up-left moves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs