A000531 -id:A000531 - cp's OEIS frontend

A118964 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that have k double rises above the x-axis (n >= 1, k >= 0).

2, 5, 1, 14, 5, 1, 42, 19, 8, 1, 132, 67, 40, 12, 1, 429, 232, 166, 79, 17, 1, 1430, 804, 634, 395, 145, 23, 1, 4862, 2806, 2335, 1708, 879, 249, 30, 1, 16796, 9878, 8480, 6824, 4376, 1823, 404, 38, 1, 58786, 35072, 30691, 26137, 19334, 10521, 3542, 625, 47, 1

Offset: 1

Emeric Deutsch, May 07 2006

A Grand Dyck path of semilength n is a path in the half-plane x >= 0, starting at (0,0), ending at (2n,0) and consisting of steps u = (1,1) and d = (1,-1); a double rise in a Grand Dyck path is an occurrence of uu in the path.

For all double rises (above, below and on the x-axis), see A118963.

			T(3,1) = 5 because we have u/ududd,u/uddud,udu/udd,duu/udd and u/udddu (the double rises above the x-axis are indicated by /).
Triangle starts:
  2;
  5,   1;
  14,  5,  1;
  42,  19, 8,  1;
  132, 67, 40, 12, 1;

Alois P. Heinz, Rows n = 1..141, flattened

T(n,0) = A000108(n+1) (Catalan numbers), T(n,1) = A114277(n-2).

Cf. A000984 (row sums), A000108, A000531, A118963.

C:=(1-sqrt(1-4*z))/2/z: r:=(1-z-t*z-sqrt(z^2*t^2-2*z^2*t-2*z*t+z^2-2*z+1))/2/t/z: G:=(1+r)/(1-z*C*(1+r))-1: Gser:=simplify(series(G,z=0,15)): for n from 1 to 11 do P[n]:=coeff(Gser,z,n) od: for n from 1 to 11 do seq(coeff(P[n],t,j),j=0..n-1) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(abs(y)>x, 0,
      `if`(x=0, 1, expand(`if`(t=2, z, 1)*b(x-1, y+1,
      `if`(y>=0, min(t+1, 2), 1)) +b(x-1, y-1, 1))))
    end:
T:= n-> (p-> seq(coeff(p,z,i), i=0..n-1))(b(2*n, 0, 1)):
seq(T(n), n=1..12);  # Alois P. Heinz, Jun 16 2014

