A182027 -id:A182027 - 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)

A371358 Number of binary strings of length n which have more 00 than 01 substrings.

Original entry on oeis.org

0, 0, 1, 2, 4, 10, 21, 42, 89, 184, 371, 758, 1546, 3122, 6315, 12782, 25780, 51962, 104759, 210934, 424404, 853806, 1716759, 3450158, 6932169, 13924260, 27959805, 56130762, 112662414, 226080318, 453595341, 909925794, 1825052601, 3660020992, 7339006091

Offset: 0

Robert P. P. McKone, Mar 19 2024

nonn

			a(4) = 4: 0000, 0001, 1000, 1100.
a(5) = 10: 00000, 00001, 00010, 00011, 00100, 01000, 10000, 10001, 11000, 11100.

Robert P. P. McKone, Table of n, a(n) for n = 0..1698

Cf. A163493 (equal 00 and 01), A371564 (more 01 than 00), A090129 (equal 01 and 10), A182027 (equal 00 and 11), A370048 (one more 00 than 01).

Cf. A000079(n-2) (more 01 than 10, for n>=2).

b:= proc(n, l, t) option remember; `if`(n+t<1, 0, `if`(n=0, 1,
      add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))
    end:
a:= n-> b(n, 2, 0):
seq(a(n), n=0..34);  # Alois P. Heinz, Mar 20 2024

