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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102699 Number of strings of length n, using as symbols numbers from the set {1, 2, ..., n}, in which consecutive symbols differ by exactly 1. 10
1, 1, 2, 6, 16, 42, 104, 252, 592, 1370, 3112, 6996, 15536, 34244, 74832, 162616, 351136, 754938, 1615208, 3443940, 7314928, 15493676, 32714992, 68918856, 144815456, 303703972, 635554064, 1327816392, 2769049312, 5766417480, 11989472672, 24897569648 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Equally, number of different n-digit numbers, using only the digits 1 through n, where consecutive digits differ by 1. It is assumed that there are n different digits available even when n > 9.

Number of endomorphisms of a path P_n. - N. J. A. Sloane, Sep 20 2009

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..3311 (terms n = 1..300 from T. D. Noe)

Sr. Arworn, An algorithm for the number of endomorphisms on paths, Disc. Math., 309 (2009), 94-103 (see p. 95).

Zhicong Lin and Jiang Zeng, On the number of congruence classes of paths, arXiv preprint arXiv:1112.4026 [math.CO], 2011.

M. A. Michels and U. Knauer, The congruence classes of paths and cycles, Discr. Math., 309 (2009), 5352-5359. See p. 5356. [From N. J. A. Sloane, Sep 20 2009]

Joseph Myers, BMO 2008-2009 Round 1 Problem 1-Generalisation

FORMULA

It appears that the limit of a(n)/a(n-1) is decreasing towards 2. - Ben Paul Thurston, Oct 04 2006

a(n) = (n+1)2^(n-1) - 4(n-1)binomial(n-2,(n-2)/2) for n even, a(n) = (n+1)2^(n-1) - (2n-1)binomial(n-1,(n-1)/2) for n odd. - Joseph Myers, Dec 23 2008

a(n) = 2 * Sum_{k=1..n-1} k*A110971(n,k). - N. J. A. Sloane, Sep 20 2009

G.f.: x * (2*(1 - x) - sqrt(1 - 4*x^2)) / (1 - 2*x)^2. - Michael Somos, Mar 17 2014

0 = a(n) * 8*n^2 - a(n+1) * 4*(n^2 - 2*n - 1) - a(n+2) * 2*(n^2 + 3*n - 2) + a(n+3) * (n-1)*(n+2) for n>0. - Michael Somos, Mar 17 2014

0 = a(n) * (16*a(n+1) - 16*a(n+2) + 4*a(n+3)) + a(n+1) * (-16*a(n+1) + 20*a(n+2) - 4*a(n+3)) + a(n+2) * (-4*a(n+2) + a(n+3)) for n>0. - Michael Somos, Mar 17 2014

EXAMPLE

For example, a(4)=16: the 16 strings are 1212, 1232, 1234, 2121, 2123, 2321, 2323, 2343, 3212, 3232, 3234, 3432, 3434, 4321, 4323, 4343.

G.f. = x + 2*x^2 + 6*x^3 + 16*x^4 + 42*x^5 + 104*x^6 + 252*x^7 + 592*x^8 + ...

MAPLE

p:= 0; paths := proc(m, n, s, t) global p; if(((t+1) <= m) and s <= (n)) then paths(m, n, s+1, t+1); end if; if(((t-1) > 0) and s <= (n)) then paths(m, n, s+1, t-1); end if; if(s = n) then p:=p+1; end if; end proc; sumpaths:=proc(j) global p; p:=0; sp:=0; for h from 1 to j do p:=0; paths(j, j, 1, h); sp:=sp+ p ; end do; sp; end proc; for l from 1 to 50 do sumpaths(l); end do; # Ben Paul Thurston, Oct 04 2006

# second Maple program:

a:= proc(n) option remember;

      `if`(n<5, [1, 1, 2, 6, 16][n+1], ((2*n^2-6*n-4) *a(n-1)

      +(56-32*n+4*n^2) *a(n-2) -8*(n-3)^2 *a(n-3))/ ((n-1)*(n-4)))

    end:

seq(a(n), n=0..30);  # Alois P. Heinz, Nov 23 2012

MATHEMATICA

a[n_] := a[n] = If[n <= 4, n*((n-3)*n+4)/2, ((2*n^2 - 6*n - 4)*a[n-1] + (4*n^2 - 32*n + 56)*a[n-2] - 8*(n-3)^2*a[n-3])/((n-1)*(n-4))]; Table[ a[n], {n, 1, 30}] (* Jean-Fran├žois Alcover, Nov 10 2015, after Alois P. Heinz *)

PROG

(PARI) x='x+O('x^55); Vec(x*(2*(1-x)-sqrt(1-4*x^2))/(1-2*x)^2) \\ Altug Alkan, Nov 10 2015

CROSSREFS

Cf. A110971, A152086.

Main diagonal of A220062. - Alois P. Heinz, Dec 03 2012

Sequence in context: A263592 A178438 A143123 * A266124 A217194 A304662

Adjacent sequences:  A102696 A102697 A102698 * A102700 A102701 A102702

KEYWORD

nonn

AUTHOR

Don Rogers (donrogers42(AT)aol.com), Feb 07 2005

EXTENSIONS

More terms from Ben Paul Thurston, Oct 04 2006

a(20) onwards from David Wasserman, Apr 26 2008

Edited by N. J. A. Sloane, Jan 03 2009 and Sep 23 2010

a(0)=1 prepended by Alois P. Heinz, Apr 17 2017

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 17:13 EDT 2019. Contains 328186 sequences. (Running on oeis4.)