A096261 Number of n-tuples of 0,1,2,3,4,5,6,7,8,9 without consecutive digits.

1, 10, 91, 828, 7534, 68552, 623756, 5675568, 51642104, 469892512, 4275561136, 38903414208, 353982925023, 3220897542254, 29307009588171, 266665052127080, 2426390512890816, 22077774624328776, 200886102122914612

Offset: 0

Author

Seppo Mustonen, Aug 01 2004

Keywords

• base
• nonn
• easy

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

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (10,-9,8,-7,6,-5,4,-3,2,-1).

Crossrefs

Case b=3 is A095263.

Column k=10 of A277666.

Programs

Magma

R:=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

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 *)

Sage

def A096261_list(prec):
    P. = 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()
A096261_list(30) # G. C. Greubel, Apr 17 2021

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

Extensions

More terms from Robert G. Wilson v, Aug 02 2004