|
%I #65 Oct 13 2022 02:52:04
%S 1,5,24,116,560,2704,13056,63040,304384,1469696,7096320,34264064,
%T 165441536,798822400,3857055744,18623512576,89922273280,434183143424,
%U 2096421666816,10122419240960,48875363631104,235991131488256,1139465980477440,5501828447862784
%N On a 3 X 3 board, number of n-move routes of chess king ending in a given side square.
%C Number of aa-avoiding words of length n on alphabet {a,b,c,d,e}. - _Tanya Khovanova_, Jan 11 2007
%C Binomial transform of A164589 and second binomial transform of A096886. [Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]
%C From _Johannes W. Meijer_, Aug 01 2010: (Start)
%C The a(n) represent the number of n-move paths of a chess king on a 3 X 3 board that end or start in a given side square m (m = 2, 4, 6, 8).
%C Inverse binomial transform of A001109 (without the leading 0).
%C (End)
%C Number of independent vertex subsets of the graph obtained by attaching two pendant edges to each vertex of the path graph P_n (see A235116). Example: a(1)=5; indeed, P_1 is the one-vertex graph and after attaching two pendant vertices we obtain the path graph ABC; the independent vertex subsets are: empty, {A}, {B}, {C}, and {A,C}.
%C Number of simple paths from corner to diagonally opposite corner on a 2 X n grid with king moves allowed. - _Andrew Howroyd_, Nov 06 2019
%C Number of 4-compositions of n+1 restricted to parts 1 and 2 (and allowed zeros); see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 16 2020
%H Indranil Ghosh, <a href="/A086347/b086347.txt">Table of n, a(n) for n = 0..1459</a>
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.
%H Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H Mike Oakes, <a href="http://groups.yahoo.com/group/primenumbers/message/12980">KingMovesForPrimes</a>.
%H Zak Seidov, <a href="http://groups.yahoo.com/group/primenumbers/message/12947">KingMovesForPrimes</a>.
%H Zak Seidov et al., <a href="/A086346/a086346.txt">New puzzle? King moves for primes</a>, digest of 28 messages in primenumbers group, Jul 13 - Jul 23, 2003. [Cached copy]
%H Sleephound, <a href="http://groups.yahoo.com/group/primenumbers/message/12976">KingMovesForPrimes</a>.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (4,4).
%F a(n) = (Sqrt[2]/32)((2+Sqrt[8])^(n+2)-(2-Sqrt[8])^(n+2))
%F G.f.: (1+x)/(1-4*x-4*x^2). a(n) = A057087(n) + A057087(n-1). - _Ralf Stephan_, Feb 01 2004
%F a(n) = 4*a(n-1) + 4*a(n-2). - _Tanya Khovanova_, Jan 11 2007
%F Limit(a(n+k)/a(k),k=infinity) = A084128(n) + 2*A057087(n-1)*sqrt(2). - _Johannes W. Meijer_, Aug 01 2010
%e a(3) = 116 = 5^3 - 9 (aaa, aab, aac, aad, aae, baa, caa, daa, eaa). [Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]
%p with(LinearAlgebra): nmax:=19; m:=2; A[5]:= [1,1,1,1,0,1,1,1,1]: A:=Matrix([[0,1,0,1,1,0,0,0,0],[1,0,1,1,1,1,0,0,0],[0,1,0,0,1,1,0,0,0],[1,1,0,0,1,0,1,1,0],A[5],[0,1,1,0,1,0,0,1,1],[0,0,0,1,1,0,0,1,0],[0,0,0,1,1,1,1,0,1],[0,0,0,0,1,1,0,1,0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax); # _Johannes W. Meijer_, Aug 01 2010
%p # second Maple program:
%p a:= n-> (<<0|1>, <4|4>>^n. <<1, 5>>)[1,1]:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Oct 12 2022
%t Table[(Sqrt[2]/32)((2+Sqrt[8])^(n+2)-(2-Sqrt[8])^(n+2)), {n, 0, 19}]
%Y Row 2 of A329118.
%Y Row sums of A235113.
%Y Cf. A086346, A086348.
%Y Cf. A028859.
%Y Cf. A126473. - _Johannes W. Meijer_, Aug 01 2010
%K nonn,easy
%O 0,2
%A _Zak Seidov_, Jul 17 2003
%E Offset changed and edited by _Johannes W. Meijer_, Jul 15 2010
|
