|
| |
|
|
A096261
|
|
Number of n-tuples of 0,1,2,3,4,5,6,7,8,9 without consecutive digits.
|
|
2
| |
|
|
1, 10, 91, 828, 7534, 68552, 623756, 5675568, 51642104, 469892512, 4275561136, 38903414208, 353982925023, 3220897542254, 29307009588171, 266665052127080, 2426390512890816, 22077774624328776, 200886102122914612
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| Sketch of a proof for a general base b=2,3,...: Let a(n) be number of n-tuples of 0,1,...,b-1 without consecutive digits and s(n,i) the number of them with i (i=0,1,...,b-1) as the last digit. Then it is clear that s(n,i)=a(n-1)-s(n-1,i-1) since when extending a valid n-1-tuple by i those ending by i-1 are not valid as n-tuples.
Thus s(n,0)=a(n-1), s(n,1)=a(n-1)-s(n-1,0)=a(n-1)-a(n-2) and in general s(n,i)=a(n-1)-a(n-2)+a(n-3)-...+(-1)^i*a(n-i-1), i=0,1,...,b-1. Since a(n)=s(n,0)+s(n,1)+...+s(n,b-1), we get the recursion formula a(n)=b*a(n-1)-(b-1)*a(n-2)+(b-2)*a(n-3)-...+(-1)^(b-1)*a(n-b).
|
|
|
FORMULA
| a(n) = 10*a(n-1) - 9*a(n-2) + 8*a(n-3) - 7*a(n-4) + 6*a(n-5) -5*a(n-6) + 4*a(n-7) - 3*a(n-8) + 2*a(n-9) - 1*a(n-10), a(0)=1, a(n)=0, for n<0.
|
|
|
MAPLE
| A096261:=proc(n, b::nonnegint) local s, i; option remember; if n<0 then RETURN(0) fi; if n=0 then RETURN(1) fi; s:=0; for i from 1 to b do s:=s+(-1)^(i-1)*(b-i+1)*A096261(n-i, b); od; end; seq(A096261(i, 10), i=0..20);
|
|
|
MATHEMATICA
| a[ -9] = a[ -8] = a[ -7] = a[ -6] = a[ -5] = a[ -4] = a[ -3] = a[ -2] = a[ -1] = 0; a[0] = 1; a[n_] := a[n] = 10a[n - 1] - 9a[n - 2] + 8a[n - 3] - 7a[n - 4] + 6a[n - 5] - 5a[n - 6] + 4a[n - 7] - 3a[n - 8] + 2a[n - 9] - a[n - 10]; Table[ a[n], {n, 0, 15}] (from Robert G. Wilson v Aug 02 2004)
|
|
|
CROSSREFS
| Case b=3 is A095263.
Sequence in context: A002739 A079928 A002452 * A015455 A110410 A051789
Adjacent sequences: A096258 A096259 A096260 * A096262 A096263 A096264
|
|
|
KEYWORD
| base,nonn
|
|
|
AUTHOR
| Seppo Mustonen (seppo.mustonen(AT)survo.fi), Aug 01 2004
|
|
|
EXTENSIONS
| More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Aug 02 2004
|
| |
|
|
