login
Number of different keys with n cuts, depths between 1 and 7 and depth difference at most 1 between adjacent cut depths.
(Formerly M4366 N1832)
5

%I M4366 N1832 #46 Apr 13 2022 13:25:16

%S 1,7,19,53,149,421,1193,3387,9627,27383,77923,221805,631469,1797957,

%T 5119593,14578387,41514003,118218823,336653331,958698053,2730124261,

%U 7774706437,22140438345,63050541515,179552587883,511322221559

%N Number of different keys with n cuts, depths between 1 and 7 and depth difference at most 1 between adjacent cut depths.

%C Also number of base 7 n-digit numbers with adjacent digits differing by one or less.

%C [Empirical] a(base,n)=a(base-1,n)+3^(n-1) for base>=n; a(base,n)=a(base-1,n)+3^(n-1)-2 when base=n-1. - _R. H. Hardin_, Dec 26 2006

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Vincenzo Librandi, <a href="/A002714/b002714.txt">Table of n, a(n) for n = 0..1000</a>

%H C. A. Coulson, <a href="http://www.jstor.org/stable/3613451">How Many different Keys?</a>, Math. Gaz. vol 53 no 383 (1969), 7-13.

%H C. A. Coulson, <a href="/A002714/a002714.pdf">How many different keys?</a>, Math. Gaz. vol 53 no 383 (1969), 7-13. [Annotated scanned copy]

%H Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, <a href="http://arxiv.org/abs/0809.0551">Smooth words and Chebyshev polynomials</a>, arXiv:0809.0551v1 [math.CO], 2008.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-2,-4,1).

%F G.f.: (2*x^4 - 5*x^3 - 7*x^2 + 3*x + 1)/(-x^4 + 4*x^3 + 2*x^2 - 4*x + 1); (from the Knopfmacher et al. reference). - _Joerg Arndt_, Aug 10 2012

%p A002714:=-(7-9*z-9*z**2+3*z**3)/(-1+4*z-2*z**2-4*z**3+z**4); # conjectured by _Simon Plouffe_ in his 1992 dissertation; correct up to offset

%p T := proc(d,n) option remember ; if n = 1 then 1; else if d = 7 then T(d,n-1)+T(d-1,n-1) ; elif d = 1 then T(d,n-1)+T(d+1,n-1) ; else T(d-1,n-1)+T(d,n-1)+T(d+1,n-1) ; fi ; fi ; end: A002714 := proc(n) local d ; add( T(d,n),d=1..7) ; end: seq(A002714(n),n=1..35) ; # _R. J. Mathar_, Jun 15 2008

%t CoefficientList[Series[(2*x^4-5*x^3-7*x^2+3*x+1)/(-x^4+4*x^3+2*x^2-4*x+1),{x,0,200}],x] (* _Vincenzo Librandi_, Aug 13 2012 *)

%t Join[{1}, LinearRecurrence[{4, -2, -4, 1}, {7, 19, 53, 149}, 30]] (* _Jean-François Alcover_, Jan 07 2019 *)

%o (S/R) stvar $[N]:(0..M-1) init $[]:=0 asgn $[]->{*} kill +[i in 0..N-2](($[i]`-$[i+1]`>1)+($[i+1]`-$[i]`>1))

%o (PARI)

%o /* from the Knopfmacher et al. reference */

%o default(realprecision,99); /* using floats */

%o sn(n,k)=1/n*sum(i=1,k,sumdiv(n,j,eulerphi(j)*(1+2*cos(i*Pi/(k+1)))^(n/j)));

%o vector(66,n, if (n==1,1,round(sn(n-1,7))) )

%o /* _Joerg Arndt_, Aug 13 2012 */

%K nonn

%O 0,2

%A _N. J. A. Sloane_

%E Information added from A126361, offset changed to 0 by _Joerg Arndt_, Aug 13 2012