|
|
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.
|
|
11
|
|
|
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.
a(n) is also the number of distinct paths of length n starting from the bottom row of an n X n chess board and ending at the top row, such that all the n squares traversed in the path are of the same color. - Kiran Ananthpur Bacche, Oct 25 2022
|
|
LINKS
|
|
|
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
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:
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Don Rogers (donrogers42(AT)aol.com), Feb 07 2005
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|