| Displaying 1-9 of 9 results found.
page
1
Third column (m=2) of triangle A060920 (bisection of Fibonacci triangle, even part).
+20
2
1, 9, 51, 233, 942, 3522, 12473, 42447, 140109, 451441, 1426380, 4434420, 13599505, 41225349, 123723351, 368080793, 1086665562, 3186317718, 9286256393, 26916587307, 77634928209, 222920650081
COMMENTS
Numerator polynomial of g.f. is sum( A061176(3,m)*x^m,m=0..3).
FORMULA
G.f.: (1-x^3)/(1-3*x+x^2)^3.
Fourth column (m=3) of triangle A060920 (bisection of Fibonacci triangle, even part).
+20
2
1, 14, 105, 594, 2860, 12402, 49963, 190570, 696787, 2463300, 8472280, 28481220, 93914325, 304597382, 973877245, 3075011478, 9602753412, 29695165110, 91026167999, 276833858530, 835933445799, 2507876305416
COMMENTS
Numerator polynomial of g.f. is sum( A061176(4,m)*x^m,m=0..4).
FORMULA
G.f.: (1+2*x-5*x^2+2*x^3+x^4)/(1-3*x+x^2)^4.
Fifth column (m=4) of triangle A060920 (bisection of Fibonacci triangle, even part).
+20
2
1, 20, 190, 1295, 7285, 36122, 163730, 693835, 2790100, 10758050, 40075630, 145052300, 512347975, 1772132390, 6018885570, 20118711993, 66306068715, 215797999830, 694463680160, 2212291834405, 6982976069384
COMMENTS
Numerator polynomial of g.f. is sum( A061176(5,m)*x^m, m=0..5).
LINKS
Index entries for linear recurrences with constant coefficients, signature (15, -95, 330, -685, 873, -685, 330, -95, 15, -1).
FORMULA
G.f.: ((1-x^5)+5*(x-x^4)-15*(x^2-x^3))/(1-3*x+x^2)^5.
MATHEMATICA
CoefficientList[Series[((1-x^5)+5(x-x^4)-15(x^2-x^3))/(1-3x+x^2)^5, {x, 0, 40}], x] (* or *) LinearRecurrence[{15, -95, 330, -685, 873, -685, 330, -95, 15, -1}, {1, 20, 190, 1295, 7285, 36122, 163730, 693835, 2790100, 10758050}, 30] (* Harvey P. Dale, Sep 01 2022 *)
Sixth column (m=5) of triangle A060920 (bisection of Fibonacci triangle, even part).
+20
1
1, 27, 315, 2534, 16407, 91959, 464723, 2171850, 9546570, 39940460, 160437690, 622844730, 2348773525, 8638447293, 31086197469, 109744786482, 380920122009, 1302304276665, 4392297900647
COMMENTS
Numerator polynomial of g.f. is sum( A061176(6,m)*x^m,m=0..6).
FORMULA
G.f.: ((1+x^6)+9*(x+x^5)-30*(x^2+x^4)+41*x^3)/(1-3*x+x^2)^6.
a(n) = 3*a(n-1) - a(n-2) for n >= 2, with a(0) = a(1) = 1.
(Formerly M1439 N0569)
+10
350
1, 1, 2, 5, 13, 34, 89, 233, 610, 1597, 4181, 10946, 28657, 75025, 196418, 514229, 1346269, 3524578, 9227465, 24157817, 63245986, 165580141, 433494437, 1134903170, 2971215073, 7778742049, 20365011074, 53316291173, 139583862445, 365435296162, 956722026041
COMMENTS
This is a bisection of the Fibonacci sequence A000045. a(n) = F(2*n-1), with F(n) = A000045(n) and F(-1) = 1. Number of ordered trees with n+1 edges and height at most 3 (height=number of edges on a maximal path starting at the root). Number of directed column-convex polyominoes of area n+1. Number of nondecreasing Dyck paths of length 2n+2. - Emeric Deutsch, Jul 11 2001 a(0) = a(1) = 1, a(n+1) is the smallest Fibonacci number greater than the n-th partial sum. - Amarnath Murthy, Oct 21 2002 The fractional part of tau*a(n) decreases monotonically to zero. - Benoit Cloitre, Feb 01 2003 Numbers k such that floor(phi^2*k^2) - floor(phi*k)^2 = 1 where phi=(1+sqrt(5))/2. - Benoit Cloitre, Mar 16 2003 Number of leftist horizontally convex polyominoes with area n+1.
Number of 31-avoiding words of length n on alphabet {1,2,3} which do not end in 3. (E.g., at n=3, we have 111, 112, 121, 122, 132, 211, 212, 221, 222, 232, 321, 322 and 332.) See A028859. - Jon Perry, Aug 04 2003 Appears to give all solutions > 1 to the equation: x^2 = ceiling(x*r*floor(x/r)) where r=phi=(1+sqrt(5))/2. - Benoit Cloitre, Feb 24 2004 a(1) = 1, a(2) = 2, then the least number such that the square of any term is just less than the geometric mean of its neighbors. a(n+1)*a(n-1) > a(n)^2. - Amarnath Murthy, Apr 06 2004 All positive integer solutions of Pell equation b(n)^2 - 5*a(n+1)^2 = -4 together with b(n)= A002878(n), n >= 0. - Wolfdieter Lang, Aug 31 2004 Essentially same as Pisot sequence E(2,5).
Number of permutations of [n+1] avoiding 321 and 3412. E.g., a(3) = 13 because the permutations of [4] avoiding 321 and 3412 are 1234, 2134, 1324, 1243, 3124, 2314, 2143, 1423, 1342, 4123, 3142, 2413, 2341. - Bridget Tenner, Aug 15 2005 Number of 1324-avoiding circular permutations on [n+1].
(x,y) = (a(n), a(n+1)) are the solutions of x/(yz) + y/(xz) + z/(xy) = 3 with z=1. - Floor van Lamoen, Nov 29 2001 Number of (s(0), s(1), ..., s(2n)) such that 0 < s(i) < 5 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n, s(0) = 1, s(2n) = 1. - Herbert Kociemba, Jun 10 2004 With interpolated zeros, counts closed walks of length n at the start or end node of P_4. a(n) counts closed walks of length 2n at the start or end node of P_4. The sequence 0,1,0,2,0,5,... counts walks of length n between the start and second node of P_4. - Paul Barry, Jan 26 2005 a(n) is the number of ordered trees on n edges containing exactly one non-leaf vertex all of whose children are leaves (every ordered tree must contain at least one such vertex). For example, a(0) = 1 because the root of the tree with no edges is not considered to be a leaf and the condition "all children are leaves" is vacuously satisfied by the root and a(4) = 13 counts all 14 ordered trees on 4 edges ( A000108) except (ignore dots) |..|
.\/.
Number of directed column-convex polyominoes of area n. Example: a(2)=2 because we have the 1 X 2 and the 2 X 1 rectangles. - Emeric Deutsch, Jul 31 2006 Same as the number of Kekulé structures in polyphenanthrene in terms of the number of hexagons in extended (1,1)-nanotubes. See Table 1 on page 411 of I. Lukovits and D. Janezic. - Parthasarathy Nambi, Aug 22 2006 Number of free generators of degree n of symmetric polynomials in 3-noncommuting variables. - Mike Zabrocki, Oct 24 2006 Inverse: With phi = (sqrt(5) + 1)/2, log_phi((sqrt(5)*a(n) + sqrt(5*a(n)^2 - 4))/2) = n for n >= 1. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
Consider a teacher who teaches one student, then he finds he can teach two students while the original student learns to teach a student. And so on with every generation an individual can teach one more student then he could before. a(n) starting at a(2) gives the total number of new students/teachers (see program). - Ben Paul Thurston, Apr 11 2007 The Diophantine equation a(n)=m has a solution (for m >= 1) iff ceiling(arcsinh(sqrt(5)*m/2)/log(phi)) != ceiling(arccosh(sqrt(5)*m/2)/log(phi)) where phi is the golden ratio. An equivalent condition is A130255(m)= A130256(m). - Hieronymus Fischer, May 24 2007 a(n+1) = B^(n)(1), n >= 0, with compositions of Wythoff's complementary A(n):= A000201(n) and B(n)= A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 2=`0`, 5=`00`, 13=`000`, ..., in Wythoff code. Bisection of the Fibonacci sequence into odd-indexed nonzero terms (1, 2, 5, 13, ...) and even-indexed terms (1, 3, 8, 21, ...) may be represented as row sums of companion triangles A140068 and A140069. - Gary W. Adamson, May 04 2008 a(n) is the number of partitions pi of [n] (in standard increasing form) such that Flatten[pi] is a (2-1-3)-avoiding permutation. Example: a(4)=13 counts all 15 partitions of [4] except 13/24 and 13/2/4. Here "standard increasing form" means the entries are increasing in each block and the blocks are arranged in increasing order of their first entries. Also number that avoid 3-1-2. - David Callan, Jul 22 2008 Let P be the partial sum operator, A000012: (1; 1,1; 1,1,1; ...) and A153463 = M, the partial sum & shift operator. It appears that beginning with any randomly taken sequence S(n), iterates of the operations M * S(n), -> M * ANS, -> P * ANS, etc. (or starting with P) will rapidly converge upon a two-sequence limit cycle of (1, 2, 5, 13, 34, ...) and (1, 1, 3, 8, 21, ...). - Gary W. Adamson, Dec 27 2008 Number of musical compositions of Rhythm-music over a time period of n-1 units. Example: a(4)=13; indeed, denoting by R a rest over a time period of 1 unit and by N[j] a note over a period of j units, we have (writing N for N[1]): NNN, NNR, NRN, RNN, NRR, RNR, RRN, RRR, N[2]R, RN[2], NN[2], N[2]N, N[3] (see the J. Groh reference, pp. 43-48). - Juergen K. Groh (juergen.groh(AT)lhsystems.com), Jan 17 2010
Given an infinite lower triangular matrix M with (1, 2, 3, ...) in every column but the leftmost column shifted upwards one row. Then (1, 2, 5, ...) = lim_{n->infinity} M^n. (Cf. A144257.) - Gary W. Adamson, Feb 18 2010 As a fraction: 8/71 = 0.112676 or 98/9701 = 0.010102051334... (fraction 9/71 or 99/9701 for sequence without initial term). 19/71 or 199/9701 for sequence in reverse. - Mark Dols, May 18 2010 For n >= 1, a(n) is the number of compositions (ordered integer partitions) of 2n-1 into an odd number of odd parts. O.g.f.: (x-x^3)/(1-3x^2+x^4) = A(A(x)) where A(x) = 1/(1-x)-1/(1-x^2).
For n > 0, determinant of the n X n tridiagonal matrix with 1's in the super and subdiagonals, (1,3,3,3,...) in the main diagonal, and the rest zeros. - Gary W. Adamson, Jun 27 2011 The number of permutations for which length equals reflection length. - Bridget Tenner, Feb 22 2012 Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n+1, with exactly 2 elements of each rank between 0 and 1. (Uniform used in the sense of Retakh, Serconek and Wilson. Graded used in R. Stanley's sense that all maximal chains have the same length.)
HANKEL transform of sequence and the sequence omitting a(0) is the sequence A019590(n). This is the unique sequence with that property. - Michael Somos, May 03 2012 The number of Dyck paths of length 2n and height at most 3. - Ira M. Gessel, Aug 06 2012 Pisano period lengths: 1, 3, 4, 3, 10, 12, 8, 6, 12, 30, 5, 12, 14, 24, 20, 12, 18, 12, 9, 30, ... - R. J. Mathar, Aug 10 2012 Primes in the sequence are 2, 5, 13, 89, 233, 1597, 28657, ... (apparently A005478 without the 3). - R. J. Mathar, May 09 2013 a(n+1) is the sum of rising diagonal of the Pascal triangle written as a square - cf. comments in A085812. E.g., 13 = 1+5+6+1. - John Molokach, Sep 26 2013 a(n) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 1, 1, 1; 0, 1, 1] or [1, 1, 1; 0, 1, 1; 1, 1, 1] or [1, 1, 0; 1, 1, 1; 1, 1, 1] or [1, 0, 1; 1, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014 Except for the initial term, positive values of x (or y) satisfying x^2 - 3xy + y^2 + 1 = 0. - Colin Barker, Feb 04 2014 Except for the initial term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 64 = 0. - Colin Barker, Feb 16 2014 Positive values of x such that there is a y satisfying x^2 - xy - y^2 - 1 = 0. - Ralf Stephan, Jun 30 2014 a(n) is also the number of permutations simultaneously avoiding 231, 312 and 321 in the classical sense which can be realized as labels on an increasing strict binary tree with 2n-1 nodes. See A245904 for more information on increasing strict binary trees. - Manda Riehl, Aug 07 2014 (1, a(n), a(n+1)), n >= 0, are Markoff triples (see A002559 and Robert G. Wilson v's Oct 05 2005 comment). In the Markoff tree they give one of the outer branches. Proof: a(n)*a(n+1) - 1 = A001906(2*n)^2 = (a(n+1) - a(n))^2 = a(n)^2 + a(n+1)^2 - 2*a(n)*a(n+1), thus 1^2 + a(n)^2 + a(n+1)^2 = 3*a(n)*a(n+1). - Wolfdieter Lang, Jan 30 2015 For n > 0, a(n) is the smallest positive integer not already in the sequence such that a(1) + a(2) + ... + a(n) is a Fibonacci number. - Derek Orr, Jun 01 2015 Number of vertices of degree n-2 (n >= 3) in all Fibonacci cubes, see Klavzar, Mollard, & Petkovsek. - Emeric Deutsch, Jun 22 2015 Except for the first term, this sequence can be generated by Corollary 1 (ii) of Azarian's paper in the references for this sequence. - Mohammad K. Azarian, Jul 02 2015 Precisely the numbers F(n)^k + F(n+1)^k that are also Fibonacci numbers with k > 1, see Luca & Oyono. - Charles R Greathouse IV, Aug 06 2015 a(n) = MA(n) - 2*(-1)^n where MA(n) is exactly the maximum area of a quadrilateral with lengths of sides in order L(n-2), L(n-2), F(n+1), F(n+1) for n > 1 and L(n)= A000032(n). - J. M. Bergot, Jan 28 2016 a(n) is the number of bargraphs of semiperimeter n+1 having no valleys (i.e., convex bargraphs). Equivalently, number of bargraphs of semiperimeter n+1 having exactly 1 peak. Example: a(5) = 34 because among the 35 (= A082582(6)) bargraphs of semiperimeter 6 only the one corresponding to the composition [2,1,2] has a valley. - Emeric Deutsch, Aug 12 2016 Integers k such that the fractional part of k*phi is less than 1/k. See Byszewski link p. 2. - Michel Marcus, Dec 10 2016 Number of words of length n-1 over {0,1,2,3} in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017 With a(0) = 0 this is the Riordan transform with the Riordan matrix A097805 (of the associated type) of the Fibonacci sequence A000045. See a Feb 17 2017 comment on A097805. - Wolfdieter Lang, Feb 17 2017 Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) < e(k). [Martinez and Savage, 2.12] - Eric M. Schmidt, Jul 17 2017 Number of permutations of [n] that avoid the patterns 321 and 2341. - Colin Defant, May 11 2018 The sequence solves the following problem: find all the pairs (i,j) such that i divides 1+j^2 and j divides 1+i^2. In fact, the pairs (a(n), a(n+1)), n > 0, are all the solutions. - Tomohiro Yamada, Dec 23 2018 Number of permutations in S_n whose principal order ideals in the Bruhat order are lattices (equivalently, modular, distributive, Boolean lattices). - Bridget Tenner, Jan 16 2020 a(n) is the upper left entry of the n-th power of the 2 X 2 tridiagonal matrix M_2 = Matrix([1,1], [1,2]) from A322602: a(n) = ((M_2)^n)[1,1]. Proof: (M_2)^2 = 3*M + 1_2 (with the 2 X 2 unit matrix 1_2) from the characteristic polynomial of M_2 (see a comment in A322602) and the Cayley-Hamilton theorem. The recurrence M^n = M*M^(n-1) leads to (M_n)^n = S(n, 3)*1_2 + S(n-a, 3)*(M - 3*1_2), for n >= 0, with S(n, 3) = F(2(n+1)) = A001906(n+1). Hence ((M_2)^n)[1,1] = S(n, 3) - 2*S(n-1, 3) = a(n) = F(2*n-1) = (1/(2*r+1))*r^(2*n-1)*(1 + (1/r^2)^(2*n-1)), with r = rho(5) = A001622 (golden ratio) (see the first Aug 31 2004 formula, using the recurrence of S(n, 3), and the Michael Somos Oct 28 2002 formula). This proves a conjecture of Gary W. Adamson in A322602. The ratio a(n)/a(n-1) converges to r^2 = rho(5)^2 = A104457 for n -> infinity (see the a(n) formula in terms of r), which is one of the statements by Gary W. Adamson in A322602. (End) a(n) is the number of ways to stack coins with a bottom row of n coins such that any coin not on the bottom row touches exactly two coins in the row below, and all the coins on any row are contiguous [Wilf, 2.12]. - Greg Dresden, Jun 29 2020 a(n) is the upper left entry of the (2*n)-th power of the 4 X 4 Jacobi matrix L with L(i,j)=1 if |i-j| = 1 and L(i,j)=0 otherwise. - Michael Shmoish, Aug 29 2020 All positive solutions of the indefinite binary quadratic F(1, -3, 1) := x^2 - 3*x*y + y^2, of discriminant 5, representing -1 (special Markov triples (1, y=x, z=y) if y <= z) are [x(n), y(n)] = [abs(F(2*n+1)), abs(F(2*n-1))], for n = -infinity..+infinity. (F(-n) = (-1)^(n+1)*F(n)). There is only this single family of proper solutions, and there are no improper solutions. [See also the Floor van Lamoen Nov 29 2001 comment, which uses this negative n, and my Jan 30 2015 comment.] - Wolfdieter Lang, Sep 23 2020 These are the denominators of the lower convergents to the golden ratio, tau; they are also the numerators of the upper convergents (viz. 1/1 < 3/2 < 8/5 < 21/13 < ... < tau < ... 13/8 < 5/3 < 2/1). - Clark Kimberling, Jan 02 2022 a(n+1) is the number of subgraphs of the path graph on n vertices. - Leen Droogendijk, Jun 17 2023 For n > 4, a(n+2) is the number of ways to tile this 3 x n "double-box" shape with squares and dominos (reflections or rotations are counted as distinct tilings). The double-box shape is made up of two horizontal strips of length n, connected by three vertical columns of length 3, and the center column can be located anywhere not touching the two outside columns.
_ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_ _ _ _|_|_ _ _ _ _ _ _|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|. - Greg Dresden and Ruishan Wu, Aug 25 2024 a(n+1) is the number of integer sequences a_1, ..., a_n such that for any number 1 <= k <= n, (a_1 + ... + a_k)^2 = a_1^3 + ... + a_k^3. - Yifan Xie, Dec 07 2024
REFERENCES
R. C. Alperin, A family of nonlinear recurrences and their linear solutions, Fib. Q., 57:4 (2019), 318-321.
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 13,15.
N. G. de Bruijn, D. E. Knuth, and S. O. Rice, The average height of planted plane trees, in: Graph Theory and Computing (ed. T. C. Read), Academic Press, New York, 1972, pp. 15-22.
GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 92.
Jurgen Groh, Computerimprovisation mit Markoffketten und "kognitiven Algorithmen", Studienarbeit, Technische Hochschule Darmstadt, 1987.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 39.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. Stanley, Enumerative combinatorics, Vol. 1. Cambridge University Press, Cambridge, 1997, pp. 96-100.
H. S. Wilf, Generatingfunctionology, 3rd ed., A K Peters Ltd., Wellesley, MA, 2006, p. 41.
LINKS
A. Blecher, C. Brennan, and A. Knopfmacher, Peaks in bargraphs, Trans. Royal Soc. South Africa, 71, No. 1, 2016, 97-103. T. Boothby, J. Burkert, M. Eichwald, D. C. Ernst, R. M. Green, and M. Macauley, On the cyclically fully commutative elements of Coxeter groups, J. Algebr. Comb. 36, No. 1, 123-148 (2012), Table 1 CFC A,B,F. A. Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding Part 1 Part 2, Fib. Quart., 9 (1971), 277-295, 298.
FORMULA
G.f.: (1-2*x)/(1-3*x+x^2).
G.f.: 1 / (1 - x / (1 - x / (1 - x))). - Michael Somos, May 03 2012 a(n) = a(1-n) for all n in Z.
a(n+2) = (a(n+1)^2+1)/a(n) with a(1)=1, a(2)=2. - Benoit Cloitre, Aug 29 2002 a(n) = (phi^(2*n-1) + phi^(1-2*n))/sqrt(5) where phi=(1+sqrt(5))/2. - Michael Somos, Oct 28 2002 a(n) = Sum_{k=0..n} binomial(n+k, 2*k). - Len Smiley, Dec 09 2001 a(n) ~ (1/5)*sqrt(5)*phi^(2*n+1). - Joe Keane (jgk(AT)jgk.org), May 15 2002
Let q(n, x) = Sum_{i=0..n} x^(n-i)*binomial(2*n-i, i); then q(n, 1)=a(n) (this comment is essentially the same as that of L. Smiley). - Benoit Cloitre, Nov 10 2002 a(n) = (1/2)*(3*a(n-1) + sqrt(5*a(n-1)^2-4)). - Benoit Cloitre, Apr 12 2003 Main diagonal of array defined by T(i, 1) = T(1, j) = 1, T(i, j) = max(T(i-1, j) + T(i-1, j-1); T(i-1, j-1) + T(i, j-1)). - Benoit Cloitre, Aug 05 2003 Solutions x > 0 to equation floor(x*r*floor(x/r)) = floor(x/r*floor(x*r)) when r=phi. - Benoit Cloitre, Feb 15 2004 a(n) = Sum_{i=0..n} binomial(n+i, n-i). - Jon Perry, Mar 08 2004 a(n) = S(n-1, 3) - S(n-2, 3) = T(2*n-1, sqrt(5)/2)/(sqrt(5)/2) with S(n, x) = U(n, x/2), resp. T(n, x), Chebyshev's polynomials of the second, resp. first kind. See triangle A049310, resp. A053120. - Wolfdieter Lang, Aug 31 2004 a(n) = ((-1)^(n-1))*S(2*(n-1), i), with the imaginary unit i and S(n, x) = U(n, x/2) Chebyshev's polynomials of the second kind, A049310. - Wolfdieter Lang, Aug 31 2004 a(n) = Sum_{0<=i_1<=i_2<=n} binomial(i_2, i_1)*binomial(n, i_1+i_2). - Benoit Cloitre, Oct 14 2004 a(n) = a(n-1) + Sum_{i=0..n-1} a(i)*a(n) = F(2*n+1)*Sum_{i=0..n-1} a(i) = F(2*n). - Andras Erszegi (erszegi.andras(AT)chello.hu), Jun 28 2005
The i-th term of the sequence is the entry (1, 1) of the i-th power of the 2 X 2 matrix M = ((1, 1), (1, 2)). - Simone Severini, Oct 15 2005 a(n-1) = (1/n)*Sum_{k=0..n} B(2*k)*F(2*n-2*k)*binomial(2*n, 2*k) where B(2*k) is the (2*k)-th Bernoulli number. - Benoit Cloitre, Nov 02 2005 a(n) = (2/sqrt(5))*cosh((2n-1)*psi), where psi=log(phi) and phi=(1+sqrt(5))/2. - Hieronymus Fischer, Apr 24 2007 a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3); a(n) = ((sqrt(5) + 5)/10)*(3/2 + sqrt(5)/2)^(n-2) + ((-sqrt(5) + 5)/10)*(3/2 - sqrt(5)/2)^(n-2). - Antonio Alberto Olivares, Mar 21 2008 With X,Y defined as X = ( F(n) F(n+1) ), Y = ( F(n+2) F(n+3) ), where F(n) is the n-th Fibonacci number ( A000045), it follows a(n+2) = X.Y', where Y' is the transpose of Y (n >= 0). - K.V.Iyer, Apr 24 2009 a(n) = Fibonacci(2*n+2) mod Fibonacci(2*n), n > 1.
a(n) = (Fibonacci(n-1)^2 + Fibonacci(n)^2 + Fibonacci(2*n-1))/2. (End)
a(n) = 2^n*f(n;1/2), where f(n;d), n=0,1,...,d, denote the so-called delta-Fibonacci numbers (see Witula et al. papers and comments in A000045). - Roman Witula, Jul 12 2012 a(n) = (Fibonacci(n+2)^2 + Fibonacci(n-3)^2)/5. - Gary Detlefs, Dec 14 2012 G.f.: 1 + x/( Q(0) - x ) where Q(k) = 1 - x/(x*k + 1 )/Q(k+1); (recursively defined continued fraction). - Sergei N. Gladkovskii, Feb 23 2013 G.f.: (1-2*x)*G(0)/(2-3*x), where G(k) = 1 + 1/( 1 - x*(5*k-9)/(x*(5*k-4) - 6/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 19 2013 G.f.: 1 + x*(1-x^2)*Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+2 + 2*x - x^2)/( x*(4*k+4 + 2*x - x^2 ) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 11 2013 G.f.: Q(0,u), where u=x/(1-x), Q(k,u) = 1 + u^2 + (k+2)*u - u*(k+1 + u)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013 Let F(n) be the n-th Fibonacci number, A000045(n), and L(n) be the n-th Lucas number, A000032(n). Then for n > 0, a(n) = F(n)*L(n-1) + (-1)^n. - Charlie Marion, Jan 01 2014 1 = a(n)*a(n+2) - a(n+1)*a(n+1) for all n in Z. - Michael Somos, Jul 08 2014 a(n) = 3*F(n-1)^2 + F(n-3)*F(n) - 2*(-1)^n. - J. M. Bergot, Feb 17 2016 E.g.f.: (2*exp(sqrt(5)*x) + 3 + sqrt(5))*exp(-x*(sqrt(5)-3)/2)/(5 + sqrt(5)). - Ilya Gutkovskiy, Jul 04 2016 a(n) = ((M_2)^n)[1,1] = S(n, 3) - 2*S(n-1, 3), with the 2 X 2 tridiagonal matrix M_2 = Matrix([1,1], [1,2]) from A322602. For a proof see the Mar 30 2020 comment above. - Wolfdieter Lang, Mar 30 2020 a(n+1) = Product_{k=1..n} (1 + 4*cos(2*Pi*k/(2*n + 1))^2). Special case of A099390. - Greg Dresden, Oct 16 2021 a(n+1) = 4^(n+1)*Sum_{k >= n} binomial(2*k,2*n)*(1/5)^(k+1). Cf. A102591. - Peter Bala, Nov 29 2021 a(n) = cosh((2*n-1)*arcsinh(1/2))/sqrt(5/4). - Peter Luschny, May 21 2022 a(n) = F(n-1)*L(n) - (-1)^n where L(n)= A000032(n) and F(n)= A000045(n). a(n) = (L(n-1)^2 + L(n-1)*L(n+1))/5 + (-1)^n.
a(n) = 2*(area of a triangle with vertices at (L(n-2), L(n-1)), (F(n), F(n-1)), (L(n), L(n+1))) + 5*(-1)^n for n > 2. (End)
EXAMPLE
a(3) = 13: there are 14 ordered trees with 4 edges; all of them, except for the path with 4 edges, have height at most 3.
MAPLE
A001519:=-(-1+z)/(1-3*z+z**2); # Simon Plouffe in his 1992 dissertation; gives sequence without an initial 1
A001519 := proc(n) option remember: if n=0 then 1 elif n=1 then 1 elif n>=2 then 3*procname(n-1)-procname(n-2) fi: end: seq( A001519(n), n=0..28); # Johannes W. Meijer, Aug 14 2011
MATHEMATICA
a[ n_] := With[{c = Sqrt[5]/2}, ChebyshevT[2 n - 1, c]/c]; (* Michael Somos, Jul 08 2014 *) CoefficientList[ Series[(1 - 2x)/(1 - 3x + x^2), {x, 0, 30}], x] (* Robert G. Wilson v, Feb 01 2015 *)
PROG
(PARI) {a(n) = fibonacci(2*n - 1)}; /* Michael Somos, Jul 19 2003 */ (PARI) {a(n) = real( quadgen(5) ^ (2*n))}; /* Michael Somos, Jul 19 2003 */ (PARI) {a(n) = subst( poltchebi(n) + poltchebi(n - 1), x, 3/2) * 2/5}; /* Michael Somos, Jul 19 2003 */ (Sage) [lucas_number1(n, 3, 1)-lucas_number1(n-1, 3, 1) for n in range(30)] # Zerinvary Lajos, Apr 29 2009 (Haskell)
a001519 n = a001519_list !! n
a001519_list = 1 : zipWith (-) (tail a001906_list) a001906_list
a001519_list = 1 : f a000045_list where f (_:x:xs) = x : f xs
(Maxima) a[0]:1$ a[1]:1$ a[n]:=3*a[n-1]-a[n-2]$ makelist(a[n], n, 0, 30); /* Martin Ettl, Nov 15 2012 */ (Magma) [1] cat [(Lucas(2*n) - Fibonacci(2*n))/2: n in [1..50]]; // Vincenzo Librandi, Jul 02 2014 (GAP)
a:=[1, 1];; for n in [3..10^2] do a[n]:=3*a[n-1]-a[n-2]; od; a; # Muniru A Asiru, Sep 27 2017
CROSSREFS
Cf. A001653, A055105, A055106, A055107, A074664, A101368, A124292, A124293, A124294, A124295, A140069, A153463, A153266, A153267, A144257, A211216, A002559, A082582.
KEYWORD
nonn,nice,easy,core,changed
a(n) = (2^(2*n + 1) + 1)/3.
(Formerly M2895)
+10
103
1, 3, 11, 43, 171, 683, 2731, 10923, 43691, 174763, 699051, 2796203, 11184811, 44739243, 178956971, 715827883, 2863311531, 11453246123, 45812984491, 183251937963, 733007751851, 2932031007403, 11728124029611, 46912496118443, 187649984473771, 750599937895083
COMMENTS
Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1)=u(k)+v(k)-w(k), v(k+1)=u(k)-v(k)+w(k), w(k+1)=-u(k)+v(k)+w(k); let M(k)=Max(u(k),v(k),w(k)); then a(n)=M(2n)=M(2n-1). - Benoit Cloitre, Mar 25 2002 Also the number of words of length 2n generated by the two letters s and t that reduce to the identity 1 by using the relations ssssss=1, tt=1 and stst=1. The generators s and t along with the three relations generate the dihedral group D6=C2xD3. - Jamaine Paddyfoot (jay_paddyfoot(AT)hotmail.com) and John W. Layman, Jul 08 2002 Number of walks of length 2n+1 between two adjacent vertices in the cycle graph C_6. Example: a(1)=3 because in the cycle ABCDEF we have three walks of length 3 between A and B: ABAB, ABCB and AFAB. - Emeric Deutsch, Apr 01 2004 Numbers of the form 1 + Sum_{i=1..m} 2^(2*i-1). - Artur Jasinski, Feb 09 2007 Prime numbers of the form 1+Sum[2^(2n-1)] are in A000979. Numbers x such that 1+Sum[2^(2n-1)] is prime for n=1,2,...,x is A127936. - Artur Jasinski, Feb 09 2007 Let A be the Hessenberg matrix of order n, defined by: A[1,j]=1, A[i,i]:=-6, (i>1), A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=1, a(n-1)=(-1)^(n-1)*charpoly(A,2). - Milan Janjic, Feb 21 2010 Number of toothpicks in the toothpick structure of A139250 after 2^n stages. - Omar E. Pol, Feb 28 2011 Numbers whose binary representation is "10" repeated (n-1) times with "11" appended on the end, n >= 1. For example 171 = 10101011 (2). - Omar E. Pol, Nov 22 2012 An Engel expansion of 2 to the base b := 4/3 as defined in A181565, with the associated series expansion 2 = b + b^2/3 + b^3/(3*11) + b^4/(3*11*43) + .... Cf. A007051. - Peter Bala, Oct 29 2013 The positive integer solution (x,y) of 3*x - 2^n*y = 1, n>=0, with smallest x is (a(n/2), 2) if n is even and (a((n-1)/2), 1) if n is odd. - Wolfdieter Lang, Feb 15 2014 The smallest positive number that requires at least n additions and subtractions of powers of 2 to be formed. See Puzzling StackExchange link. - Alexander Cooke Jul 16 2023
REFERENCES
H. W. Gould, Combinatorial Identities, Morgantown, 1972, (1.77), page 10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Eric Weisstein's World of Mathematics, Repunit
FORMULA
G.f.: (1-2*x)/(1-5*x+4*x^2). (End)
a(n) = Sum_{k = 0..n} binomial(n+k, 2*k)/2^(k - n).
a(n) = 4*a(n-1) - 1, n > 0.
a(n) = 1 + 2*Sum_{k = 0..n-1} 4^k;
a(0) = 1; a(n+1) = a(n) * 4 - 1. - Regis Decamps (decamps(AT)users.sf.net), Feb 04 2004 (correction to lead index by K. Spage, Aug 20 2014) a(n) = Sum_{i + j + k = n; 0 <= i, j, k <= n} (n+k)!/i!/j!/(2*k)!. - Benoit Cloitre, Mar 25 2004 a(n) = left and right terms in M^n * [1 1 1] where M = the 3X3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 1 1] = [a(n) A002450(n+1) a(n)] E.g. a(3) = 43 since M^n * [1 1 1] = [43 85 43] = [a(3) A002450(4) a(3)]. - Gary W. Adamson, Dec 18 2004 a(n) = Sum_{k = -floor(n/3)..floor(n/3)} binomial(2*n, n+3*k)/2. - Mircea Merca, Jan 28 2012 a(n) == 2*n + 1 (mod 3). Indeed, from Regis Decamps' formula (Feb 04 2004) we have a(i+1) - a(i) == -1 (mod 3), i= 0, 1, ..., n - 1. Summing, we have a(n) - 1 == -n (mod 3), and the formula follows. - Vladimir Shevelev, May 13, 20 2015 a(n) = Sum_{k = 0..2n} (-2)^k == 1 + Sum_{k = 1..n} 2^(2k-1). - Bob Selcoe, Aug 21 2016
MAPLE
a[0]:=1:for n from 1 to 50 do a[n]:=4*a[n-1]-1 od: seq(a[n], n=0..23); # Zerinvary Lajos, Feb 22 2008, with correction by K. Spage, Aug 20 2014 (2^(2*n+1)+1)/3 ;
MATHEMATICA
Table[(2^(2n+1) + 1)/3, {n, 0, 23}]
Table[1 + 2Sum[4^k, {k, 0, n-1}], {n, 0, 23}]
NestList[4# -1 &, 1, 23]
Table[Sum[Binomial[n+k, 2k]/2^(k-n), {k, 0, n}], {n, 0, 23}]
CoefficientList[Series[(1-2x)/(1-5x+4x^2), {x, 0, 23}], x] (* End *)
PROG
(PARI) a(n)=sum(k=-n\3, n\3, binomial(2*n+1, n+1+3*k))
(PARI) a=1; for(n=1, 23, print1(a, ", "); a=bitor(a, 3*a)) \\ K. Spage, Aug 20 2014 (PARI) Vec((1-2*x)/(1-5*x+4*x^2) + O(x^30)) \\ Altug Alkan, Dec 08 2015 (Haskell)
a007583 = (`div` 3) . (+ 1) . a004171
(Sage) [(2^(2*n+1) + 1)/3 for n in (0..25)] # G. C. Greubel, Dec 25 2019 (GAP) List([0..25], n-> (2^(2*n+1) + 1)/3); # G. C. Greubel, Dec 25 2019
CROSSREFS
Cf. location of records in A007302.
Bisection of Fibonacci triangle A037027: odd-indexed members of column sequences of A037027 (not counting leading zeros).
+10
10
1, 3, 2, 8, 10, 3, 21, 38, 22, 4, 55, 130, 111, 40, 5, 144, 420, 474, 256, 65, 6, 377, 1308, 1836, 1324, 511, 98, 7, 987, 3970, 6666, 6020, 3130, 924, 140, 8, 2584, 11822, 23109, 25088, 16435, 6588, 1554, 192, 9
COMMENTS
Companion triangle (odd-indexed members) A060920.
FORMULA
a(n, m) = (2*(n-m+1)* A060920(n, m-1)+2*(2*n+1)*a(n-1, m-1))/(5*m), n >= m>0; a(n, 0) := S(n, 3)= A001906(n+1) with Chebyshev's S(n, x) polynomials A049310; else 0. G.f. for column m >= 0: x^m*pFo(m+1, x)/(1-3*x+x^2)^(m+1), where pFo(n, x) := Sum_{m=0..n-1} A061177(n-1, m)*x^m (row polynomials of signed triangle A061177).
EXAMPLE
{1}; {3,2}; {8,10,3}; {21,38,22,4}; ...; pFo(2,x) = 2*(1-x).
Coefficients of polynomials ( (1 -x +sqrt(x))^n + (1 -x -sqrt(x))^n )/2.
+10
8
1, 1, -1, 1, -1, 1, 1, 0, 0, -1, 1, 2, -5, 2, 1, 1, 5, -15, 15, -5, -1, 1, 9, -30, 41, -30, 9, 1, 1, 14, -49, 77, -77, 49, -14, -1, 1, 20, -70, 112, -125, 112, -70, 20, 1, 1, 27, -90, 126, -117, 117, -126, 90, -27, -1, 1, 35, -105, 90, 45, -131, 45, 90, -105, 35, 1
COMMENTS
The row polynomial pFe(k+1, x) = Sum_{j=0..k+1} T(k+1, j)*x^j is the numerator of the g.f. for the k-th column sequence of A060920, the even part of the bisected Fibonacci triangle.
FORMULA
T(n, k) = coefficients of x^k of ((1-x+sqrt(x))^n + (1-x-sqrt(x))^n)/2.
T(n, k) = Sum_{j=0..k} (-1)^(k-j)*binomial(n, 2*j)*binomial(n-2*j, k-j), if 0 <= k <= floor(n/2) and T(n, k) = (-1)^n*T(n, n-k) if floor(n/2) < k <= n, otherwise 0.
EXAMPLE
The first few polynomials are:
pFe(0,x) = 1.
pFe(1,x) = 1 - x.
pFe(2,x) = 1 - x + x^2.
pFe(3,x) = 1 - 0*x + 0*x^2 - x^3.
pFe(4,x) = 1 + 2*x - 5*x^2 + 2*x^3 + x^4.
Number triangle begins as:
1;
1, -1;
1, -1, 1;
1, 0, 0, -1;
1, 2, -5, 2, 1;
1, 5, -15, 15, -5, -1;
1, 9, -30, 41, -30, 9, 1;
1, 14, -49, 77, -77, 49, -14, -1;
1, 20, -70, 112, -125, 112, -70, 20, 1;
MATHEMATICA
T[n_, k_]:= Sum[(-1)^(k+j)*Binomial[n, 2*j]*Binomial[n-2*j, k-j], {j, 0, k}];
Table[T[n, k], {n, 0, 15}, {k, 0, n}]//Flatten (* G. C. Greubel, Apr 06 2021 *)
PROG
(Magma)
A061176:= func< n, k | (&+[(-1)^(k+j)*Binomial(n, 2*j)*Binomial(n-2*j, k-j): j in [0..k]]) >;
(Sage)
def A061176(n, k): return sum((-1)^(k+j)*binomial(n, 2*j)*binomial(n-2*j, k-j) for j in (0..k))
Even-indexed terms of A001629(n), n >= 2, (Fibonacci convolution).
+10
7
1, 5, 20, 71, 235, 744, 2285, 6865, 20284, 59155, 170711, 488400, 1387225, 3916061, 10996580, 30737759, 85573315, 237387960, 656451269, 1810142185, 4978643596, 13661617195, 37409025455, 102238082976, 278920277425, 759695287349
COMMENTS
8*a(n) is the number of Boolean (equivalently, lattice, modular lattice, distributive lattice) intervals of the form [s,w] in the Bruhat order on S_n, where s is a simple reflection. - Bridget Tenner, Jan 16 2020
FORMULA
a(n) = ((2*n+1)*F(2*(n+1)) + 4*(n+1)*F(2*n+1))/5, with F(n) = A000045(n) (Fibonacci numbers). G.f.: (1 - x + x^2)/(1 - 3*x + x^2)^2.
a(n) = Sum_{k=1..n+1} k*binomial(2*n-2*k+2, k). - Emeric Deutsch, Jun 11 2003
PROG
(PARI) a(n) = ((2*n+1)*fibonacci(2*(n+1))+4*(n+1)*fibonacci(2*n+1))/5; \\ Jinyuan Wang, Jul 28 2019
Search completed in 0.023 seconds
|