A055244 -id:A055244 - cp's OEIS frontend

A001629 Self-convolution of Fibonacci numbers.

0, 0, 1, 2, 5, 10, 20, 38, 71, 130, 235, 420, 744, 1308, 2285, 3970, 6865, 11822, 20284, 34690, 59155, 100610, 170711, 289032, 488400, 823800, 1387225, 2332418, 3916061, 6566290, 10996580, 18394910, 30737759, 51310978, 85573315, 142587180, 237387960, 394905492

Offset: 0

N. J. A. Sloane

Number of elements in all subsets of {1,2,...,n-1} with no consecutive integers. Example: a(5)=10 because the subsets of {1,2,3,4} that have no consecutive elements, i.e., {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, the total number of elements is 10. - Emeric Deutsch, Dec 10 2003
If g is either of the real solutions to x^2-x-1=0, g'=1-g is the other one and phi is any 2 X 2-matricial solution to the same equation, not of the form gI or g'I, then Sum'_{i+j=n-1} g^i phi^j = F_n + (A001629(n) - A001629(n-1)g')*(phi-g'I), where i,j >= 0, F_n is the n-th Fibonacci number and I is the 2 X 2 identity matrix... - Michele Dondi (blazar(AT)lcm.mi.infn.it), Apr 06 2004
Number of 3412-avoiding involutions containing exactly one subsequence of type 321.
Number of binary sequences of length n with exactly one pair of consecutive 1's. - George J. Schaeffer (gschaeff(AT)andrew.cmu.edu), Sep 02 2004
For this sequence the n-th term is given by (nF(n+1)-F(n)+nF(n-1))/5 where F(n) is the n-th Fibonacci number. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), Apr 20 2005
If an unbiased coin is tossed n times then there are 2^n possible strings of H and T. Out of these, number of strings with exactly one 'HH' is given by a(n) where a(n) denotes n-th term of this sequence. - Mrs. J. P. Shiwalkar and M. N. Deshpande (dpratap_ngp(AT)sancharnet.in), May 04 2005
a(n) is half the number of horizontal dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; a(n+1) = the number of vertical dominoes in all domino tilings of a horizontally aligned 2 X n rectangle; thus 2*a(n)+a(n+1)=n*F(n+1) = the number of dominoes in all domino tilings of a 2 X n rectangle, where F=A000045, the Fibonacci sequence. - Roberto Tauraso, May 02 2005; Graeme McRae, Jun 02 2006
a(n+1) = (-i)^(n-1)*(d/dx)S(n,x)|A049310%20for%20the%20S-polynomials.%20-%20_Wolfdieter%20Lang">{x=i}, where i is the imaginary unit, n >= 1. First derivative of Chebyshev S-polynomials evaluated at x=i multiplied by (-i)^(n-1). See A049310 for the S-polynomials. - _Wolfdieter Lang, Apr 04 2007
For n >= 4, a(n) is the number of weak compositions of n-2 in which exactly one part is 0 and all other parts are either 1 or 2. - Milan Janjic, Jun 28 2010
For n greater than 1, a(n) equals the absolute value of (1 - (1/2 - i/2)*(1 + (-1)^(n + 1))) times the x-coefficient of the characteristic polynomial of the (n-1) X (n-1) tridiagonal matrix with i's along the main diagonal (i is the imaginary unit), 1's along the superdiagonal and the subdiagonal and 0's everywhere else (see Mathematica code below). - John M. Campbell, Jun 23 2011
For n > 0: a(n) = Sum_{k=1..n-1} (A039913(n-1,k)) / 2. - Reinhard Zumkeller, Oct 07 2012
The right-hand side of a binomial-coefficient identity [Gauthier]. - N. J. A. Sloane, Apr 09 2013
a(n) is the number of edges in the Fibonacci cube Gamma(n-1) (see the Klavzar 2005 reference, p. 149). Example: a(3)=2; indeed, the Fibonacci cube Gamma(2) is the path P(3) having 2 edges. - Emeric Deutsch, Aug 10 2014
a(n) is the number of c(i)'s, including repetitions, in p(n), where p(n)/q(n) is the n-th convergent p(n)/q(n) of the formal infinite continued fraction [c(0), c(1), ...]; e.g., the number of c(i)'s in p(3) = c(0)*c(1)*c(2)*c(3) + c(0)*c(1) + c(0)*c(3) + c(2)*c(3) + 1 is a(5) = 10. - Clark Kimberling, Dec 23 2015
Also the number of maximal and maximum cliques in the (n-1)-Fibonacci cube graph. - Eric W. Weisstein, Sep 07 2017
a(n+1) is the total number of fixed points in all permutations p on 1, 2, ..., n such that |k-p(k)| <= 1 for 1 <= k <= n. - Katharine Ahrens, Sep 03 2019
From Steven Finch, Mar 22 2020: (Start)
a(n+1) is the total binary weight (cf. A000120) of all A000045(n+2) binary sequences of length n not containing any adjacent 1's.
The only three 2-bitstrings without adjacent 1's are 00, 01 and 10. The bitsums of these are 0, 1 and 1. Adding these give a(3)=2.
The only five 3-bitstrings without adjacent 1's are 000, 001, 010, 100 and 101. The bitsums of these are 0, 1, 1, 1 and 2. Adding these give a(4)=5.
The only eight 4-bitstrings without adjacent 1's are 0000, 0001, 0010, 0100, 1000, 0101, 1010 and 1001. The bitsums of these are 0, 1, 1, 1, 1, 2, 2, and 2. Adding these give a(5)=10. (End)
Number of tilings of a 1 X n strip with monominoes (1 X 1 squares) and at least one domino (1 X 2 rectangles), where exactly one of the dominoes is colored gold. - Greg Dresden and Jiachen Weng, Jul 31 2025

			G.f. = x^2 + 2*x^3 + 5*x^4 + 10*x^5 + 20*x^6 + 38*x^7 + 71*x^8 + 130*x^9 + ... - _Michael Somos_, Jun 24 2018

