cp's OEIS Frontend

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

%I A096261 #27 Apr 18 2021 02:17:46
%S A096261 1,10,91,828,7534,68552,623756,5675568,51642104,469892512,4275561136,
%T A096261 38903414208,353982925023,3220897542254,29307009588171,
%U A096261 266665052127080,2426390512890816,22077774624328776,200886102122914612
%N A096261 Number of n-tuples of 0,1,2,3,4,5,6,7,8,9 without consecutive digits.
%C A096261 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.
%C A096261 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).
%H A096261 Alois P. Heinz, <a href="/A096261/b096261.txt">Table of n, a(n) for n = 0..1000</a>
%H A096261 <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (10,-9,8,-7,6,-5,4,-3,2,-1).
%F A096261 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.
%F A096261 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
%p A096261 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);
%t A096261 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 *)
%t A096261 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 *)
%o A096261 (Magma)
%o A096261 R<x>:=PowerSeriesRing(Integers(), 30);
%o A096261 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
%o A096261 (Sage)
%o A096261 def A096261_list(prec):
%o A096261     P.<x> = PowerSeriesRing(ZZ, prec)
%o A096261     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()
%o A096261 A096261_list(30) # _G. C. Greubel_, Apr 17 2021
%Y A096261 Case b=3 is A095263.
%Y A096261 Column k=10 of A277666.
%K A096261 base,nonn,easy
%O A096261 0,2
%A A096261 _Seppo Mustonen_, Aug 01 2004
%E A096261 More terms from _Robert G. Wilson v_, Aug 02 2004