b[x_, y_, t_] := b[x, y, t] = If[Abs[y] > x, 0, If[x == 0, 1, Expand[If[t == 2, z, 1]*b[x-1, y+1, If[y >= 0, Min[t+1, 2], 1]] + b[x-1, y-1, 1]]]]; T[n_] := Function[ {p}, Table[Coefficient[p, z, i], {i, 0, n-1}]][b[2*n, 0, 1]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

Sum_{k>=0} k*T(n,k) = A000531(n-1).

G.f.: G(t,z) = (1+r)/[1-z(1+r)C]-1, where r = r(t,z) is the Narayana function, defined by (1+r)(1+tr)z = r, r(t,0) = 0 and C = C(z) = [1-sqrt(1-4z)]/(2z) is the Catalan function. More generally, the g.f. H = H(t,s,u,z), where t,s and u mark double rises above, below and on the x-axis, respectively, is H = [1 + r(s,z)]/[1 - z(1 + tr(t,z))(1 + ur(s,z))].

Keyword tabf changed to tabl by Michel Marcus, Apr 07 2013

A172060 The number of returns to the origin in all possible one-dimensional walks of length 2n.

Original entry on oeis.org

0, 2, 14, 76, 374, 1748, 7916, 35096, 153254, 661636, 2831300, 12030632, 50826684, 213707336, 894945944, 3734901296, 15540685574, 64496348516, 267060529364, 1103587381256, 4552196053844, 18747042089816, 77092267322984, 316602500019536, 1298657603761244

Offset: 0

Geoffrey Critzer, Jan 24 2010

a(n)/4^n is the expected number of times a gambler will return to his break-even point while making 2n equal wagers on the outcome of a fair coin toss. Note the surprisingly low and slow growth of this expectation.

			a(2) = 14 because there are fourteen 0's in the set of all possible walks of length 4: {{-1, -2, -3, -4}, {-1, -2, -3, -2}, {-1, -2, -1, -2}, {-1, -2, -1, 0}, {-1, 0, -1, -2}, {-1, 0, -1, 0}, {-1, 0, 1, 0}, {-1, 0, 1, 2}, {1, 0, -1, -2}, {1, 0, -1, 0}, {1, 0, 1, 0}, {1, 0, 1, 2}, {1, 2, 1, 0}, {1, 2, 1, 2}, {1, 2, 3, 2}, {1, 2, 3, 4}}.

W. Feller, An Introduction to Probability Theory and its Applications, Vol 1, 3rd ed. New York: Wiley, pp. 67-97, 1968.

M. Bona, Non-overlapping permutation patterns, PU. M. A. Vol. 22 (2012), 99-105. - _N. J. A. Sloane_, Oct 13 2012

[Factorial(2*n+1)/Factorial(n)^2 - 4^n : n in [0..30]]; // Wesley Ivan Hurt, Mar 24 2015

[0] cat [n le 1 select 2 else 4*Self(n-1)+ Binomial(2*n,n): n in [1..30]]; // Vincenzo Librandi, Mar 25 2015

A172060:=n->(2*n+1)!/(n!)^2 - 4^n: seq(A172060(n), n=0..30); # Wesley Ivan Hurt, Mar 24 2015

Table[Count[Flatten[Map[Accumulate, Strings[{-1, 1}, n]]], 0], {n, 0, 20, 2}]
CoefficientList[Series[(1 - (1 - 4 x)^(1/2)) / (1 - 4 x)^(3/2), {x, 0, 33}], x] (* Vincenzo Librandi, Mar 25 2015 *)

a(n) = (2n+1)!/(n!)^2 - 4^n.
a(n) = 4*a(n-1) + binomial(2n,n).
O.g.f.: (1-(1-4x)^(1/2))/(1-4x)^(3/2).
a(n) = A002457(n) - A000302(n). - Wesley Ivan Hurt, Mar 24 2015
a(n) = 2*A000531(n). - R. J. Mathar, Jan 03 2018

A296769 Row sums of A296662.

Original entry on oeis.org

1, 7, 38, 187, 874, 3958, 17548, 76627, 330818, 1415650, 6015316, 25413342, 106853668, 447472972, 1867450648, 7770342787, 32248174258, 133530264682, 551793690628, 2276098026922, 9373521044908, 38546133661492, 158301250009768, 649328801880622

Offset: 0

Peter Luschny, Dec 20 2017

nonn

Cf. A000531, A296662, bisection of A296663.

a := n -> 2^(1 + 2*n)*((2*GAMMA(5/2 + n))/(sqrt(Pi)*GAMMA(2 + n)) - 1):
seq(a(n), n=0..23);
# alternative
A296769 := proc(n)
    2^(2*n)*(doublefactorial(2*n+3)/(1+n)/doublefactorial(2*n)-2) ;
end proc:
seq(A296769(n),n=0..10) ; # R. J. Mathar, Jan 03 2018

a(n) = 2^(1 + 2*n)*((2*Gamma(5/2 + n))/(sqrt(Pi)*Gamma(2 + n)) - 1).
a(n) ~ 4^(n+1)*(sqrt(n/Pi) - 1/2).
a(n) = A000531(n+1). - R. J. Mathar, Jan 03 2018
a(n) = A033876(n)-2^(2*n+1). - R. J. Mathar, Jan 03 2018

A157513 Triangle of numbers of walks in the quarter-plane, of length 2n beginning and ending at the origin using steps {(1,1), (1,0), (-1,0), (-1,-1)} (Gessel steps) arranged according to the number of times the steps (1,1) and (-1,-1) occur.

Original entry on oeis.org

1, 1, 1, 2, 7, 2, 5, 37, 38, 5, 14, 177, 390, 187, 14, 42, 806, 3065, 3175, 874, 42, 132, 3566, 20742, 37260, 22254, 3958, 132, 429, 15485, 127575, 351821, 365433, 141442, 17548, 429, 1430, 66373, 734332, 2876886, 4597444, 3100670, 839068, 76627, 1430

Offset: 0

Arvind Ayyer, Mar 02 2009

The first and the last terms in each row are Catalan numbers. The sum in each row gives the Gessel sequence.

			For n=2, there are 2 walks of length 4 where the diagonal steps (1,1) and (-1,-1) occur zero times [(1,0),(1,0),(-1,0),(-1,0)] and [(1,0),(-1,0),(1,0),(-1,0)];
7 walks where the diagonal steps occur once [(1,0),(-1,0),(1,1),(-1,-1)], [(1,1),(-1,-1),(1,0),(-1,0)],  [(1,0),(1,1),(-1,0),(-1,-1)],  [(1,0),(1,1),(-1,-1),(-1,0)],  [(1,1),(1,0),(-1,0),(-1,-1)],  [(1,1),(1,0),(-1,-1),(-1,0)],  [(1,1),(-1,0),(1,0),(-1,-1)];
and finally 2 walks where the diagonal steps occur twice [(1,1),(1,1),(-1,-1),(-1,-1)] and [(1,1),(-1,-1),(1,1),(-1,-1)].
Triangle begins:
1;
1,     1;
2,     7,    2;
5,    37,   38,    5;
14,  177,  390,  187,   14;
42,  806, 3065, 3175,  874,  42;

Alois P. Heinz, Table of n, a(n) for n = 0..5049
Arvind Ayyer, Towards a human proof of Gessel's conjecture, arXiv:0902.2329 [math.CO], 2009.
Manuel Kauers, Christoph Koutschan and Doron Zeilberger, Proof of Ira Gessel's Lattice Path Conjecture
Marko Petkovsek and Herbert S. Wilf, On a conjecture of Ira Gessel, arXiv:0807.3202 [math.CO], 2008.

Cf. A135404, A000531, A000108.

b:= proc(n, k, t, x, y) option remember; `if` (min(n, x, y, k, t, n-x)<0, 0, `if` (n=0, `if` (max(n, k, t)=0, 1, 0), b(n-1, k-1, t, x+1, y+1) +b(n-1, k, t, x+1, y) +b(n-1, k, t, x-1, y) +b(n-1, k, t-1, x-1, y-1))) end: T:= (n,k)-> b(2*n, k, k, 0, 0):
seq (seq (T(n, k), k=0..n), n=0..8);  # Alois P. Heinz, Jul 04 2011

b[n_, k_, t_, x_, y_] := b[n, k, t, x, y] = If[Min[n, x, y, k, t, n-x] < 0, 0, If[n == 0, If[Max[n, k, t] == 0, 1, 0], b[n-1, k-1, t, x+1, y+1] + b[n - 1, k, t, x+1, y] + b[n-1, k, t, x-1, y] + b[n-1, k, t-1, x-1, y-1]]]; T[n_, k_] := b[2*n, k, k, 0, 0]; Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 27 2016, after Alois P. Heinz *)