Donald E. Knuth, Fundamental Algorithms, Addison-Wesley, 1968, p. 83, Eq. 1.2.8--(17). - Don Knuth, Feb 26 2019
Thomas Koshy, Fibonacci and Lucas Numbers with Applications, 2001, Chapter 15, page 187, "Hosoya's Triangle", and p. 375, eq. (32.13).
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
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).
S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989, p. 183, Nr.(98).

T. D. Noe, Table of n, a(n) for n = 0..500
Marco Abrate, Stefano Barbero, Umberto Cerruti and Nadir Murru, Colored compositions, Invert operator and elegant compositions with the "black tie", Discrete Math. 335 (2014), 1--7. MR3248794.
Katharine A. Ahrens, Combinatorial Applications of the k-Fibonacci Numbers: A Cryptographically Motivated Analysis, Ph. D. thesis, North Carolina State University (2020).
Carlos Alirio Rico Acevedo and Ana Paula Chaves, Double-Recurrence Fibonacci Numbers and Generalizations, arXiv:1903.07490 [math.NT], 2019.
Marcella Anselmo, Giuseppa Castiglione, Manuela Flores, Dora Giammarresi, Maria Madonia, and Sabrina Mantaci, Hypercubes and Isometric Words based on Swap and Mismatch Distance, arXiv:2303.09898 [math.CO], 2023.
Kassie Archer and Robert P. Laudone, Pattern avoidance and the fundamental bijection, arXiv:2407.06338 [math.CO], 2024. See p. 6.
Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar and Marko Petkovšek, Vertex and edge orbits of Fibonacci and Lucas cubes, arXiv:1407.4962 [math.CO], 2014. See Table 2.
Ali Reza Ashrafi, Jernej Azarija, Khadijeh Fathalikhani, Sandi Klavžar, et al., Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings, 2014.
Jean-Luc Baril, Sergey Kirgizov and Vincent Vajnovszki, Gray codes for Fibonacci q-decreasing words, arXiv:2010.09505 [cs.DM], 2020.
Daniel Birmajer, Juan Gil and Michael D. Weiner, Linear recurrence sequences and their convolutions via Bell polynomials, arXiv:1405.7727 [math.CO], 2014.
Daniel Birmajer, Juan B. Gil and Michael D. Weiner, Linear Recurrence Sequences and Their Convolutions via Bell Polynomials, Journal of Integer Sequences, 18 (2015), #15.1.2.
Matthew Blair, Rigoberto Flórez and Antara Mukherjee, Matrices in the Hosoya triangle, arXiv:1808.05278 [math.CO], 2018.
Matthew Blair, Rigoberto Flórez and Antara Mukherjee, Honeycombs in the Pascal triangle and beyond, arXiv:2203.13205 [math.HO], 2022. See p. 5.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Giuseppa Castiglione, Antonio Restivo and Marinella Sciortino, Circular Sturmian words and Hopcroft's algorithm, Theor. Comput. Sci. 410, No. 43, 4372-4381 (2009)
Charles H. Conley and Valentin Ovsienko, Shadows of rationals and irrationals: supersymmetric continued fractions and the super modular group, arXiv:2209.10426 [math-ph], 2022.
Éva Czabarka, Rigoberto Flórez and Leandro Junes, A Discrete Convolution on the Generalized Hosoya Triangle, Journal of Integer Sequences, 18 (2015), #15.1.6.
Eric S. Egge, Restricted 3412-Avoiding Involutions, p. 16, arXiv:math/0307050 [math.CO], 2003.
Sergio Falcon, Half self-convolution of the k-Fibonacci sequence, Notes on Number Theory and Discrete Mathematics (2020) Vol. 26, No. 3, 96-106.
Luca Ferrari and Emanuele Munarini, Enumeration of edges in some lattices of paths, arXiv:1203.6792 [math.CO], 2012.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
Rigoberto Flórez, Robinson Higuita and Alexander Ramírez, The resultant, the discriminant, and the derivative of generalized Fibonacci polynomials, arXiv:1808.01264 [math.NT], 2018.
Napoleon Gauthier (Proposer), Problem H-703, Fib. Quart., 50 (2012), 379-381.
Ricardo Gómez Aíza, Trees with flowers: A catalog of integer partition and integer composition trees with their asymptotic analysis, arXiv:2402.16111 [math.CO], 2024. See p. 23.
Martin Griffiths, Digit Proportions in Zeckendorf Representations, Fibonacci Quart. 48 (2010), no. 2, 168-174.
Verner E. Hoggatt, Jr. and M. Bicknell-Johnson, Fibonacci convolution sequences, Fib. Quart., 15 (1977), 117-122.
Milan Janjić, Hessenberg Matrices and Integer Sequences, J. Int. Seq. 13 (2010) # 10.7.8, section 3.
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 8.
Sandi Klavžar, On median nature and enumerative properties of Fibonacci-like cubes, Disc. Math. 299 (2005), 145-153.
Sandi Klavžar, Structure of Fibonacci cubes: a survey, Institute of Mathematics, Physics and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia; Preprint series Vol. 49 (2011), 1150 ISSN 2232-2094. (See Section 4.)
Toufik Mansour, Generalization of some identities involving the Fibonacci numbers, arXiv:math/0301157 [math.CO], 2003.
Toufik Mansour and Mark Shattuck, Pattern avoidance in flattened derangements, Disc. Math. Lett. (2025) Vol. 15, 67-74. See p. 74.
Pieter Moree, Convoluted convolved Fibonacci numbers, arXiv:math/0311205 [math.CO], 2003.
Pieter Moree, Convoluted Convolved Fibonacci Numbers, Journal of Integer Sequences, Vol. 7 (2004), Article 04.2.2.
László Németh, Walks on tiled boards, arXiv:2403.12159 [math.CO], 2024. See p. 2.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Valentin Ovsienko, Shadow sequences of integers, from Fibonacci to Markov and back, arXiv:2111.02553 [math.CO], 2021.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Mihai Prunescu and Lorenzo Sauras-Altuzarra, On the representation of C-recursive integer sequences by arithmetic terms, arXiv:2405.04083 [math.LO], 2024. See p. 18.
Jeffrey B. Remmel and J. L. B. Tiefenbruck, Q-analogues of convolutions of Fibonacci numbers, Australasian Journal of Combinatorics, Volume 64(1) (2016), Pages 166-193.
J. Riordan, Notes to N. J. A. Sloane, Jul. 1968
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Maximal Clique
Eric Weisstein's World of Mathematics, Maximum Clique
Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Row sums of triangles A058071, A134510, A134836.
First differences of A006478.
Cf. A000032, A000045, A001628, A010049, A037027, A055244, A214178.

