|
| |
|
|
A096261
|
|
Number of n-tuples of 0,1,2,3,4,5,6,7,8,9 without consecutive digits.
|
|
3
|
|
|
|
1, 10, 91, 828, 7534, 68552, 623756, 5675568, 51642104, 469892512, 4275561136, 38903414208, 353982925023, 3220897542254, 29307009588171, 266665052127080, 2426390512890816, 22077774624328776, 200886102122914612
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Sketch of a proof for a general base b >= 2: Let a(n) be the 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 with i those ending with 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) = Sum_{j=0..b-1} s(n,j), 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).
|
|
|
LINKS
|
Index entries for linear recurrences with constant coefficients, signature (10,-9,8,-7,6,-5,4,-3,2,-1).
|
|
|
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.
G.f.: 1/(1 - 10*x + 9*x^2 - 8*x^3 + 7*x^4 - 6*x^5 + 5*x^6 - 4*x^7 + 3*x^8 - 2*x^9 + x^10). - Colin Barker, Dec 06 2012
|
|
|
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[n_]:= a[n]= If[n<0, 0, If[n==0, 1, 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, 25}] (* Robert G. Wilson v, Aug 02 2004 *)
LinearRecurrence[{10, -9, 8, -7, 6, -5, 4, -3, 2, -1}, {1, 10, 91, 828, 7534, 68552, 623756, 5675568, 51642104, 469892512}, 30] (* Harvey P. Dale, Dec 16 2013 *)
|
|
|
PROG
|
(Magma)
R<x>:=PowerSeriesRing(Integers(), 30);
Coefficients(R!( 1/(1-10*x+9*x^2-8*x^3+7*x^4-6*x^5+5*x^6-4*x^7+3*x^8-2*x^9+x^10) )); // G. C. Greubel, Apr 17 2021
(Sage)
P.<x> = PowerSeriesRing(ZZ, prec)
return P( 1/(1-10*x+9*x^2-8*x^3+7*x^4-6*x^5+5*x^6-4*x^7+3*x^8-2*x^9+x^10) ).list()
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
base,nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