A090299 Table T(n,k), n>=0 and k>=0, read by antidiagonals : the k-th column given by the k-th polynomial K_k related to A090285.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 5, 10, 5, 1, 14, 35, 22, 7, 1, 42, 126, 93, 38, 9, 1, 132, 462, 386, 187, 58, 11, 1, 429, 1716, 1586, 874, 325, 82, 13, 1, 1430, 6435, 6476, 3958, 1686, 515, 110, 15, 1, 4862, 24310, 26333, 17548, 8330, 2934, 765, 142, 17, 1

Offset: 0

Philippe Deléham, Jan 25 2004

Read as a number triangle, this is the Riordan array (c(x),x/sqrt(1-4x)) where c(x) is the g.f. of A000108. - Paul Barry, May 16 2005

			row n=0 : 1, 1, 2, 5, 14, 42, 132, 429, ... see A000108.
row n=1 : 1, 3, 10, 35, 126, 462, 1716, 6435, ... see A001700.
row n=2 : 1, 5, 22, 93, 386, 1586, 6476, ... see A000346.
row n=3 : 1, 7, 38, 187, 874, 3958, 17548, ... see A000531.
row n=4 : 1, 9, 58, 325, 1686, 8330, 39796, ... see A018218.

Other rows : A029887, A042941, A045724, A042985, A045492. Columns : A000012, A005408. Row n is the convolution of the row (n-j) with A000984, A000302, A002457, A002697 (first term omitted), A002802, A038845, A020918, A038846, A020920 for j=1, 2, ..9 respectively.

T(n, k) = K_k(n)= Sum_{j>=0} A090285(k, j)*2^j*binomial(n, j). T(n, 1) = 2*n+1. T(n, 2) = 2*A028387(n).

Corrected by Alford Arnold, Oct 18 2006

A143019 Infinite square array read by antidiagonals: a(q,n) is the coefficient of z^n in the series expansion of C(z)^q/(1-4z)^(3/2), where C(z) = (1-sqrt(1-4z))/(2z) is the Catalan function (q,n = 0,1,2,...).

Original entry on oeis.org

1, 1, 6, 1, 7, 30, 1, 8, 38, 140, 1, 9, 47, 187, 630, 1, 10, 57, 244, 874, 2772, 1, 11, 68, 312, 1186, 3958, 12012, 1, 12, 80, 392, 1578, 5536, 17548, 51480, 1, 13, 93, 485, 2063, 7599, 25147, 76627, 218790, 1, 14, 107, 592, 2655, 10254, 35401, 112028, 330818

Offset: 0

Emeric Deutsch, Jul 24 2008

a(q,n) = a(q-1,n) + a(q+1,n-1).

Row 0 is A002457; row 1 is A000531; row 2 is A029760; row 3 is A045720.

			Array starts:
  1, 6, 30, 140,  630, ...
  1, 7, 38, 187,  874, ...
  1, 8, 47, 244, 1186, ...
  1, 9, 57, 312, 1578, ...
  ...

