A047073 -id:A047073 - cp's OEIS frontend

A063886 Number of n-step walks on a line starting from the origin but not returning to it.

1, 2, 2, 4, 6, 12, 20, 40, 70, 140, 252, 504, 924, 1848, 3432, 6864, 12870, 25740, 48620, 97240, 184756, 369512, 705432, 1410864, 2704156, 5408312, 10400600, 20801200, 40116600, 80233200, 155117520, 310235040, 601080390, 1202160780, 2333606220, 4667212440

Offset: 0

Henry Bottomley, Aug 28 2001

A Chebyshev transform of A007877(n+1). The g.f. is transformed to (1+x)/((1-x)(1+x^2)) under the mapping G(x)->(1/(1+x^2))G(1/(1+x^2)). - Paul Barry, Oct 12 2004
a(n-1) = 2*C(n-2, floor((n-2)/2)) is also the number of bit strings of length n in which the number of 00 substrings is equal to the number of 11 substrings. For example, when n = 4 we have 4 such bit strings: 0011, 0101, 1010, and 1100. - Angel Plaza, Apr 23 2009
Hankel transform is A120617. - Paul Barry, Aug 10 2009
The Hankel transform of a(n) is (-2)^C(n+1,2). The Hankel transform of (-1)^C(n+1,2)*a(n) is (-1)^C(n+1,2)*A164584(n). - Paul Barry, Aug 17 2009
For n > 1, a(n) is also the number of n-step walks starting from the origin and returning to it exactly once. - Geoffrey Critzer, Jan 24 2010
-a(n) is the Z-sequence for the Riordan array A130777. (See the W. Lang link under A006232 for A- and Z-sequences for Riordan matrices). - Wolfdieter Lang, Jul 12 2011
Number of subsets of {1,...,n} in which the even elements appear as often at even positions as at odd positions. - Gus Wiseman, Mar 17 2018

			a(4) = 6 because there are six length four walks that do not return to the origin: {-1, -2, -3, -4}, {-1, -2, -3, -2}, {-1, -2, -1, -2}, {1, 2, 1, 2}, {1, 2, 3, 2}, {1, 2, 3, 4}. There are also six such walks that return exactly one time: {-1, -2, -1, 0}, {-1, 0, -1, -2}, {-1, 0, 1, 2}, {1, 0, -1, -2}, {1, 0, 1, 2}, {1, 2, 1, 0}. - _Geoffrey Critzer_, Jan 24 2010
The a(5) = 12 subsets in which the even elements appear as often at even positions as at odd positions: {}, {1}, {3}, {5}, {1,3}, {1,5}, {2,4}, {3,5}, {1,2,4}, {1,3,5}, {2,4,5}, {1,2,4,5}. - _Gus Wiseman_, Mar 17 2018

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Emeric Deutsch, Problem 11424, The American Mathematical Monthly, Vol. 116, No. 3 (March 2009), p. 277.
D. Perrin, A conjecture on rational sequences, pp. 267-274 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.

Apart from initial terms, same as A182027.
Cf. A000108, A000246, A000712, A000984, A001405, A001700, A002420, A006232, A007877, A026010, A028329, A045931, A047073, A089849, A097613, A106180, A120617, A130777, A130780, A138364, A164584, A171966, A239241, A300787, A300788, A300789.
Cf. A307768 (complementary event).

[1] cat [2*Binomial(n-1, Floor((n-1)/2)): n in [1..40]]; // G. C. Greubel, Jun 07 2023

seq(seq(binomial(2*j,j)*i, i=1..2),j=0..16); # Zerinvary Lajos, Apr 28 2007
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n+1,
       4*a(n-2) +2*(a(n-1) -4*a(n-2))/n)
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 10 2014
# third program:
A063886 := series(BesselI(0, 2*x)*(1 + x*2 + x*Pi*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x), x = 0, 34): seq(n!*coeff(A063886, x, n), n = 0 .. 33); # Mélika Tebni, Jun 17 2024

