Displaying 1-10 of 13 results found.
a(n) = a(n-1) + 2*a(n-2) - a(n-3), with a(0) = a(1) = 0, a(2) = 1.
(Formerly M2358)
+10
41
0, 0, 1, 1, 3, 4, 9, 14, 28, 47, 89, 155, 286, 507, 924, 1652, 2993, 5373, 9707, 17460, 31501, 56714, 102256, 184183, 331981, 598091, 1077870, 1942071, 3499720, 6305992, 11363361, 20475625, 36896355, 66484244, 119801329, 215873462, 388991876, 700937471
COMMENTS
a(n+1) = S(n) for n>=1, where S(n) is the number of 01-words of length n, having first letter 1, in which all runlengths of 1's are odd. Example: S(4) counts 1000, 1001, 1010, 1110. See A077865. - Clark Kimberling, Jun 26 2004 For n>=1, number of compositions of n into floor(j/2) kinds of j's (see g.f.). - Joerg Arndt, Jul 06 2011 Counts walks of length n between the first and second nodes of P_3, to which a loop has been added at the end. Let A be the adjacency matrix of the graph P_3 with a loop added at the end. A is a 'reverse Jordan matrix' [0,0,1; 0,1,1; 1,1,0]. a(n) is obtained by taking the (1,2) element of A^n. - Paul Barry, Jul 16 2004 a(n) appears in the formula for the nonnegative powers of rho:= 2*cos(Pi/7), the ratio of the smaller diagonal in the heptagon to the side length s=2*sin(Pi/7), when expressed in the basis <1,rho,sigma>, with sigma:=rho^2-1, the ratio of the larger heptagon diagonal to the side length, as follows. rho^n = C(n)*1 + C(n+1)*rho + a(n)*sigma, n>=0, with C(n) = A052547(n-2). See the Steinbach reference, and a comment under A052547. - Wolfdieter Lang, Nov 25 2010 If with the above notations the power basis <1,rho,rho^2> of Q(rho) is used, nonnegative powers of rho are given by rho^n = -a(n-1)*1 + A052547(n-1)*rho + a(n)*rho^2. For negative powers see A006054. - Wolfdieter Lang, May 06 2011 -a(n-1) also appears in the formula for the nonpositive powers of sigma (see the above comment for the definition, and the Steinbach basis <1,rho,sigma>) as follows: sigma^(-n) = A(n)*1 -a(n+1)*rho -A(n-1)*sigma, with A(n) = A052547(n), A(-1):=0. - Wolfdieter Lang, Nov 25 2010
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. Witula, E. Hetmaniok and D. Slota, Sums of the powers of any order roots taken from the roots of a given polynomial, Proceedings of the 15th International Conference on Fibonacci Numbers and Their Applications (2012).
FORMULA
a(n) = c^(n-2) - a(n-1)*(c-1) + (1/c)*a(n-2) for n > 3 where c = 2*cos(Pi/7). Example: a(7) = 14 = c^5 - 9*(c-1) + 4/c = 18.997607... - 7.21743962... + 2.219832528... - Gary W. Adamson, Jan 24 2010 G.f.: -1 + 1/(1 - Sum_{j>=1} floor(j/2)*x^j). - Joerg Arndt, Jul 06 2011 a(n) = 2^n*(c(1)^(n-1)*(c(1)+c(2)) + c(3)^(n-1)*(c(3)+c(6)) + c(5)^(n-1)*(c(5)+c(4)) )/7, with c(j):=cos(Pi*j/7). - Herbert Kociemba, Dec 18 2011 a(n+1)*(-1)^n*49^(1/3) = (c(1)/c(4))^(1/3)*(2*c(1))^n + (c(2)/c(1))^(1/3)*(2*c(2))^n + (c(4)/c(2))^(1/3)*(2c(4))^n = (c(2)/c(1))^(1/3)*(2*c(1))^(n+1) + (c(4)/c(2))^(1/3)*(c(2))^(n+1) + (c(1)/c(4))^(1/3)*(2*c(4))^(n+1), where c(j) := cos(2Pi*j/7); for the proof, see Witula et al.'s papers. - Roman Witula, Jul 21 2012 G.f.: x^2 / (1 - x / (1 - 2*x / (1 + 5*x / (2 - x / (5 - 2*x))))). - Michael Somos, Jan 20 2017 a(n) ~ r*c^n, where r=0.241717... is one of the roots of 49*x^3-7*x+1, and c=2*cos(Pi/7) (as in Gary W. Adamson's formula). - Daniel Checa, Nov 04 2022
EXAMPLE
G.f. = x^2 + x^3 + 3*x^4 + 4*x^5 + 9*x^6 + 14*x^7 + 28*x^8 + 47*x^9 + ...
Regarding the description "number of compositions of n into floor(j/2) kinds of j's," the a(6)=9 compositions of 6 are (2a, 2a, 2a), (3a, 3a), (2a, 4a), (2a, 4b), (4a, 2a), (4b, 2a), (6a), (6b), (6c). - Bridget Tenner, Feb 25 2022
MAPLE
a[0]:=0: a[1]:=0: a[2]:=1: for n from 3 to 40 do a[n]:=a[n-1]+2*a[n-2]-a[n-3] od:seq(a[n], n=0..40); # Emeric Deutsch
PROG
(Magma) [ n eq 1 select 0 else n eq 2 select 0 else n eq 3 select 1 else Self(n-1) +2*Self(n-2) -Self(n-3): n in [1..40] ]: // Vincenzo Librandi, Aug 19 2011 (Haskell)
a006053 n = a006053_list !! n
a006053_list = 0 : 0 : 1 : zipWith (+) (drop 2 a006053_list)
(zipWith (-) (map (2 *) $ tail a006053_list) a006053_list)
(PARI) {a(n) = if( n<0, n = -1-n; polcoeff( -1 / (1 - 2*x - x^2 + x^3) + x * O(x^n), n), polcoeff( x^2 / (1 - x - 2*x^2 + x^3) + x * O(x^n), n))}; /* Michael Somos, Nov 30 2014 */ (SageMath)
@CachedFunction
if (n<3): return (n//2)
else: return a(n-1) + 2*a(n-2) - a(n-3)
Number of Catalan paths (nonnegative, starting and ending at 0, step +/-1) of 2*n steps with all values <= 5.
+10
21
1, 1, 2, 5, 14, 42, 131, 417, 1341, 4334, 14041, 45542, 147798, 479779, 1557649, 5057369, 16420730, 53317085, 173118414, 562110290, 1825158051, 5926246929, 19242396629, 62479659622, 202870165265, 658715265222, 2138834994142, 6944753544643, 22549473023585
COMMENTS
With interpolated zeros (1,0,1,0,2,...), counts closed walks of length n at start or end node of P_6. The sequence (0,1,0,2,...) counts walks of length n between the start and second node. - Paul Barry, Jan 26 2005 HANKEL transform of sequence and the sequence omitting a(0) is the sequence A130716. This is the unique sequence with that property. - Michael Somos, May 04 2012 a(n) is also the upper left entry of the n-th power of the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: a(n) = ((M_3)^n)[1,1]. Proof: (M_3)^n = b(n-2)*(M_3)^2 - (6*b(n-3) - b(n-4))*M_3 + b(n-3)*1_3, for n >= 0, with b(n) = A005021(n), for n >= -4. For the proof of this see a comment in A005021. Hence (M_3)^n[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0. This proves the 3 X 3 part of the conjecture in A332602 by Gary W. Adamson. The formula for a(n) given below in terms of r = rho(7) = A160389 proves that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796..., because r - 2/r = 0.6920... < 1, and r^2 - 3 = 0.2469... < 1. This limit was conjectured in A332602 by Gary W. Adamson. (End)
FORMULA
G.f.: (1-4*x+3*x^2)/(1-5*x+6*x^2-x^3). - Ralf Stephan, May 13 2003 a(n) = (4/7-4/7*cos(1/7*Pi)^2)*(4*(cos(Pi/7))^2)^n + (1/7-2/7*cos(1/7*Pi) + 4/7*cos(1/7*Pi)^2)*(4*(cos(2*Pi/7))^2)^n + (2/7+2/7*cos(1/7*Pi))*(4*(cos(3*Pi/7))^2)^n for n>=0. - Richard Choulet, Apr 19 2010 G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x / (1 - x))))). - Michael Somos, May 04 2012 In terms of the algebraic number r = rho(7) = A160389 of degree 3 the formula given by Richard Choulet becomes a(n) = (1/7)*(r)^(2*n)*(C1(r) + C2(r)*(r - 2/r)^(2*n) + C3(r)*(r^2 - 3)^(2*n)), with C1(r) = 4 - r^2, C2(r) = 1 - r + r^2, and C3 = 2 + r. a(n) = ((M_3)^n)[1,1] = 2*b(n-2) - 5*b(n-3) + b(n-4), for n >= 0, with the 3 X 3 tridiagonal matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602, and b(n) = A005021(n) (with offset n >= -4). (End)
EXAMPLE
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 131*x^6 + 417*x^7 + 1341*x^8 + ...
MAPLE
a:= n-> (<<0|1|0>, <0|0|1>, <1|-6|5>>^n. <<1, 1, 2>>)[1, 1]:
MATHEMATICA
nn=56; Select[CoefficientList[Series[(1-4x^2+3x^4)/(1-5x^2+6x^4-x^6), {x, 0, nn}], x], #>0 &] (* Geoffrey Critzer, Jan 26 2014 *)
PROG
(PARI) a=vector(99); a[1]=1; a[2]=2; a[3]=5; for(n=4, #a, a[n]=5*a[n-1]-6*a[n-2] +a[n-3]); a \\ Charles R Greathouse IV, Jun 10 2011 (PARI) {a(n) = if( n<0, n = -n; polcoeff( (1 - 3*x + x^2) / (1 - 6*x + 5*x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - 4*x + 3*x^2) / (1 - 5*x + 6*x^2 - x^3) + x * O(x^n), n))} /* Michael Somos, May 04 2012 */ (Magma) I:=[1, 1, 2]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Jan 09 2016
CROSSREFS
Cf. A033191 which essentially provide the same sequence for different limits and tend to A000108.
Random walks (binomial transform of A006054).
(Formerly M3888)
+10
19
1, 5, 19, 66, 221, 728, 2380, 7753, 25213, 81927, 266110, 864201, 2806272, 9112264, 29587889, 96072133, 311945595, 1012883066, 3288813893, 10678716664, 34673583028, 112584429049, 365559363741, 1186963827439, 3854047383798, 12514013318097, 40632746115136
COMMENTS
Number of walks of length 2n+5 in the path graph P_6 from one end to the other one. Example: a(1)=5 because in the path ABCDEF we have ABABCDEF, ABCBCDEF, ABCDCDEF, ABCDEDEF and ABCDEFEF. - Emeric Deutsch, Apr 02 2004 Since a(n) is the binomial transform of A006054 from formula (3.63) in the Witula-Slota-Warzynski paper, it follows that a(n)=A(n;1)*(B(n;-1)-C(n;-1))-B(n;1)*B(n;-1)+C(n;1)*(A(n;-1)-B(n;-1)+C(n;-1)), where A(n;1)= A077998(n), B(n;1)= A006054(n+1), C(n;1)= A006054(n), A(n;-1)= A121449(n), B(n+1;-1)=- A085810(n+1), C(n;-1)= A215404(n) and A(n;d), B(n;d), C(n;d), n in N, d in C, denote the quasi-Fibonacci numbers defined and discussed in comments in A121449 and in the cited paper. - Roman Witula, Aug 09 2012 With offset -4 this sequence 6, 1, 0, 0, 1, 5, ... appears in the formula for the n-th power of the 3 X 3 tridiagonal Matrix M_3 = Matrix([1,1,0], [1,2,1], [0,1,2]) from A332602: (M_3)^n = a(n-2)*(M_3)^2 - (6*a(n-3) - a(n-4))*M_3 + a(n-3)*1_3, with the 3 X 3 unit matrix 1_3, for n >= 0. Proof from Cayley-Hamilton: (M_3)^n = 5*(M_3)^3 - 6*M_3 + 1_3 (see A332602 for the characteristic polynomial Phi(3, x)), and the recurrence (M_3)^n = M_3*(M_3)^(n-1). For (M_3)^n[1,1] = 2*a(n-2) - 5*a(n-3) + a(n-4), for n >= 0, see A080937(n). The formula for a(n) in terms of r = rho(7) = A160389 given below shows that a(n)/a(n-1) converges to rho(7)^2 = A116425 = 3.2469796... for n -> infinity. This is because r - 2/r = 0.692..., and r - 1 - 1/r = 0.137... . (End)
REFERENCES
W. Feller, An Introduction to Probability Theory and its Applications, 3rd ed, Wiley, New York, 1968, p. 96.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
G. Kreweras, Sur les éventails de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #15 (1970), 3-41. [Annotated scanned copy]
FORMULA
a(n) = Sum_{j=-infinity..infinity} (binomial(5+2*k, 7*j+k-2) - binomial(5+2*k, 7*j+k-1)) (a finite sum).
a(n-2) = 2^n*C(n;1/2)=(1/7)*((c(2)-c(4))*(c(4))^(2n) + (c(4)-c(1))*(c(1))^(2n) + (c(1)-c(2))*(c(2))^(2n)), where a(-2)=a(-1):=0, c(j):=2*cos(2Pi*j/7). This formula follows from the Binet formula for C(n;d)--one of the quasi-Fibonacci numbers (see comments in A121449 and the formula (3.17) in the Witula-Slota-Warzynski paper). - Roman Witula, Aug 09 2012 In terms of the algebraic number r = rho(7) = 2*cos(Pi/7) = A160389 of degree 3 the preceding formula gives a(n) = r^(2*(n+2))*(A1(r) + A2(r)*(r - 2/r)^(2*(n+1)) = A3(r)*(r - 1 - 1/r)^(2*(n+1)))/7, for n >= -4 (see a comment above for this offset), with A1(r) = -r^2 + 2*r + 1, A2(r) = -r^2 - r + 2, and A3(r) = 2*r^2 - r - 3. - Wolfdieter Lang, Mar 30 2020
MAPLE
a:=k->sum(binomial(5+2*k, 7*j+k-2), j=ceil((2-k)/7)..floor((7+k)/7))-sum(binomial(5+2*k, 7*j+k-1), j=ceil((1-k)/7)..floor((6+k)/7)): seq(a(k), k=0..25);
A005021:=-(z-1)*(z-5)/(-1+5*z-6*z**2+z**3); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence apart from the initial 1
MATHEMATICA
LinearRecurrence[{5, -6, 1}, {1, 5, 19}, 50] (* Roman Witula, Aug 09 2012 *) CoefficientList[Series[1/(1 - 5 x + 6 x^2 - x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)
PROG
(Magma) I:=[1, 5, 19]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 18 2015 (PARI) x='x+O('x^30); Vec(1/(1-5*x+6*x^2-x^3)) \\ G. C. Greubel, Apr 19 2018
Number of three-choice paths along a corridor of height 5, starting from the lower side.
+10
15
1, 2, 5, 13, 35, 96, 266, 741, 2070, 5791, 16213, 45409, 127206, 356384, 998509, 2797678, 7838801, 21963661, 61540563, 172432468, 483144522, 1353740121, 3793094450, 10628012915, 29779028189, 83438979561, 233790820762, 655067316176, 1835457822857, 5142838522138, 14409913303805
COMMENTS
A three-choice path is a path whose steps lie in the set {(1,1), (1,0), (1,-1)}.
The paths under consideration "live" in a corridor like 0<=y<=5. Thus, the ordinate of a vertex of a path can take six values (0,1,2,3,4,5), but the height of the corridor is five.
a(1)=1 is the number of paths with zero steps, a(2)=2 is the number of paths with one step, a(3)=5 is the number of paths with two steps, ...
(End)
C(n):= a(n)*(-1)^n appears in the following formula for the nonpositive powers of rho*sigma, where rho:=2*cos(Pi/7) and sigma:=sin(3*Pi/7)/sin(Pi/7) = rho^2-1 are the ratios of the smaller and larger diagonal length to the side length in a regular 7-gon (heptagon). See the Steinbach reference where the basis <1,rho,sigma> is used in an extension of the rational field. (rho*sigma)^(-n) = C(n) + B(n)*rho + A(n)*sigma,n>=0, with B(n)= A181880(n-2)*(-1)^n, and A(n)= A116423(n+1)*(-1)^(n+1). For the nonnegative powers see A120757(n), | A122600(n-1)| and A181879(n), respectively. See also a comment under A052547. a(n) is also the number of bi-wall directed polygons with n cells. (The definition of bi-wall directed polygons is given in the article on A122737.)
FORMULA
a(n) = 4*a(n-1) - 3*a(n-2) - a(n-3).
G.f.: (1-2*x)/(1-4*x+3*x^2+x^3).
a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-k} C(n-k, j)*C(j+k, 2k));
a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-k} C(n-k, k+j)*C(k, k-j)*2^(n-2k-j));
a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-2*k} C(n-j, n-2*k-j)*C(k, j)(-1)^j*2^(n-2*k-j)). (End)
a(n-1) = -B(n;-1) = (1/7)*((c(4)-c(1))*(1-c(1))^n + (c(1)-c(2))*(1-c(2))^n + (c(2)-c(4))*(1-c(4))^n), where a(-1):=0, c(j):=2*cos(2*Pi*j/7). Moreover, B(n;d), n in N, d in C, denotes the respective quasi-Fibonacci number defined in comments to A121449 or in Witula-Slota-Warzynski's paper (see also A077998, A006054, A052975, A094789, A121442). - Roman Witula, Aug 09 2012
MATHEMATICA
LinearRecurrence[{4, -3, -1}, {1, 2, 5}, 50] (* Roman Witula, Aug 09 2012 *) CoefficientList[Series[(1 - 2 x)/(1 - 4 x + 3 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)
PROG
(Magma) I:=[1, 2, 5]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2)-Self(n-3): n in [1..35]]; // Vincenzo Librandi, Sep 18 2015 (PARI) x='x+O('x^30); Vec((1-2*x)/(1-4*x+3*x^2+x^3)) \\ G. C. Greubel, Apr 19 2018
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2*n, s(0) = 1, s(2n) = 3.
+10
14
1, 3, 9, 28, 89, 286, 924, 2993, 9707, 31501, 102256, 331981, 1077870, 3499720, 11363361, 36896355, 119801329, 388991876, 1263047761, 4101088878, 13316149700, 43237262993, 140390505643, 455845099957, 1480119728920
COMMENTS
In general a(n) = (2/m)*Sum_{r=1..m-1} sin(r*j*Pi/m)*sin(r*k*Pi/m)*(2*cos(r*Pi/m))^(2n)) counts (s(0), s(1), ..., s(2n)) such that 0 < s(i) < m and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = j, s(2n) = k.
With interpolated zeros (0,0,1,0,3,0,9,...), counts walks of length n between the first and third nodes of P_6. - Paul Barry, Jan 26 2005 Counts all paths of length (2*n+1), n >= 0, starting at the initial node and ending on the nodes 1, 2, 3, 4 and 5 on the path graph P_6, see the Maple program. - Johannes W. Meijer, May 29 2010
FORMULA
a(n) = (2/7)*Sum_{k=1..6} sin(Pi*k/7)*sin(3*Pi*k/7)*(2*cos(Pi*k/7))^(2n).
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3).
G.f.: x*(1-2*x)/(1 - 5*x + 6*x^2 - x^3).
a(n) = rightmost term in M^n * [1,0,0] where M = the 3 X 3 matrix [2,1,1; 1,2,0; 1,0,1]. E.g., M^3 * [1,0,0] = [19,14,9]; right term = 9 = a(3). - Gary W. Adamson, Apr 04 2006
MAPLE
with(GraphTheory):G:=PathGraph(6): A:= AdjacencyMatrix(G): nmax:=24; n2:=2*nmax+1: for n from 0 to n2 do B(n):=A^n; a(n):=add(B(n)[k, 1], k=1..5); od: seq(a(2*n+1), n=0..nmax); # Johannes W. Meijer, May 29 2010
MATHEMATICA
f[n_]:= FullSimplify[ TrigToExp[(2/7)Sum[ Sin[Pi*k/7]Sin[3Pi*k/7](2Cos[Pi*k/7] )^(2n), {k, 6}]]];
LinearRecurrence[{5, -6, 1}, {1, 3, 9}, 30] (* Harvey P. Dale, Nov 19 2019 *)
PROG
(Magma) [n le 3 select 3^(n-1) else 5*Self(n-1) -6*Self(n-2) +Self(n-3): n in [1..31]]; // G. C. Greubel, Feb 12 2023 (SageMath)
@CachedFunction
if (n<4): return 3^(n-1)
else: return 5*a(n-1) - 6*a(n-2) + a(n-3)
Expansion of (1-2*x)*(1-x)/(1-5*x+6*x^2-x^3).
+10
11
1, 2, 6, 19, 61, 197, 638, 2069, 6714, 21794, 70755, 229725, 745889, 2421850, 7863641, 25532994, 82904974, 269190547, 874055885, 2838041117, 9215060822, 29921113293, 97153242650, 315454594314, 1024274628963, 3325798821581, 10798800928441, 35063486341682
COMMENTS
Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 7 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 3, s(2n) = 3. - Herbert Kociemba, Jun 11 2004 Counts all paths of length (2*n), n>=0, starting at the initial node and ending on the nodes 1, 2, 3, 4 and 5 on the path graph P_6, see the second Maple program. - Johannes W. Meijer, May 29 2010
FORMULA
G.f.: (1-2*x)*(1-x)/(1-5*x+6*x^2-x^3).
a(n) = Sum (1/7*(2-3*_alpha+_alpha^2)*_alpha^(-1-n), _alpha=RootOf(-1+5*_Z-6*_Z^2+_Z^3))
a(n) = (2/7)*Sum_{r=1..6} sin(r*3*Pi/7)^2*(2*cos(r*Pi/7))^(2*n).
a(n) = 5*a(n-1) - 6*a(n-2) + a(n-3). (End)
a(n) = 2^n*A(n;1/2) = (1/7)*(s(2)^2*c(4)^(2n) + s(4)^2*c(1)^(2n) + s(1)^2*c(2)^(2n)), where c(j):=2*cos(2Pi*j/7) and s(j):=2*sin(2*Pi*j/7). Here A(n;d), n in N, d in C denotes the respective quasi-Fibonacci number - see A121449 and Witula-Slota-Warzynski paper for details (see also A094789, A085810, A077998, A006054, A121442). I note that my and the respective Herbert Kociemba's formulas are "compatible". - Roman Witula, Aug 09 2012
MAPLE
spec := [S, {S=Sequence(Prod(Union(Sequence(Prod(Sequence(Z), Z)), Sequence(Z)), Z))}, unlabeled ]: seq(combstruct[count ](spec, size=n), n=0..20);
with(GraphTheory):G:=PathGraph(6): A:= AdjacencyMatrix(G): nmax:=25; n2:=2*nmax+1: for n from 0 to n2 do B(n):=A^n; a(n):=add(B(n)[k, 1], k=1..5); od: seq(a(2*n), n=0..nmax); # Johannes W. Meijer, May 29 2010
MATHEMATICA
LinearRecurrence[{5, -6, 1}, {1, 2, 6}, 50] (* Roman Witula, Aug 09 2012 *) CoefficientList[Series[(1 - 2 x) (1 - x)/(1 - 5 x + 6 x^2 - x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)
PROG
(Magma) I:=[1, 2, 6]; [n le 3 select I[n] else 5*Self(n-1)-6*Self(n-2)+Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 18 2015 (PARI) x='x+O('x^30); Vec((1-2*x)*(1-x)/(1-5*x+6*x^2-x^3)) \\ G. C. Greubel, Apr 19 2018
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
Square array T, read by antidiagonals : T(n,k) = 0 if n-k>=3 or if k-n>=4, T(2,0) = T(1,0) = T(0,0) = T(0,1) = T(0,2) = T(0,3) = 1, T(n,k) = T(n-1,k) + T(n,k-1).
+10
10
1, 1, 1, 1, 2, 1, 1, 3, 3, 0, 0, 4, 6, 3, 0, 0, 4, 10, 9, 0, 0, 0, 0, 14, 19, 9, 0, 0, 0, 0, 14, 33, 28, 0, 0, 0, 0, 0, 0, 47, 61, 28, 0, 0, 0, 0, 0, 0, 47, 108, 89, 0, 0, 0, 0, 0, 0, 0, 0, 155, 197, 89, 0, 0, 0, 0
REFERENCES
E. Lucas, Théorie des nombres, Tome 1, Albert Blanchard, Paris, 1958, p.89
FORMULA
T(n+1,n) = T(n+2,n) = A094790(n+1). T(n,n+2) = T(n,n+3) = A094789(n+1). Sum_{k, 0<=k<=n} T(n-k,k) = (-1)^n* A078038(n).
EXAMPLE
Square array begins:
1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... row n = 0
1, 2, 3, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, ... row n = 1
1, 3, 6, 10, 14, 14, 0, 0, 0, 0, 0, 0, 0, ... row n = 2
0, 3, 9, 19, 33, 47, 47, 0, 0, 0, 0, 0, 0, ... row n = 3
0, 0, 9, 28, 61, 108, 155, 155, 0, 0, 0, 0, 0, ... row n = 4
0, 0, 0, 28, 89, 197, 352, 507, 507, 0, 0, 0, 0, ... row n = 5
0, 0, 0, 0, 89, 286, 638,1147,1652,1652, 0, 0, 0, ... row n = 6
...
Expansion of (1-x^2)/(1-x-9*x^2+x^3).
+10
9
1, 1, 9, 17, 97, 241, 1097, 3169, 12801, 40225, 152265, 501489, 1831649, 6192785, 22176137, 76079553, 269472001, 932011841, 3281180297, 11399814865, 39998425697, 139315579185, 487901595593, 1701743382561, 5953542163713, 20781331011169, 72661467102025
COMMENTS
We have a(n)=A(n;2), where A(n;2), B(n;2) and C(n;2) are the special cases of so-called quasi-Fibonacci numbers A(n;d), B(n;d), and C(n;d) for the value of argument d=2 - for details see Witula's comments to A121449 or the paper of Witula-Slota-Warzynski's. The sequences A(n;2), B(n;2) and C(n;2) are defined by the following system of recurrence equations: A(0;2)=1, B(0;2)=C(0;2)=0,
A(n+1;2)=A(n;2)+4*B(n;2)-2*C(n;2), B(n+1;2)=2*A(n;2)+B(n;2), and C(n+1;2)=2*B(n;2)-C(n;2).
We note that A(n;1)= A077998(n), B(n;1)= A006054(n+1), and C(n;1)= A006054(n). We know (see formulas (3.61-63) in Witula et al.'s paper) that the sequences: (-2)^(-n)*(A(n;1)*(A(n;2)-C(n;2))-B(n;1)*(B(n;2)+C(n;2))+C(n;1)*B(n;2)), (-2)^(-n)*(-A(n;1)*C(n;2)+B(n;1)*(A(n;2)-C(n;2))-C(n;1)*(B(n;2)-C(n;2))), and (-2)^(-n)*(A(n;1)*(B(n;2)-C(n;2))-B(n;1)*B(n;2)+C(n;1)*(A(n;2)-B(n;2)+C(n;2))) are the binomial transforms of the sequences (-2)^(-n)*A(n;1), (-2)^(-n)*B(n;1), and (-2)^(-n)*C(n;1) respectively. Moreover the elements of the sequences A(n;1/2)=2^(-n)* A052975, B(n;1/2)=2^(-n)* A094789, and C(n;1/2) could be described by certain convolutions type identities for the elements of A(n;2), B(n;2), and C(n;2) (see identities (3.58-60) in Witula et al.'s paper). (End)
FORMULA
a(0)=a(1)=1, a(2)=9, a(n+1) = a(n)+9*a(n-1)-a(n-2) for n>=2.
7*a(n) = (2-c(4))*(1-2*c(1))^n + (2-c(1))*(1-2*c(2))^n + (2-c(2))*(1-2*c(4))^n = (s(2))^2*(1-2*c(1))^n + (s(4))^2*(1-2*c(2))^n + (s(1))^2*(1-2*c(4))^n, where c(j):=2*Cos(2Pi*j/7) and s(j):=2*Sin(2Pi*j/7) - it is the special case, for d=2, of the Binet's formula for the respective quasi-Fibonacci number A(n;d) discussed in Witula-Slota-Warzynski's paper (see also A121449). - Roman Witula, Aug 08 2012
MATHEMATICA
LinearRecurrence[{1, 9, -1}, {1, 1, 9}, 50] (* Roman Witula, Aug 08 2012 *)
CoefficientList[Series[(1 - x^2)/(1 - x - 9 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)
PROG
(Magma) I:=[1, 1, 9]; [n le 3 select I[n] else Self(n-1)+9*Self(n-2)-Self(n-3): n in [1..30]]; // Vincenzo Librandi, Sep 18 2015
a(n) = 4*a(n-1) - 3*a(n-2) - a(n-3), with a(0)=0, a(1)=0 and a(2)=1.
+10
6
0, 0, 1, 4, 13, 39, 113, 322, 910, 2561, 7192, 20175, 56563, 158535, 444276, 1244936, 3488381, 9774440, 27387681, 76739023, 215018609, 602469686, 1688083894, 4729907909, 13252910268, 37133833451, 104046695091, 291532369743, 816855560248, 2288778436672, 6413014696201
COMMENTS
We have a(n)=C(n;-1), A121449(n)=A(n;-1), A085810(n+1)=-B(n+1;-1), where A(n;d), B(n;d), and C(n;d), n in N, d in C, are so-called quasi-Fibonacci numbers defined and discussed in the comments to A121449 and in Witula-Slota-Warzynski's paper. It follows from formulas (3.47-49) in this paper that the value of A(n;1/3), B(n;1/3) and C(n;1/3) could be obtained from special convolution type identities for sequences a(n), A121449, and A085810.
LINKS
Ilya Amburg, Krishna Dasaratha, Laure Flapan, Thomas Garrity, Chansoo Lee, Cornelia Mihaila, Nicholas Neumann-Chun, Sarah Peluse, and Matthew Stoffregen, Stern Sequences for a Family of Multidimensional Continued Fractions: TRIP-Stern Sequences, arXiv:1509.05239 [math.CO], 2015.
FORMULA
G.f.: x^2/(1-4*x+3*x^2+x^3).
a(n) = (1/7)*((c(2)-c(4))*(1-c(1))^n + (c(4)-c(1))*(1-c(2))^n + (c(1)-c(2))*(1-c(4))^n), where c(j):=2*cos(2*Pi*j/7) - this formula is the Binet formula for a(n) (see the Binet formula (3.17) for the respective quasi-Fibonacci number C(n;d) for value d=-1 in the Witula-Slota-Warzynski paper).
MATHEMATICA
LinearRecurrence[{4, -3, -1}, {0, 0, 1}, 50]
CoefficientList[Series[x^2/(1 - 4 x + 3 x^2 + x^3), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 18 2015 *)
PROG
(Magma) I:=[0, 0, 1]; [n le 3 select I[n] else 4*Self(n-1)-3*Self(n-2)-Self(n-3): n in [1..35]]; // Vincenzo Librandi, Sep 18 2015
Square array T, read by antidiagonals: T(n,k) = 0 if n-k >= 1 or if k-n >= 6, T(0,0) = T(0,1) = T(0,2) = T(0,3) = T(0,4) = T(0,5) = 1, T(n,k) = T(n-1,k) + T(n,k-1).
+10
4
1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 5, 0, 0, 0, 0, 5, 9, 5, 0, 0, 0, 0, 5, 14, 14, 0, 0, 0, 0, 0, 0, 19, 28, 14, 0, 0, 0, 0, 0, 0, 19, 47, 42, 0, 0, 0, 0, 0, 0, 0, 0, 66, 89, 42, 0, 0, 0, 0, 0, 0, 0, 0, 66, 155, 131, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 221, 286, 131, 0, 0
COMMENTS
A hexagon arithmetic of E. Lucas.
REFERENCES
E. Lucas, Théorie des nombres, A.Blanchard, Paris, 1958, Tome 1, p.89
FORMULA
Sum_{k, 0<=k<=n} T(n-k,k) = A028495(n).
EXAMPLE
Square array begins:
1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... row n=0
0, 1, 2, 3, 4, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, ... row n=1
0, 0, 2, 5, 9, 14, 19, 19, 0, 0, 0, 0, 0, 0, 0, ... row n=2
0, 0, 0, 5, 14, 28, 47, 66, 66, 0, 0, 0, 0, 0, 0, ... row n=3
0, 0, 0, 0, 14, 42, 89, 155, 221, 221, 0, 0, 0, 0, ... row n=4
0, 0, 0, 0, 0, 0, 42, 131, 286, 507, 728, 728, 0, 0, ... row n=5
0, 0, 0, 0, 0, 0, 131, 417, 924, 1652, 2380, 2380, 0, ... row n=6
...
MATHEMATICA
Clear[t]; t[0, k_ /; k <= 5] = 1; t[n_, k_] /; k < n || k > n+5 = 0; t[n_, k_] := t[n, k] = t[n-1, k] + t[n, k-1]; Table[t[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Mar 18 2013 *)
Search completed in 0.022 seconds
| 