tup[n_] := Tuples[{0, 1}, n];
cou[lst_List] := Count[lst, {0, 0}] > Count[lst, {0, 1}];
par[lst_List] := Partition[lst, 2, 1];
a[n_] := Map[cou, Map[par, tup[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

{ a371358(n) = 2^(n-1) - sum(k=0, n\3, binomial(2*k,k) * (2*binomial(n-2*k,n-3*k) - binomial(n-2*k-1,n-3*k))) / 2; } \\ Max Alekseyev, May 01 2024

a(n) = 2^n - A163493(n) - A371564(n).
a(n) = ((4*n^2-15*n+7)*a(n-1) -(5*n^2-22*n+14)*a(n-2) +2*(3*n^2-14*n+10)*a(n-3) -4*(3*n^2-16*n+18)*a(n-4) +8*(n-2)*(n-4)*a(n-5)) / (n*(n-3)) for n>=5. - Alois P. Heinz, Mar 20 2024
For n >= 2, a(n) = 2*a(n-1) + A163493(n-1) - A163493(n-2) - A370048(n-2). - Max Alekseyev, Apr 30 2024
a(n) = 2^(n-1) - (1/2) * Sum_{k=0..floor(n/3)} binomial(2*k,k) * (2*binomial(n-2*k,n-3*k) - binomial(n-2*k-1,n-3*k)). - Max Alekseyev, May 01 2024
G.f. 1/(1-2*x)/2 - (1+x)/(2*sqrt(1-2*x+x^2-4*x^3+4*x^4)). - Max Alekseyev, Apr 30 2024

A371564 Number of binary strings of length n which have more 01 than 00 substrings.

Original entry on oeis.org

0, 0, 1, 3, 6, 13, 28, 56, 113, 231, 464, 930, 1875, 3766, 7547, 15151, 30398, 60917, 122116, 244786, 490435, 982544, 1968413, 3942649, 7896116, 15813268, 31665423, 63403245, 126945244, 254152625, 508798604, 1018538560, 2038870881, 4081149015, 8168806568

Offset: 0

Robert P. P. McKone, Mar 27 2024

nonn

			a(4) = 6: 0101, 0110, 0111, 1010, 1011, 1101.
a(5) = 13: 0010, 0100, 0101, 0101, 0110, 0111, 0111, 1010, 1011, 1011, 1101, 1101, 1110.

Cf. A163493 (equal 00 and 01), A371358 (more 00 than 01), A090129 (equal 01 and 10), A182027 (equal 00 and 11), A370048 (one more 00 than 01).

Cf. A000079(n-2) (more 01 than 10, for n>=2).

b:= proc(n, l, t) option remember; `if`(n+t<1, 0, `if`(n=0, 1,
      add(b(n-1, i, t-`if`(l=0, (-1)^i, 0)), i=0..1)))
    end:
a:= n-> b(n, 2, 0):
seq(a(n), n=0..34);  # Alois P. Heinz, Mar 27 2024

tup[n_] := Tuples[{0, 1}, n];
cou[lst_List] := Count[lst, {0, 1}] > Count[lst, {0, 0}];
par[lst_List] := Partition[lst, 2, 1];
a[n_] := Map[cou, Map[par, tup[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

a(n) = 2^n - A163493(n) - A371358(n).
a(n) = (1 - 8*(n-4)*a(n-5) + 4*(3*n-10)*a(n-4) + 2*(8-3*n)*a(n-3) + (5*n-12)*a(n-2) + (7-4*n)*a(n-1))/(1-n) for n>=5.
For n >= 2, a(n) = 2*a(n-1) - A163493(n) + A163493(n-1) + A163493(n-2) + A370048(n-2). - Max Alekseyev, May 01 2024
G.f.: ((1-3*x+2*x^2)^(-1) - (1-2*x+x^2-4*x^3+4*x^4)^(-1/2)) * x / 2. - Max Alekseyev, Apr 30 2024

A370048 Number of binary strings of length n in which the number of substrings 00 is one more than that of substrings 01.

Original entry on oeis.org

0, 0, 1, 1, 2, 6, 10, 18, 40, 76, 141, 285, 558, 1066, 2097, 4121, 8000, 15660, 30763, 60171, 117918, 231690, 454816, 893208, 1756688, 3455580, 6799195, 13388587, 26375466, 51974798, 102470402, 202108730, 398756664, 787025260, 1553900235, 3068937675, 6062944710, 11981429394, 23683822694, 46828287038

Offset: 0

Max Alekseyev, Apr 30 2024

nonn

Cf. A000079, A090129, A163493, A182027, A371358, A371564.

{ a370048(n) = (n > 1) * sum(m=0,(n-1)\3, binomial(2*m,m+1) * binomial(n-1-2*m,m) + binomial(2*m+1,m) * binomial(n-2-2*m,m) ); }

from math import comb
def A370048(n): return 0 if n<2 else 1+sum((x:=comb((k:=m<<1),m+1)*comb(n-1-k,m))+x*(k+1)*(n-1-3*m)//(m*(n-1-k)) for m in range(1,(n+2)//3)) # Chai Wah Wu, May 01 2024

For n >= 2, a(n) = Sum_{m=0..floor((n-1)/3)} binomial(2*m,m+1) * binomial(n-1-2*m,m) + binomial(2*m+1,m) * binomial(n-2-2*m,m).
For n >= 4, a(n) = ( (n-2)*(2*n-1)*(n^2-n-4)*a(n-1) - (n^2-5*n+2)*(n^2+n-4)*a(n-2) + 2*(n-3)*n^2*(2*n-3)*a(n-3) - 4*(n-3)*(n-1)^2*n*a(n-4) ) / (n-2)^2 / (n-1) / (n+2).
a(n) = 2*A371358(n+1) - A371358(n+2) + A163493(n+1) - A163493(n).
G.f. ((1-x^2-2*x^3)*(1-2*x+x^2-4*x^3+4*x^4)^(-1/2) - 1 - x)/x^2/2, which can be expressed in terms of g.f. C(x) = (1-sqrt(1-4*x))/x/2 for Catalan number (A000108) as x*((x+1)*C(x^3/(1-x))-1)/(1-x-2*x^3*C(x^3/(1-x))).

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

A371358 Number of binary strings of length n which have more 00 than 01 substrings.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A371564 Number of binary strings of length n which have more 01 than 00 substrings.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A370048 Number of binary strings of length n in which the number of substrings 00 is one more than that of substrings 01.

Views

Author

Keywords

Crossrefs

Programs

PARI

Python

Formula