Cf. A002457, A000531, A029760, A045720.

a:=proc(q,n) options operator, arrow: sum(4^i*binomial(2*n-2*i+q, n-i), i= 0.. n) end proc: aa:=proc(q,n) options operator, arrow: a(q-1,n-1) end proc: matrix(10,10,aa); # yields sequence in matrix form

a(q,n) = Sum_{i=0..n} 4^i*binomial(2n-2i+q, n-i).

A164705 T(n,k) = binomial(2n-k,n) * 2^(k-1), T(0,0)=1; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 3, 3, 2, 10, 10, 8, 4, 35, 35, 30, 20, 8, 126, 126, 112, 84, 48, 16, 462, 462, 420, 336, 224, 112, 32, 1716, 1716, 1584, 1320, 960, 576, 256, 64, 6435, 6435, 6006, 5148, 3960, 2640, 1440, 576, 128, 24310, 24310, 22880, 20020, 16016, 11440, 7040, 3520, 1280, 256

Offset: 0

Geoffrey Critzer, Aug 23 2009

T(n,k) is the number of 2n digit binary sequences in which the (n+1)th zero occurs in the (2n-k+1)th position. T(n,k)/2^(2n-1) is the probability sought in Banach's matchbox problem. Row sum is 2^(2n-1). T(n,0) = T(n,1) = A088218(n).

			T(2,1) = 3 because there are 3 length 4 binary sequences in which the third zero appears in the fourth position: {0,0,1,0}, {0,1,0,0}, {1,0,0,0}.
Triangle begins
   1;
   1,   1;
   3,   3,   2;
  10,  10,   8,  4;
  35,  35,  30, 20,  8;
 126, 126, 112, 84, 48, 16;
 ...

Sean A. Irvine, Computing A382782, 2025.

Row sums give A081294.
Main diagonal gives A011782.
Cf. A000531, A088218.

T:= (n, k)-> ceil(binomial(2*n-k, n)*2^(k-1)):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Apr 06 2025

Table[Table[Binomial[2 n - k, n]*2^(k - 1), {k, 0, n}], {n, 0, 9}] // Grid

Sum_{k=0..n} k * T(n,k) = A000531(n). - Alois P. Heinz, Apr 06 2025

T(0,0)=1 prepended by Sean A. Irvine, Apr 05 2025

A200613 Number of quasi-abelian ideals in the affine Lie algebra sl_n^{hat}.

Original entry on oeis.org

1, 3, 11, 44, 183, 774, 3294, 14034, 59711, 253430, 1072506, 4525168, 19036726, 79861404, 334155036, 1394789214, 5808981711, 24143440374, 100156051746, 414762312504, 1714844273586, 7079573497524, 29187378344676, 120180109515204, 494264431607718, 2030539136846844

Offset: 1

N. J. A. Sloane, Nov 19 2011

nonn

Christian Krattenthaler has shown that a(n)=((n+4)/4)*binomial(2*n,n)-3*2^(2*n-3). This implies that a(n)=A194460(n) - A000531(n-1). The latter fact was first empirically observed by D. S. McNeil. [Volodymyr Mazorchuk, Sep 14 2012]

Karin Baur and Volodymyr Mazorchuk, Combinatorial analogues of ad-nilpotent ideals for untwisted affine Lie algebras, arXiv:1108.3659 [math.RA]

a(n) = ((n+4)/4)*binomial(2*n,n)-3*2^(2*n-3);

a(n) = ((n+4)/4)*binomial(2*n,n)-3*2^(2*n-3). [Volodymyr Mazorchuk, Sep 14 2012]

cp's OEIS Frontend

A118964 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that have k double rises above the x-axis (n >= 1, k >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A172060 The number of returns to the origin in all possible one-dimensional walks of length 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Programs

Magma

Magma

Maple

Mathematica

Formula

A296769 Row sums of A296662.

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

A157513 Triangle of numbers of walks in the quarter-plane, of length 2n beginning and ending at the origin using steps {(1,1), (1,0), (-1,0), (-1,-1)} (Gessel steps) arranged according to the number of times the steps (1,1) and (-1,-1) occur.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A090299 Table T(n,k), n>=0 and k>=0, read by antidiagonals : the k-th column given by the k-th polynomial K_k related to A090285.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A143019 Infinite square array read by antidiagonals: a(q,n) is the coefficient of z^n in the series expansion of C(z)^q/(1-4z)^(3/2), where C(z) = (1-sqrt(1-4z))/(2z) is the Catalan function (q,n = 0,1,2,...).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A164705 T(n,k) = binomial(2n-k,n) * 2^(k-1), T(0,0)=1; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A200613 Number of quasi-abelian ideals in the affine Lie algebra sl_n^{hat}.