Table[Length[Select[Map[Accumulate, Strings[{-1, 1}, n]], Count[ #, 0] == 0 &]], {n, 0, 20}] (* Geoffrey Critzer, Jan 24 2010 *)
CoefficientList[Series[Sqrt[(1+2x)/(1-2x)],{x,0,40}],x] (* Harvey P. Dale, Apr 28 2016 *)

PARI
```
a(n)=(n==0)+2*binomial(n-1,(n-1)\2)
```

a(n) = 2^n*prod(k=0,n-1,(k/n+1/n)^((-1)^k)); \\ Michel Marcus, Dec 03 2013

from math import ceil
from sympy import binomial
def a(n):
    if n==0: return 1
    return 2*binomial(n-1,(n-1)//2)
print([a(n) for n in range(18)])
# David Nacin, Feb 29 2012

[2*binomial(n-1, (n-1)//2) + int(n==0) for n in range(41)] # G. C. Greubel, Jun 07 2023

G.f.: sqrt((1+2*x)/(1-2*x)).
a(n+1) = 2*C(n, floor(n/2)) = 2*A001405(n); a(2n) = C(2n, n) = A000984(n) = 4*a(2n-2)-|A002420(n)| = 4*a(2n-2)-2*A000108(n-1) = 2*A001700(n-1); a(2n+1) = 2*a(2n) = A028329(n).
2*a(n) = A047073(n+1).
a(n) = Sum_{k=0..n} abs(A106180(n,k)). - Philippe Deléham, Oct 06 2006
a(n) = Sum_{k=0..n} (k+1)binomial(n, (n-k)/2) ( 1-cos((k+1)*Pi/2) (1+(-1)^(n-k))/(n+k+2) ). - Paul Barry, Oct 12 2004
G.f.: 1/(1-2*x/(1+x/(1+x/(1-x/(1-x/(1+x/(1+x/(1-x/(1-x/(1+ ... (continued fraction). - Paul Barry, Aug 10 2009
G.f.: 1 + 2*x/(G(0)-x+x^2) where G(k)= 1 - 2*x^2 - x^4/G(k+1); (continued fraction, 1-step). - Sergei N. Gladkovskii, Aug 10 2012
D-finite with recurrence: n*a(n) = 2*a(n-1) + 4*(n-2)*a(n-2). - R. J. Mathar, Dec 03 2012
From Sergei N. Gladkovskii, Jul 26 2013: (Start)
G.f.: 1/G(0), where G(k) = 1 - 2*x/(1 + 2*x/(1 + 1/G(k+1) )); (continued fraction).
G.f.: G(0), where G(k) = 1 + 2*x/(1 - 2*x/(1 + 1/G(k+1) )); (continued fraction).
G.f.: W(0)/2*(1+2*x), where W(k) = 1 + 1/(1 - 2*x/(2*x + (k+1)/(x*(2*k+1))/W(k+1) )), abs(x) < 1/2; (continued fraction). (End)
a(n) = 2^n*Product_{k=0..n-1} (k/n + 1/n)^((-1)^k). - Peter Luschny, Dec 02 2013
G.f.: G(0), where G(k) = 1 + 2*x*(4*k+1)/((2*k+1)*(1+2*x) - (2*k+1)*(4*k+3)*x*(1+2*x)/((4*k+3)*x + (k+1)*(1+2*x)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 19 2014
From Peter Bala, Mar 29 2024: (Start)
a(n) = 2^n * Sum_{k = 0..n} (-1)^(n+k)*binomial(1/2, k)*binomial(- 1/2, n-k) = 2^n * A000246(n)/n!.
a(n) = (1/2^n) * binomial(2*n, n) * hypergeom([-1/2, -n], [1/2 - n], -1). (End)
E.g.f.: BesselI(0, 2*x)*(1 + x*(2 + Pi)*StruveL(1, 2*x)) - Pi*x*BesselI(1, 2*x)*StruveL(0, 2*x). - Stefano Spezia, May 11 2024
a(n) = A089849(n) + A138364(n). - Mélika Tebni, Jun 17 2024
From Amiram Eldar, Aug 15 2025: (Start)
Sum_{n>=0} 1/a(n) = Pi/(3*sqrt(3)) + 2.
Sum_{n>=0} (-1)^n/a(n) = 2/3 + Pi/(9*sqrt(3)). (End)

A028329 Twice central binomial coefficients.

Original entry on oeis.org

2, 4, 12, 40, 140, 504, 1848, 6864, 25740, 97240, 369512, 1410864, 5408312, 20801200, 80233200, 310235040, 1202160780, 4667212440, 18150270600, 70690527600, 275693057640, 1076515748880, 4208197927440, 16466861455200, 64495207366200, 252821212875504, 991837065896208

Offset: 0

Mohammad K. Azarian

Central elements in the even-Pascal triangle A028326.
If Y is a 3-subset of an 2n-set X then, for n>=3, a(n-1) is the number of (n+1)-subsets of X having at least two elements in common with Y. - Milan Janjic, Dec 16 2007
a(n) denotes the number of ways one can reach the (n,n) point in an n X n grid via the point (n-1, n-1) starting from (0,0) when moving right and up is allowed [From Avik Roy (avik_3.1416(AT)yahoo.co.in), Jan 29 2009]
It appears that a(n-1) is also the number of quivers in the mutation class of twisted types BD_n and CD_n for n >= 3. - Christian Stump, Nov 03 2010
This is the case m = n+1 in the Catalan's formula (2m)!*(2n)!/(m!*(m+n)!*n!) - see Umberto Scarpis in References. - Bruno Berselli, Apr 27 2012
From Ran Pan, Feb 01 2016: (Start)
a(n) is the number of North-East paths from (0,0) to (n+1,n+1) that bounce off the diagonal y = x an even number of times. Details can be found in Section 4.2 in Pan and Remmel's link.
a(n) is the number of North-East paths from (0,0) to (n+1,n+1) that cross the diagonal y = x an even number of times. Details can be found in Section 4.3 in Pan and Remmel's link. (End)

Umberto Scarpis, Sui numeri primi e sui problemi dell'analisi indeterminata in Questioni riguardanti le matematiche elementari, Nicola Zanichelli Editore (1924-1927, third Edition), page 11.

Vincenzo Librandi, Table of n, a(n) for n = 0..300
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Ran Pan and Jeffrey B. Remmel, Paired patterns in lattice paths, arXiv:1601.07988 [math.CO], 2016.

Bisection of A047073, A063886.
First differences of A054113.
Cf. A000984, A095660, A100320, A162551.
Cf. A028326, A028327, A028328, A028330, A028331, A028332.

[2*(n+1)*Catalan(n): n in [0..30]]; // G. C. Greubel, Jul 13 2024

seq(add(binomial(2*n,n),k=1..2),n=0..23); # Zerinvary Lajos, Dec 14 2007

Table[2Binomial[2n,n],{n,0,30}] (* Harvey P. Dale, Aug 08 2011 *)

PARI
```
a(n)=2*binomial(2*n,n)
```

[2*binomial(2*n,n) for n in range(31)] # G. C. Greubel, Jul 13 2024

G.f.: 2/sqrt(1 - 4*x).
a(n) = 2*A000984(n).
a(n) = 2 * binomial(2*n, n).
a(n) = A100320(n) = A095660(2*n,n) for n > 0. - Reinhard Zumkeller, Apr 08 2012
G.f.: G(0), where G(k)= 1 + 1/(1 - 2*x*(2*k + 1)/(2*x*(2*k + 1) + (k + 1)/ G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 07 2013
a(n) = binomial(2*n+2, n+1) - A162551(n). - Ran Pan, Feb 01 2016
D-finite with recurrence: n*a(n) + 2*(-2*n+1)*a(n-1)=0. - R. J. Mathar, Jan 17 2020
E.g.f.: 2*exp(2*x)*BesselI(0, 2*x). - Stefano Spezia, May 11 2024

Edited by Michael Somos, Sep 13 2003

A047072 Array A read by diagonals: A(h,k)=number of paths consisting of steps from (0,0) to (h,k) such that each step has length 1 directed up or right and no step touches the line y=x unless x=0 or x=h.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 3, 2, 2, 3, 1, 1, 4, 5, 4, 5, 4, 1, 1, 5, 9, 5, 5, 9, 5, 1, 1, 6, 14, 14, 10, 14, 14, 6, 1, 1, 7, 20, 28, 14, 14, 28, 20, 7, 1, 1, 8, 27, 48, 42, 28, 42, 48, 27, 8, 1, 1, 9, 35, 75, 90, 42, 42, 90, 75, 35, 9, 1

Offset: 0

Clark Kimberling

			Array, A(n, k), begins as:
  1, 1,  1,  1,  1,   1,   1,   1, ...;
  1, 2,  1,  2,  3,   4,   5,   6, ...;
  1, 1,  2,  2,  5,   9,  14,  20, ...;
  1, 2,  2,  4,  5,  14,  28,  48, ...;
  1, 3,  5,  5, 10,  14,  42,  90, ...;
  1, 4,  9, 14, 14,  28,  42, 132, ...;
  1, 5, 14, 28, 42,  42,  84, 132, ...;
  1, 6, 20, 48, 90, 132, 132, 264, ...;
Antidiagonals, T(n, k), begins as:
  1;
  1,  1;
  1,  2,  1;
  1,  1,  1,  1;
  1,  2,  2,  2,  1;
  1,  3,  2,  2,  3,  1;
  1,  4,  5,  4,  5,  4,  1;
  1,  5,  9,  5,  5,  9,  5,  1;
  1,  6, 14, 14, 10, 14, 14,  6,  1;

G. C. Greubel, Antidiagonals n = 0..50, flattened
R. K. Guy, Catwalks, sandsteps and Pascal pyramids, J. Integer Sequences, Vol. 3 (2000), Article #00.1.6.

Cf. A000007, A000027, A000096, A002420.
Cf. A005586, A025174, A047079, A063886.
Cf. A047073, A047074, A047079.
The following are all versions of (essentially) the same Catalan triangle: A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Diagonals give A000108, A000245, A002057, A000344, A003517, A000588, A003518, A003519, A001392, ...

b:= func< n | n eq 0 select 1 else 2*Catalan(n-1) >;
function A(n,k)
  if k eq n then return b(n);
  elif k gt n then return Binomial(n+k-1, n) - Binomial(n+k-1, n-1);
  else return Binomial(n+k-1, k) - Binomial(n+k-1, k-1);
  end if; return A;
end function;
// [[A(n,k): k in [0..12]]: n in [0..12]];
T:= func< n,k | A(n-k, k) >;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Oct 13 2022

A[, 0]= 1; A[0, ]= 1; A[h_, k_]:= A[h, k]= If[(k-1>h || k-1Jean-François Alcover, Mar 06 2019 *)

def A(n,k):
    if (k==n): return 2*catalan_number(n-1) + 2*int(n==0)
    elif (k>n): return binomial(n+k-1, n) - binomial(n+k-1, n-1)
    else: return binomial(n+k-1, k) - binomial(n+k-1, k-1)
def T(n,k): return A(n-k, k)
# [[A(n,k) for k in range(12)] for n in range(12)]
flatten([[T(n,k) for k in range(n+1)] for n in range(12)]) # G. C. Greubel, Oct 13 2022

A(n, n) = 2*[n=0] - A002420(n),
A(n, n+1) = 2*A000108(n-1), n >= 1.
From G. C. Greubel, Oct 13 2022: (Start)
T(n, n-1) = A000027(n-2) + 2*[n<3], n >= 1.
T(n, n-2) = A000096(n-4) + 2*[n<5], n >= 2.
T(n, n-3) = A005586(n-6) + 4*[n<7] - 2*[n=3], n >= 3.
T(2*n, n) = 2*A000108(n-1) + 3*[n=0].
T(2*n-1, n-1) = T(2*n+1, n+1) = A000180(n).
T(3*n, n) = A025174(n) + [n=0]
Sum_{k=0..n} T(n, k) = 2*A063886(n-2) + [n=0] - 2*[n=1]
Sum_{k=0..n} (-1)^k * T(n, k) = A000007(n).
Sum_{k=0..floor(n/2)} T(n, k) = A047079(n). (End)

A047074 a(n) = Sum_{i=0..floor(n/2)} T(i,n-i), array T as in A047072.

Original entry on oeis.org

1, 1, 3, 2, 5, 6, 14, 20, 45, 70, 154, 252, 546, 924, 1980, 3432, 7293, 12870, 27170, 48620, 102102, 184756, 386308, 705432, 1469650, 2704156, 5616324, 10400600, 21544100, 40116600, 82907640, 155117520, 319929885, 601080390, 1237518450

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A047072, A047073, A047079.

b:= func< n | n eq 0 select 1 else 2*Catalan(n-1) >;
function A(n, k)
  if k eq n then return b(n);
  elif k gt n then return Binomial(n+k-1, n) - Binomial(n+k-1, n-1);
  else return Binomial(n+k-1, k) - Binomial(n+k-1, k-1);
  end if; return A;
end function;
[(&+[A(j, n-j): j in [0..Floor(n/2)]]): n in [0..50]]; // G. C. Greubel, Oct 29 2022

A[n_, k_]:= A[n, k]= If[k==n, 2*CatalanNumber[n-1] +2*Boole[n==0], If[k>n, Binomial[n+k-1,n] -Binomial[n+k-1,n-1], Binomial[n+k-1,k] - Binomial[n+k-1, k - 1]]];
A047074[n_]:= Sum[A[j, n-j], {j,0,Floor[n/2]}] +Boole[n==0];
Table[A047074[n], {n, 0, 50}] (* G. C. Greubel, Oct 29 2022 *)

def A047072(n, k): # array
    if (k==n): return 2*catalan_number(n-1) + 2*int(n==0)
    elif (k>n): return binomial(n+k-1, n) - binomial(n+k-1, n-1)
    else: return binomial(n+k-1, k) - binomial(n+k-1, k-1)
def A047074(n): return sum( A047072(j, n-j) for j in range((n//2)+1) )
[A047074(n) for n in range(51)] # G. C. Greubel, Oct 29 2022

Extra leading 1 removed by Sean A. Irvine, May 11 2021

A047079 a(n) = Sum_{i=0..floor(n/2)} A047072(i, n-2*i).

Original entry on oeis.org

1, 1, 2, 3, 3, 4, 7, 9, 14, 23, 33, 52, 85, 127, 202, 329, 503, 804, 1307, 2027, 3250, 5277, 8263, 13276, 21539, 33957, 54638, 88595, 140373, 226108, 366481, 582865, 939622, 1522487, 2428517, 3917412, 6345929, 10145769, 16374126

Offset: 0

Clark Kimberling

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A047072, A047073, A047074.

b:= func< n | n eq 0 select 1 else 2*Catalan(n-1) >;
function A(n, k)
  if k eq n then return b(n);
  elif k gt n then return Binomial(n+k-1, n) - Binomial(n+k-1, n-1);
  else return Binomial(n+k-1, k) - Binomial(n+k-1, k-1);
  end if; return A;
end function;
[(&+[A(j, n-2*j): j in [0..Floor(n/2)]]): n in [0..50]]; // G. C. Greubel, Oct 29 2022

T[n_, k_]:= T[n, k]= If[k==n, 2*CatalanNumber[n-1] +2*Boole[n==0], If[k>n, Binomial[n+k-1,n] -Binomial[n+k-1,n-1], Binomial[n+k-1,k] -Binomial[n+k-1, k- 1]]];
A047079[n_]:= Sum[T[j, n-2*j], {j,0,Floor[n/2]}] +Boole[n==0];
Table[A047079[n], {n,0,50}] (* G. C. Greubel, Oct 29 2022 *)

def A047072(n, k): # array
    if (k==n): return 2*catalan_number(n-1) + 2*int(n==0)
    elif (k>n): return binomial(n+k-1, n) - binomial(n+k-1, n-1)
    else: return binomial(n+k-1, k) - binomial(n+k-1, k-1)
def A047079(n): return sum( A047072(j, n-2*j) for j in range(((n+1)//2)+1) )
[A047079(n) for n in range(51)] # G. C. Greubel, Oct 29 2022

Name improved by Sean A. Irvine, May 11 2021

A257546 Number of permutations of length n such that numbers at odd positions are monotone and numbers at even positions are also monotone.

Original entry on oeis.org

1, 1, 2, 6, 24, 40, 80, 140, 280, 504, 1008, 1848, 3696, 6864, 13728, 25740, 51480, 97240, 194480, 369512, 739024, 1410864, 2821728, 5408312, 10816624, 20801200, 41602400, 80233200, 160466400, 310235040, 620470080, 1202160780, 2404321560, 4667212440

Offset: 0

Ran Pan, Apr 29 2015

Robert Israel, Table of n, a(n) for n = 0..2993
Ran Pan, Exercise C, Project P.

Cf. A047073, A000142.

[1,1,2,6] cat [4*Binomial(n,Floor(n/2)): n in [4..40]]; // Vincenzo Librandi, Apr 30 2015

f:= gfun:-rectoproc({a(n+2)= 4*(1+n)*a(n)/(n+3) + 2*a(n+1)/(n+3), seq(a(n)=[1,1,2,6,24,40,80][n+1],n=0..5)},a(n),remember):
map(f, [$0..100]); # Robert Israel, May 12 2015

Table[If[n <= 4, n!, 4 Binomial[n, Floor[n/2]]], {n, 31}] (* Michael De Vlieger, Apr 29 2015 *)

a(n) = 4*binomial(n,floor(n/2)) for n > 4; a(n) = n! for n <= 4.
From Robert Israel, Apr 30 2015: (Start)
G.f.: -3*(1+x)*(1+2*x^2) - 2/x + 2*(2+1/x)/sqrt(1-4*x^2).
a(n+2) = (4*(1+n)*a(n) + 2*a(n+1))/(n+3) for n >= 4. (End)

More terms from Vincenzo Librandi, Apr 30 2015

cp's OEIS Frontend

A063886 Number of n-step walks on a line starting from the origin but not returning to it.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

SageMath

Formula

A028329 Twice central binomial coefficients.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A047072 Array A read by diagonals: A(h,k)=number of paths consisting of steps from (0,0) to (h,k) such that each step has length 1 directed up or right and no step touches the line y=x unless x=0 or x=h.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A047074 a(n) = Sum_{i=0..floor(n/2)} T(i,n-i), array T as in A047072.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Extensions

A047079 a(n) = Sum_{i=0..floor(n/2)} A047072(i, n-2*i).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Extensions

A257546 Number of permutations of length n such that numbers at odd positions are monotone and numbers at even positions are also monotone.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions