|
| |
|
|
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.
|
|
9
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
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. [From N. J. A. Sloane (njas(AT)research.att.com), Sep 20 2009]
|
|
|
REFERENCES
| Sr. Arworn, An algorithm for the number of endomorphisms on paths, Disc. Math., 309 (2009), 94-103 (see p. 95).
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 (njas(AT)research.att.com), Sep 20 2009]
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..300
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 Thurston (benthurston27(AT)yahoo.com), 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. [From Joseph Myers (jsm(AT)polyomino.org.uk), Dec 23 2008]
a(n) = 2 * Sum_{k=1..n-1} k*A110971(n,k). [From N. J. A. Sloane (njas(AT)research.att.com), Sep 20 2009]
|
|
|
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.
|
|
|
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 Thurston (benthurston27(AT)yahoo.com), Oct 04 2006
|
|
|
CROSSREFS
| Cf. A110971, A152086.
Sequence in context: A158920 A178438 A143123 * A156664 A025169 A111282
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 Thurston (benthurston27(AT)yahoo.com), Oct 04 2006
a(20) onwards from David Wasserman (dwasserm(AT)earthlink.net), Apr 26 2008
Edited by N. J. A. Sloane (njas(AT)research.att.com), Jan 03 2009 and Sep 23 2010
|
| |
|
|
