login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A063886 Number of n-step walks on a line starting from the origin but not returning to it. 17
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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, [(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

REFERENCES

D. Perrin, A conjecture on rational sequences, pp. 267-274 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Emeric Deutsch, Problem 11424, American Mathematical Monthly, March, 2009.

FORMULA

G.f.: sqrt((1+2*x)/(1-2*x)).

a(n+1) = 2*C(n, [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-2x/(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

Conjecture: n*a(n) -2*a(n-1) +4*(-n+2)*a(n-2)=0. - R. J. Mathar, Dec 03 2012

G.f.: 1/G(0), where G(k)= 1 - 2*x/(1 + 2*x/(1 + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 26 2013

G.f.: G(0), where G(k)= 1 + 2*x/(1 - 2*x/(1 + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 26 2013

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). - Sergei N. Gladkovskii, Jul 26 2013

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

EXAMPLE

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

MAPLE

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

MATHEMATICA

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

PROG

(Python)

from math import ceil

from gmpy import comb

def a(n):

.return 2*comb(n-2, ceil(n/2)-1) # David Nacin, Feb 29 2012

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

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

CROSSREFS

Cf. A000984, A130777.

Apart from initial terms, same as A182027.

Sequence in context: A059123 A001679 A030435 * A003000 A216957 A122536

Adjacent sequences:  A063883 A063884 A063885 * A063887 A063888 A063889

KEYWORD

nonn

AUTHOR

Henry Bottomley, Aug 28 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 26 00:51 EDT 2017. Contains 284111 sequences.