List([0..40],n->Sum([0..n],k->Fibonacci(k)*Fibonacci(n-k))); # Muniru A Asiru, Jun 24 2018

a001629 n = a001629_list !! (n-1)
a001629_list = f [] $ tail a000045_list where
   f us (v:vs) = (sum $ zipWith (*) us a000045_list) : f (v:us) vs
-- Reinhard Zumkeller, Jan 18 2014, Oct 16 2011

I:=[0,0,1,2]; [n le 4 select I[n] else 2*Self(n-1)+Self(n-2)-2*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Nov 19 2014

a:= n-> (<<2|1|0|0>, <1|0|1|0>, <-2|0|0|1>, <-1|0|0|0>>^n)[1,3]:
seq(a(n), n=0..40); # Alois P. Heinz, Aug 01 2008
# Alternative:
A001629 := n -> `if`(n<2, 0, (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4)):
seq(simplify(A001629(n)), n=0..37); # Peter Luschny, Apr 10 2018

Table[Sum[Binomial[n-i, i] i, {i, 0, n}], {n, 0, 34}] (* Geoffrey Critzer, May 04 2009 *)
Table[Abs[(1 -(1/2 -I/2)(1 - (-1)^n))*Coefficient[CharacteristicPolynomial[ Array[KroneckerDelta[#1, #2] I + KroneckerDelta[#1 + 1, #2] + KroneckerDelta[#1 -1, #2] &, {n-1, n-1}], x], x]], {n,2,50}] (* John M. Campbell, Jun 23 2011 *)
LinearRecurrence[{2,1,-2,-1}, {0,0,1,2}, 40] (* Harvey P. Dale, Aug 26 2013 *)
CoefficientList[Series[x^2/(1-x-x^2)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Nov 19 2014 *)
Table[(2nFibonacci[n-1] + (n-1)Fibonacci[n])/5, {n, 0, 40}] (* Vladimir Reshetnikov, May 08 2016 *)
Table[With[{fibs=Fibonacci[Range[n]]},ListConvolve[fibs,fibs]],{n,-1,40}]//Flatten (* Harvey P. Dale, Aug 19 2018 *)

Vec(1/(1-x-x^2)^2+O(x^99)) \\ Charles R Greathouse IV, Feb 03 2014

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-2,1,2]^n)[2,4] \\ Charles R Greathouse IV, Jul 20 2016

def A001629(n): return (1/5)*(n*lucas_number2(n, 1, -1) - fibonacci(n))
[A001629(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

G.f.: x^2/(1 - x - x^2)^2. - Simon Plouffe in his 1992 dissertation
a(n) = A037027(n-1, 1), n >= 1 (Fibonacci convolution triangle).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), n > 3.
a(n) = Sum_{k=0..n} A000045(k)*A000045(n-k).
a(n+1) = Sum_{i=0..F(n)} A007895(i), where F = A000045, the Fibonacci sequence. - Claude Lenormand (claude.lenormand(AT)free.fr), Feb 04 2001
a(n) = Sum_{k=0..floor(n/2)-1} (k+1)*binomial(n-k-1, k+1). - Emeric Deutsch, Nov 15 2001
a(n) = floor( (1/5)*(n - 1/sqrt(5))*phi^n + 1/2 ) where phi=(1+sqrt(5))/2 is the golden ratio. - Benoit Cloitre, Jan 05 2003
a(n) = a(n-1) + A010049(n-1) for n > 0. - Emeric Deutsch, Dec 10 2003
a(n) = Sum_{k=0..floor((n-2)/2)} (n-k-1)*binomial(n-k-2, k). - Paul Barry, Jan 25 2005
a(n) = ((n-1)*F(n) + 2*n*F(n-1))/5, F(n)=A000045(n) (see Vajda and Koshy reference).
F'(n, 1), the first derivative of the n-th Fibonacci polynomial evaluated at 1. - T. D. Noe, Jan 18 2006
a(n) = a(n-1) + a(n-2) + F(n-1), where F=A000045, the Fibonacci sequence. - Graeme McRae, Jun 02 2006
a(n) = (1/5)*(n-1/sqrt(5))*((1+sqrt(5))/2)^n + (1/5)*(n+1/sqrt(5))*((1-sqrt(5))/2)^n. - Graeme McRae, Jun 02 2006
a(n) = A055244(n-1) - F(n-2). Example: a(6) = 20 = A055244(5) - F(3) = (23 - 3). - Gary W. Adamson, Jul 27 2007
a(n) = term (1,3) in the 4 X 4 matrix [2,1,0,0; 1,0,1,0; -2,0,0,1; -1,0,0,0]^n. - Alois P. Heinz, Aug 01 2008
a(n) = A214178(n,1) for n > 0. - Reinhard Zumkeller, Jul 08 2012
a(n) = ((n+1)*F(n-1) + (n-1)*F(n+1))/5. - Richard R. Forberg, Aug 04 2014
(n-2)*a(n) - (n-1)*a(n-1) - n*a(n-2) = 0, n > 1. - Michael D. Weiner, Nov 18 2014
a(n) = Sum_{i=0..n-1} Sum_{j=0..i} F(j-1)*F(i-j), where F(n) = A000045 Fibonacci Numbers. - Carlos A. Rico A., Jul 14 2016
a(n) = (n*Lucas(n) - Fibonacci(n))/5, where Lucas = A000032, Fibonacci = A000045. - Vladimir Reshetnikov, Sep 27 2016
a(n) = (n-1)*hypergeom([1-n/2, (3-n)/2], [1-n], -4) for n >= 2. - Peter Luschny, Apr 10 2018
a(n) = -(-1)^n a(-n) for all n in Z. - Michael Somos, Jun 24 2018
E.g.f.: (1/50)*exp(-2*x/(1+sqrt(5)))*(2*sqrt(5)-5*(-1+sqrt(5))*x+exp(sqrt(5)*x)*(-2*sqrt(5)+5*(1+sqrt(5))*x)). - Stefano Spezia, Sep 03 2019
From Peter Bala, Jan 14 2025: (Start)
a(2*n+1) is even and a(2*n) has the same parity as Fibonacci(n).
For n >= 1, a(n) = (2/n)*Sum_{k = 0..n} k*Fibonacci(k)*Fibonacci(n-k). (End)

A046854 Triangle read by rows: T(n, k) = binomial(floor((n+k)/2), k), n >= k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 3, 3, 4, 1, 1, 1, 3, 6, 4, 5, 1, 1, 1, 4, 6, 10, 5, 6, 1, 1, 1, 4, 10, 10, 15, 6, 7, 1, 1, 1, 5, 10, 20, 15, 21, 7, 8, 1, 1, 1, 5, 15, 20, 35, 21, 28, 8, 9, 1, 1, 1, 6, 15, 35, 35, 56, 28, 36, 9, 10, 1, 1, 1, 6, 21, 35, 70, 56, 84, 36, 45, 10, 11, 1, 1

Offset: 0

Wouter Meeussen

Row sums are Fibonacci(n+2). Diagonal sums are A016116. - Paul Barry, Jul 07 2004
Riordan array (1/(1-x), x/(1-x^2)). Matrix inverse is A106180. - Paul Barry, Apr 24 2005
As an infinite lower triangular matrix * [1,2,3,...] = A055244. - Gary W. Adamson, Dec 23 2008
From Emeric Deutsch, Jun 18 2010: (Start)
T(n,k) is the number of alternating parity increasing subsequences of {1,2,...,n} of size k, starting with an odd number (Terquem's problem, see the Riordan reference, p. 17). Example: T(8,5)=6 because we have 12345, 12347, 12367, 12567, 14567, and 34567.
T(n,k) is the number of alternating parity increasing subsequences of {1,2,...,n,n+1} of size k, starting with an even number. Example: T(7,4)=5 because we have 2345, 2347, 2367, 2567, and 4567. (End)
From L. Edson Jeffery, Mar 01 2011: (Start)
This triangle can be constructed as follows. Interlace two copies of the table of binomial coefficients to get the preliminary table
  1
  1
  1  1
  1  1
  1  2  1
  1  2  1
  1  3  3  1
  1  3  3  1
  ...,
then shift each entire r-th column up r rows, r=0,1,2,.... Also, a signed version of this sequence (A187660 in tabular form) begins with
  1;
  1, -1;
  1, -1, -1;
  1, -2, -1, 1;
  1, -2, -3, 1, 1;
  ...
(compare with A066170, A130777). Let T(N,k) denote the k-th entry in row N of the signed table. Then, for N>1, row N gives the coefficients of the characteristic function p_N(x) = Sum_{k=0..N} T(N,k)*x^(N-k) = 0 of the N X N matrix U_N=[(0 ... 0 1);(0 ... 0 1 1);...;(0 1 ... 1);(1 ... 1)]. Now let Q_r(t) be a polynomial with recurrence relation Q_r(t)=t*Q_(r-1)(t)-Q_(r-2)(t) (r>1), with Q_0(t)=1 and Q_1(t)=t. Then p_N(x)=0 has solutions Q_(N-1)(phi_j), where phi_j=2*(-1)^(j-1)*cos(j*Pi/(2*N+1)), j=1,2,...,N.
For example, row N=3 is {1,-2,-1,1}, giving the coefficients of the characteristic function p_3(x) = x^3-2*x^2-x+1 = 0 for the 3 X 3 matrix U_3=[(0 0 1);(0 1 1);(1 1 1)], with eigenvalues Q_2(phi_j)=[2*(-1)^(j-1)*cos(j*Pi/7)]^2-1, j=1,2,3. (End)
Given the signed polynomials (+--++--,...) of the triangle, the largest root of the n-th row polynomial is the longest (2n+1) regular polygon diagonal length, with edge = 1. Example: the largest root to x^3 - 2x^2 - x + 1 = 0 is 2.24697...; the longest heptagon diagonal, sin(3*Pi/7)/sin(Pi/7). - Gary W. Adamson, Sep 06 2011
Given the signed polynomials from Gary W. Adamson's comment, the largest root of the n-th polynomial also equals the length from the center to a corner (vertex) of a regular 2*(2*n+1)-sided polygon with side (edge) length = 1. - L. Edson Jeffery, Jan 01 2012
Put f(x,0) = 1 and f(x,n) = x + 1/f(x,n-1). Then f(x,n) = u(x,n)/v(x,n), where u(x,n) and v(x,n) are polynomials. The flattened triangles of coefficients of u and v are both essentially A046854, as indicated by the Mathematica program headed "Polynomials". - Clark Kimberling, Oct 12 2014
From Jeremy Dover, Jun 07 2016: (Start)
T(n,k) is the number of binary strings of length n+1 starting with 0 that have exactly k pairs of consecutive 0's and no pairs of consecutive 1's.
T(n,k) is the number of binary strings of length n+2 starting with 1 that have exactly k pairs of consecutive 0's and no pairs of consecutive 1's. (End)

			Triangle begins:
  1;
  1 1;
  1 1 1;
  1 2 1 1;
  1 2 3 1 1;
  1 3 3 4 1 1;
  ...

J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, 1978. [Emeric Deutsch, Jun 18 2010]

Nathaniel Johnston, Rows 0..100, flattened
Robert G. Donnelly, Molly W. Dunkum, and Rachel McCoy, Olry Terquem's forgotten problem, arXiv:2303.05949 [math.HO], 2023.
Jeremy M. Dover, Some Notes on Pairs in Binary Strings, arXiv:1609.00980 [math.CO], 2016.
Dominique Foata and Guo-Niu Han, Multivariable Tangent and Secant q-derivative Polynomials, arXiv:1304.2486 [math.CO], 2013; see Fig. 10.1.
Index entries for triangles and arrays related to Pascal's triangle

Reflected version of A065941, which is considered the main entry. A deficient version is in A030111.
Cf. A066170, A097806, A134513, A168561, A187660.
Cf. A055244. - Gary W. Adamson, Dec 23 2008

Flat(List([0..16], n-> List([0..n], k-> Binomial(Int((n+k)/2), k) ))); # G. C. Greubel, Jul 13 2019

a046854 n k = a046854_tabl !! n !! k
a046854_row n = a046854_tabl !! n
a046854_tabl = [1] : f [1] [1,1] where
   f us vs = vs : f vs  (zipWith (+) (us ++ [0,0]) ([0] ++ vs))
-- Reinhard Zumkeller, Apr 24 2013

[Binomial(Floor((n+k)/2), k): k in [0..n], n in [0..16]]; // G. C. Greubel, Jul 13 2019

A046854:= proc(n,k): binomial(floor(n/2+k/2), k) end: seq(seq(A046854(n,k),k=0..n),n=0..16); # Nathaniel Johnston, Jun 30 2011

Table[Binomial[Floor[(n+k)/2], k], {n,0,16}, {k,0,n}]//Flatten
(* next program: Polynomials *)
z = 12; f[x_, n_] := x + 1/f[x, n - 1]; f[x_, 1] = 1;
t = Table[Factor[f[x, n]], {n, 1, z}]
u = Flatten[CoefficientList[Numerator[t], x]] (* this sequence *)
v = Flatten[CoefficientList[Denominator[t], x]]
(* Clark Kimberling, Oct 13 2014 *)

T(n,k) = binomial((n+k)\2, k); \\ G. C. Greubel, Jul 13 2019

[[binomial(floor((n+k)/2), k) for k in (0..n)] for n in (0..16)] # G. C. Greubel, Jul 13 2019

T(n,k) = binomial(floor((n+k)/2), k).
G.f.: (1+x)/(1-x*y-x^2). - Ralf Stephan, Feb 13 2005
Triangle = A097806 * A168561, as infinite lower triangular matrices. - Gary W. Adamson, Oct 28 2007
T(n,k) = A065941(n,n-k) = abs(A130777(n,k)) = abs(A066170(n,k)) = abs(A187660(n,k)). - Johannes W. Meijer, Aug 08 2011
For n > 1: T(n, k) = T(n-1, k-1) + T(n-2, k), 0 < k < n-1. - Reinhard Zumkeller, Apr 24 2013
T(n,k) = A168561(n,k) + A168561(n-1,k). - R. J. Mathar, Feb 10 2024

A194778 T(n,k)=Number of lower triangles of an (n+2k-2)X(n+2k-2) 0..k array with new values introduced in row major order 0..k and no element unequal to more than one horizontal or vertical neighbor.

Original entry on oeis.org

1, 7, 3, 43, 17, 6, 268, 105, 41, 12, 1740, 672, 265, 95, 23, 11862, 4490, 1736, 655, 219, 43, 85013, 31466, 11857, 4464, 1641, 493, 79, 639760, 231445, 85007, 31429, 11686, 4069, 1101, 143, 5045610, 1784788, 639753, 231395, 84727, 30608, 10121, 2427, 256

Offset: 1

R. H. Hardin Sep 02 2011

Table starts
...1....7....43....268....1740....11862.....85013.....639760....5045610
...3...17...105....672....4490....31466....231445....1784788...14404218
...6...41...265...1736...11857....85007....639753....5045602...41615156
..12...95...655...4464...31429...231395...1784723...14404136..121420974
..23..219..1641..11686...84727...639325...5044981...41614291..358184223
..43..493..4069..30608..229869..1782111..14399939..121414559.1066897441
..79.1101.10121..80961..631373..5029741..41587186..358138793.3210593393
.143.2427.25025.214469.1745459.14321783.121261490.1066617315

			Some solutions for n=2 k=2
..0........0........0........0........0........0........0........0
..0.0......0.0......1.1......1.1......0.0......1.1......0.1......0.0
..1.1.1....0.0.1....1.1.2....1.1.1....0.0.0....1.1.1....0.1.1....0.0.0
..1.1.1.0..0.0.1.1..1.1.2.2..0.0.0.0..0.0.0.1..2.2.2.2..0.1.1.0..1.1.1.1

R. H. Hardin, Table of n, a(n) for n = 1..120

Column 1 is A055244

A194540 T(n,k) is the number of lower triangles of an n X n 0..k array with new values introduced in row major order 0..k and no element equal to more than one horizontal or vertical neighbor.

Original entry on oeis.org

1, 1, 3, 1, 4, 6, 1, 4, 59, 12, 1, 4, 116, 1851, 23, 1, 4, 131, 16556, 119548, 43, 1, 4, 132, 43785, 7721920, 16039294, 79, 1, 4, 132, 62038, 79201795, 11525456507, 4460214471, 143, 1, 4, 132, 67377, 286773762, 627974590650, 54979732214116, 2572187445993

Offset: 1

R. H. Hardin, Aug 28 2011

			Table starts:
...1.............1..................1......................1
...3.............4..................4......................4
...6............59................116....................131
..12..........1851..............16556..................43785
..23........119548............7721920...............79201795
..43......16039294........11525456507...........627974590650
..79....4460214471.....54979732214116......21399815343394998
.143.2572187445993.838387866908847478.3132305932642809585983
Some solutions for n=4 and k=3:
..0........0........0........0........0........0........0........0
..1.2......1.0......1.0......1.0......0.1......1.2......1.0......1.2
..3.1.1....0.1.0....2.0.3....2.3.1....2.3.0....1.3.3....2.3.3....0.3.1
..2.3.2.0..2.1.3.1..2.1.0.1..1.0.3.2..3.0.3.1..3.1.1.2..0.2.2.0..2.1.2.1

R. H. Hardin, Table of n, a(n) for n = 1..86

Column 1 is A055244.

A131913 Product of the square matrix in A065941 and the column vector (1, 2, 3, ...)'.

Original entry on oeis.org

1, 3, 6, 13, 25, 48, 89, 163, 294, 525, 929, 1632, 2849, 4947, 8550, 14717, 25241, 43152, 73561, 125075, 212166, 359133, 606721, 1023168, 1722625, 2895843, 4861254, 8149933, 13646809, 22825200, 38136089, 63653827, 106146534, 176849517, 294401825, 489706272

Offset: 0

Gary W. Adamson, Jul 27 2007

			a(4) = 25 = (1, 1, 3, 2, 1) dot (1, 2, 3, 4, 5) = (1 + 2 + 9 + 8 + 5), where (1, 1, 3, 2, 1) = row 4 of triangle A065941.
a(4) = 25 = A010049(4) + A001629(6) = 5 + 20.
a(5) = 48 = A055244(6) + A001629(4) = 43 + 5.

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Cf. A000045, A065941, A010049, A001629, A055244.

a(n) = A010049(n) + A001629(n+2) = A055244(n+1) + A001629(n-1).
From Philippe Deléham, Dec 28 2013: (Start)
G.f.: (1+x-x^2)/(1-x-x^2)^2.
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3) - a(n-4), a(0)=1, a(1)=3, a(2)=6, a(3)=13.
a(n) = a(n-1) + a(n-2) + 2*Fibonacci(n). (End)

A055245 Numerator sequence of mean length of certain stackings of n+1 squares on a double staircase.

Original entry on oeis.org

1, 1, 5, 12, 28, 61, 127, 257, 507, 982, 1872, 3523, 6557, 12089, 22105, 40128, 72380, 129809, 231611, 411337, 727455, 1281578, 2249856, 3936935, 6868537, 11950033, 20737613, 35901300, 62014396, 106897669, 183905143, 315806321, 541372131

Offset: 0

Wolfdieter Lang, May 10 2000

Denominator sequence is A055244(n).

L. Turban, Lattice animals on a staircase and Fibonacci numbers, J.Phys. A 33 (2000) 2587-2595.

Index entries for linear recurrences with constant coefficients, signature (3, 0, -5, 0, 3, 1).

Cf. A000045, A055244.

a:= n-> (Matrix([[1,-1,0,2,-9,25]]). Matrix(6, (i,j)-> if (i=j-1) then 1 elif j=1 then [3,0,-5,0,3,1][i] else 0 fi)^(n))[1,1]: seq(a(n), n=0..32); # Alois P. Heinz, Aug 05 2008

CoefficientList[Series[(1-2x+2x^2+2x^3-3x^4-x^5)/(1-x-x^2)^3,{x,0,50}],x] (* or *) LinearRecurrence[{3,0,-5,0,3,1},{1,1,5,12,28,61},50] (* Harvey P. Dale, Aug 24 2014 *)

G.f.: (1-2*x+2*x^2+2*x^3-3*x^4-x^5)/(1-x-x^2)^3. (from Turban reference eq.(3.11)).
a(n) = ((5*n^2+3*n-27)*F(n)+(19*n+25)*F(n+1))/25 with F(n)=A000045(n) (Fibonacci numbers) (from Turban reference eq.(3.12)).
a(0)=1, a(1)=1, a(2)=5, a(3)=12, a(4)=28, a(5)=61, a(n)=3*a(n-1)- 5*a(n-3)+ 3*a(n-5)+a(n-6). - Harvey P. Dale, Aug 24 2014

A129718 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k runs of 1's (n >= 0, 0 <= k <= floor((n+1)/2)). A Fibonacci binary word is a binary word having no 00 subword. A run of 1's is a maximal subword of the form 11..1.

Original entry on oeis.org

1, 1, 1, 0, 3, 0, 4, 1, 0, 4, 4, 0, 4, 8, 1, 0, 4, 12, 5, 0, 4, 16, 13, 1, 0, 4, 20, 25, 6, 0, 4, 24, 41, 19, 1, 0, 4, 28, 61, 44, 7, 0, 4, 32, 85, 85, 26, 1, 0, 4, 36, 113, 146, 70, 8, 0, 4, 40, 145, 231, 155, 34, 1, 0, 4, 44, 181, 344, 301, 104, 9, 0, 4, 48, 221, 489, 532, 259, 43, 1

Offset: 0

Emeric Deutsch, May 12 2007

Row n has 1+floor((n+1)/2) terms.
Row sums are the Fibonacci numbers (A000045).
T(n,k) = A129717(n,k-1) (since in each word the number of runs of 1's = 1 + the number of 101's).
Sum_{k=0..floor((n+1)/2)} k*T(n,k) = A055244(n) (n >= 1).

			T(6,3)=5 because we have 110101, 101101, 101010, 101011 and 010101.
Triangle starts:
  1;
  1,  1;
  0,  3;
  0,  4,  1;
  0,  4,  4;
  0,  4,  8,  1;
  0,  4, 12,  5;

Cf. A000045, A129717, A055244.

G:=(1+z)*(1-z+t*z)/(1-z-t*z^2): Gser:=simplify(series(G,z=0,21)): for n from 0 to 18 do P[n]:=sort(coeff(Gser,z,n)) od: for n from 0 to 17 do seq(coeff(P[n],t,j),j=0..ceil(n/2)) od; # yields sequence in triangular form

G.f. = G(t,z) = (1+z)(1-z+tz)/(1-z-tz^2).

T(n,k) = binomial(n-k,k-1) + 2*binomial(n-k-1,k-1) + binomial(n-k-2,k-1) for n >= 4 and 0 <= k < floor((n+1)/2).

cp's OEIS Frontend

A001629 Self-convolution of Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A046854 Triangle read by rows: T(n, k) = binomial(floor((n+k)/2), k), n >= k >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

A194778 T(n,k)=Number of lower triangles of an (n+2k-2)X(n+2k-2) 0..k array with new values introduced in row major order 0..k and no element unequal to more than one horizontal or vertical neighbor.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A194540 T(n,k) is the number of lower triangles of an n X n 0..k array with new values introduced in row major order 0..k and no element equal to more than one horizontal or vertical neighbor.

Views

Author

Keywords

Examples

Links

Crossrefs

A131913 Product of the square matrix in A065941 and the column vector (1, 2, 3, ...)'.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A055245 Numerator sequence of mean length of certain stackings of n+1 squares on a double staircase.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A129718 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k runs of 1's (n >= 0, 0 <= k <= floor((n+1)/2)). A Fibonacci binary word is a binary word having no 00 subword. A run of 1's is a maximal subword of the form 11..1.

Views

Author

Keywords

Comments

Examples

Crossrefs