A035317 -id:A035317 - cp's OEIS frontend

A001654 Golden rectangle numbers: F(n) * F(n+1), where F(n) = A000045(n) (Fibonacci numbers).

0, 1, 2, 6, 15, 40, 104, 273, 714, 1870, 4895, 12816, 33552, 87841, 229970, 602070, 1576239, 4126648, 10803704, 28284465, 74049690, 193864606, 507544127, 1328767776, 3478759200, 9107509825, 23843770274, 62423800998, 163427632719, 427859097160, 1120149658760

Offset: 0

N. J. A. Sloane

a(n)/A007598(n) ~= golden ratio, especially for larger n. - Robert Happelberg (roberthappelberg(AT)yahoo.com), Jul 25 2005
Let phi be the golden ratio (cf. A001622). Then 1/phi = phi - 1 = Sum_{n>=1} (-1)^(n-1)/a(n), an alternating infinite series consisting solely of unit fractions. - Franz Vrabec, Sep 14 2005
a(n+2) is the Hankel transform of A005807 aerated. - Paul Barry, Nov 04 2008
A more exact name would be: Golden convergents to rectangle numbers. These rectangles are not actually golden (ratio of sides is not phi) but are golden convergents (sides are numerator and denominator of convergents in the continued fraction expansion of phi, whence ratio of sides converges to phi). - Daniel Forgues, Nov 29 2009
The Kn4 sums (see A180662 for definition) of the "Races with Ties" triangle A035317 lead to this sequence. - Johannes W. Meijer, Jul 20 2011
Numbers m such that m(5m+2)+1 or m(5m-2)+1 is a square. - Bruno Berselli, Oct 22 2012
In pairs, these numbers are important in finding binomial coefficients that appear in at least six places in Pascal's triangle. For instance, the pair (m,n) = (40, 104) finds the numbers binomial(n-1,m) = binomial(n,m-1). Two additional numbers are found on the other side of the triangle. The final two numbers appear in row binomial(n-1,m). See A003015. - T. D. Noe, Mar 13 2013
For n>1, a(n) is one-half the area of the trapezoid created by the four points (F(n),L(n)), (L(n),F(n)), (F(n+1), L(n+1)), (L(n+1), F(n+1)) where F(n) = A000045(n) and L(n) = A000032(n). - J. M. Bergot, May 14 2014
[Note on how to calculate: take the two points (a,b) and (c,d) with aa(n) = A067962(n-1) / A067962(n-2), n > 1. - Reinhard Zumkeller, Sep 24 2015
Can be obtained (up to signs) by setting x = F(n)/F(n+1) in g.f. for Fibonacci numbers - see Pongsriiam. - N. J. A. Sloane, Mar 23 2017

			G.f. = x + 2*x^2 + 6*x^3 + 15*x^4 + 40*x^5 + 104*x^6 + 273*x^7 + 714*x^8 + ...

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 9.
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).

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from T. D. Noe)
R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., Vol. 58, No. 2 (2020), 140-142.
Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays, JIS 12 (2009) 09.8.6.
A. Brousseau, A sequence of power formulas, Fib. Quart., 6 (1968), 81-83.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 17.
Ömer Egecioglu, Elif Saygi, and Zülfükar Saygi, The Mostar index of Fibonacci and Lucas cubes, arXiv:2101.04740 [math.CO], 2021. Mentions this sequence.
Shalosh B. Ekhad and Doron Zeilberger, Automatic Counting of Tilings of Skinny Plane Regions, arXiv preprint arXiv:1206.4864 [math.CO], 2012.
Sergio Falcon, On the Sequences of Products of Two k-Fibonacci Numbers, American Review of Mathematics and Statistics, March 2014, Vol. 2, No. 1, pp. 111-120.
Dale Gerdemann, Golden Ratio Base Digit Patterns for Columns of the Fibonomial Triangle, "Another interesting pattern is for Golden Rectangle Numbers A001654. I made a short video illustrating this pattern, along with other columns of the Fibonomial Triangle A010048".
Jonny Griffiths and Martin Griffiths, Fibonacci-related sequences via iterated QRT maps, Fib. Q., 51 (2013), 218-227.
James P. Jones and Péter Kiss, Representation of integers as terms of a linear recurrence with maximal index, Acta Academiae Paedagogicae Agriensis, Sectio Mathematicae, 25. (1998) pp. 21-37. See Lemma 4.1 p. 34.
Ronald Orozco López, Generating Functions of Generalized Simplicial Polytopic Numbers and (s,t)-Derivatives of Partial Theta Function, arXiv:2408.08943 [math.CO], 2024. See p. 11.
Ronald Orozco López, Simplicial d-Polytopic Numbers Defined on Generalized Fibonacci Polynomials, arXiv:2501.11490 [math.CO], 2025. See p. 6.
C. Pita, On s-Fibonomials, J. Int. Seq. 14 (2011) # 11.3.7.
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
Prapanpong Pongsriiam, Integral Values of the Generating Functions of Fibonacci and Lucas Numbers, College Math. J., 48 (No. 2 2017), pp 97ff.
M. Renault, Dissertation
Wikipedia, Illustration of 273 as a golden rectangle number.
Robert G. Wilson v, Letter to N. J. A. Sloane, circa 1993
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (2,2,-1).

Cf. A001655, A001656, A001657, A001658, A010048, A067962.
Cf. A005968, A005969, A098531, A098532, A098533, A119283, A128697.
Cf. A000071, A079472, A080145, A239798, A290565.
Bisection of A006498, A070550, A080239.
First differences of A064831.
Partial sums of A007598.

a001654 n = a001654_list !! n
a001654_list = zipWith (*) (tail a000045_list) a000045_list
-- Reinhard Zumkeller, Jun 08 2013

I:=[0,1,2]; [n le 3 select I[n] else 2*Self(n-1) + 2*Self(n-2) - Self(n-3): n in [1..30]]; // G. C. Greubel, Jan 17 2018

with(combinat): A001654:=n->fibonacci(n)*fibonacci(n+1):
seq(A001654(n), n=0..28); # Zerinvary Lajos, Oct 07 2007

LinearRecurrence[{2,2,-1}, {0,1,2}, 100] (* Vladimir Joseph Stephan Orlovsky, Jul 03 2011 *)
Times@@@Partition[Fibonacci[Range[0,30]],2,1] (* Harvey P. Dale, Aug 18 2011 *)
Accumulate[Fibonacci[Range[0, 30]]^2] (* Paolo Xausa, May 31 2024 *)

A001654(n)=fibonacci(n)*fibonacci(n+1);

b(n, k)=prod(j=1, k, fibonacci(n+j)/fibonacci(j));
vector(30, n, b(n-1, 2))  \\ Joerg Arndt, May 08 2016

from sympy import fibonacci as F
def a(n): return F(n)*F(n + 1)
[a(n) for n in range(101)] # Indranil Ghosh, Aug 03 2017

from math import prod
from gmpy2 import fib2
def A001654(n): return prod(fib2(n+1)) # Chai Wah Wu, May 19 2022

a(n) = A010048(n+1, 2) = Fibonomial(n+1, 2).
a(n) = A006498(2*n-1).
a(n) = a(n - 1) + A007598(n) = a(n - 1) + A000045(n)^2 = Sum_{j <= n} Fibonacci(j)^2. - Henry Bottomley, Feb 09 2001 [corrected by Ridouane Oudra, Apr 12 2025]
For n > 0, 1 - 1/a(n+1) = Sum_{k=1..n} 1/(F(k)*F(k+2)) where F(k) is the k-th Fibonacci number. - Benoit Cloitre, Aug 31 2002.
G.f.: x/(1-2*x-2*x^2+x^3) = x/((1+x)*(1-3*x+x^2)). (Simon Plouffe in his 1992 dissertation; see Comments to A055870),
a(n) = 3*a(n-1) - a(n-2) - (-1)^n = -a(-1-n).
Let M = the 3 X 3 matrix [1 2 1 / 1 1 0 / 1 0 0]; then a(n) = the center term in M^n *[1 0 0]. E.g., a(5) = 40 since M^5 * [1 0 0] = [64 40 25]. - Gary W. Adamson, Oct 10 2004
a(n) = Sum{k=0..n} Fibonacci(k)^2. The proof is easy. Start from a square (1*1). On the right side, draw another square (1*1). On the above side draw a square ((1+1)*(1+1)). On the left side, draw a square ((1+2)*(1+2)) and so on. You get a rectangle (F(n)*F(1+n)) which contains all the squares of side F(1), F(2), ..., F(n). - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 19 2007
With phi = (1+sqrt(5))/2, a(n) = round((phi^(2*n+1))/5) = floor((1/2) + (phi^(2*n+1))/5), n >= 0. - Daniel Forgues, Nov 29 2009
a(n) = 2*a(n-1) + 2*a(n-2) - a(n-3), a(1)=1, a(2)=2, a(3)=6. - Sture Sjöstedt, Feb 06 2010
a(n) = (A002878(n) - (-1)^n)/5. - R. J. Mathar, Jul 22 2010
a(n) = 1/|F(n+1)/F(n) - F(n)/F(n-1)| where F(n) = Fibonacci numbers A000045. b(n) = F(n+1)/F(n) - F(n)/F(n-1): 1/1, -1/2, 1/6, -1/15, 1/40, -1/104, ...; c(n) = 1/b(n) = a(n)*(-1)^(n+1): 1, -2, 6, -15, 40, -104, ... (n=1,2,...). - Thomas Ordowski, Nov 04 2010
a(n) = (Fibonacci(n+2)^2 - Fibonacci(n-1)^2)/4. - Gary Detlefs, Dec 03 2010
Let d(n) = n mod 2, a(0)=0 and a(1)=1. For n > 1, a(n) = d(n) + 2*a(n-1) + Sum_{k=0..n-2} a(k). - L. Edson Jeffery, Mar 20 2011
From Tim Monahan, Jul 11 2011: (Start)
a(n+1) = ((2+sqrt(5))*((3+sqrt(5))/2)^n+(2-sqrt(5))*((3-sqrt(5))/2)^n+(-1)^n)/5.
a(n) = ((1+sqrt(5))*((3+sqrt(5))/2)^n+(1-sqrt(5))*((3-sqrt(5))/2)^n-2*(-1)^n)/10. (End)
From Wolfdieter Lang, Jul 21 2012: (Start)
a(n) = (2*A059840(n+2) - A027941(n))/3, n >= 0, with A059840(n+2) = Sum_{k=0..n} F(k)*F(k+2) and A027941(n) = A001519(n+1) - 1, n >= 0, where A001519(n+1) = F(2*n+1). (End)
a(n) = (-1)^n * Sum_{k=0..n} (-1)^k*F(2*k), n >= 0. - Wolfdieter Lang, Aug 11 2012
a(-1-n) = -a(n) for all n in Z. - Michael Somos, Sep 19 2014
0 = a(n)*(+a(n+1) - a(n+2)) + a(n+1)*(-2*a(n+1) + a(n+2)) for all n in Z. - Michael Somos, Sep 19 2014
a(n) = (L(2*n+1) - (-1)^n)/5 with L(k) = A000032(k). - J. M. Bergot, Apr 15 2016
E.g.f.: ((3 + sqrt(5))*exp((5+sqrt(5))*x/2) - 2*exp((2*x)/(3+sqrt(5))+x) - 1 - sqrt(5))*exp(-x)/(5*(1 + sqrt(5))). - Ilya Gutkovskiy, Apr 15 2016
From Klaus Purath, Apr 24 2019: (Start)
a(n) = A061646(n) - Fibonacci(n-1)^2.
a(n) = (A061646(n+1) - A061646(n))/2. (End)
a(n) = A226205(n+1) + (-1)^(n+1). - Flávio V. Fernandes, Apr 23 2020
Sum_{n>=1} 1/a(n) = A290565. - Amiram Eldar, Oct 06 2020
Product_{n>=2} (1 + (-1)^n/a(n)) = phi^2/2 (A239798). - Amiram Eldar, Dec 02 2024
G.f.: x * exp( Sum_{k>=1} F(3*k)/F(k) * x^k/k ), where F(n) = A000045(n). - Seiichi Manyama, May 07 2025

Extended by Wolfdieter Lang, Jun 27 2000

A026641 Number of nodes of even outdegree (including leaves) in all ordered trees with n edges.

Original entry on oeis.org

1, 1, 4, 13, 46, 166, 610, 2269, 8518, 32206, 122464, 467842, 1794196, 6903352, 26635774, 103020253, 399300166, 1550554582, 6031074184, 23493410758, 91638191236, 357874310212, 1399137067684, 5475504511858, 21447950506396

Offset: 0

Clark Kimberling

Number of lattice paths from (0,0) to (n,n) using steps (1,0),(0,2),(1,1). - Joerg Arndt, Jun 30 2011
From Emeric Deutsch, Jan 25 2004: (Start)
Let B = 1/sqrt(1-4*z) = g.f. for central binomial coeffs (A000984); F = (1-sqrt(1-4*z))/(z*(3-sqrt(1-4*z))) = g.f. for (A000957).
B = 1 + 2*z + 6*z^2 + 20*z^3 + ... gives the number of nodes in all ordered trees with 0,1,2,3,... edges. On p. 288 of the Deutsch-Shapiro paper one finds that z*B*F = z + 2*z^2 + 7*z^3 + 24*z^4 + ... gives the number of nodes of odd outdegree in all ordered trees with 1,2,3,... edges (cf. A014300).
Consequently, B - z*B*F = 2/(3*sqrt(1-4*z)-1+4*z) = 1 + z + 4*z^2 + 13*z^3 + 46*z^4 + ... gives the total number of nodes of even degree in all ordered trees with 0,1,2,3,4,... edges.  (End)
Main diagonal of the following array: first column is filled with 1's, first row is filled alternatively with 1's or 0's: m(i,j) = m(i-1,j) + m(i,j-1): 1 0 1 0 1 ... / 1 1 2 2 3 ... / 1 2 4 6 9 ... / 1 3 7 13 22 ... / 1 4 11 24 46 ... - Benoit Cloitre, Aug 05 2002
The Hankel transform of [1,1,4,13,46,166,610,2269,...] is 3^n. - Philippe Deléham, Mar 08 2007
Second binomial transform of A127361. - Philippe Deléham, Mar 14 2007
Starting with offset 1, generated from iterates of M * [1,1,1,...]; where M = a tridiagonal matrix with (0,2,2,2,...) in the main diagonal and (1,1,1,...) in the super and subdiagonals. - Gary W. Adamson, Jan 04 2009
Equals left border of triangle A158815. - Gary W. Adamson, Mar 27 2009
Equals the INVERTi transform of A101850: (1, 2, 7, 26, 100, ...). - Gary W. Adamson, Jan 10 2012
Diagonal of rational function 1/(1 - (x + x*y + y^2)). - Gheorghe Coserea, Aug 06 2018
Let A(i, j) denote the infinite array such that the i-th row of this array is the sequence obtained by applying the partial sum operator i times to the function (-1)^(n+1) for n > 0. Then A(n, n) equals a(n-1) for all n > 0. - John M. Campbell, Jan 20 2019
These numbers have the same parity as the Catalan numbers A000108; that is, a(n) is odd if and only if n = 2^k - 1 for some nonnegative integer k. It appears that if a(n) is odd then a(n) == 1 (mod 4). - Peter Bala, Feb 07 2024
The number a(n)/(n+1) is the coefficient of x^(n+1) in log(1+(1-sqrt(1-4*x))/2), the generating series of the Sabinin operad. - F. Chapoton, Mar 14 2024

			From _Joerg Arndt_, Jul 01 2011: (Start)
The triangle of number of lattice paths from (0,0) to (n,k) using steps (1,0),(0,2),(1,1) begins
  1;
  1, 1;
  1, 2,  4;
  1, 3,  7, 13;
  1, 4, 11, 24,  46;
  1, 5, 16, 40,  86, 166;
  1, 6, 22, 62, 148, 314,  610;
  1, 7, 29, 91, 239, 553, 1163, 2269;
This sequence is the diagonal. (End)
G.f. = 1 + x + 4*x^2 + 13*x^3 + 46*x^4 + 166*x^5 + 610*x^6 + 2269*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Isaac DeJager, Madeleine Naquin, and Frank Seidl, Colored Motzkin Paths of Higher Order, VERUM 2019.
Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
Karl Dilcher and Maciej Ulas, Arithmetic properties of polynomial solutions of the Diophantine equation P(x)x^(n+1)+Q(x)(x+1)^(n+1) = 1, arXiv:1909.11222 [math.NT], 2019.
Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.

Cf. A101850, A120588, A158815.

Cf. A091526 (k=-2), A072547 (k=-1), this sequence (k=0), A014300 (k=1), A014301 (k=2), A172025 (k=3), A172061 (k=4), A172062 (k=5), A172063 (k=6), A172064 (k=7), A172065 (k=8), A172066 (k=9), A172067 (k=10).

List([0..25],n->(-1)^n*Sum([0..n],k->(-1)^k*Binomial(n+k,k))); # Muniru A Asiru, Aug 06 2018

[(-1)^n*(&+[(-1)^k*Binomial(n+k, k): k in [0..n]]): n in [0..30]]; // G. C. Greubel, Feb 12 2019

seq(add((binomial(k+n, n-k)*binomial(n-k, k)),k=0..floor(n/2)),n=0..30);
# From Richard Choulet, Jan 22 2010: (Start)
a:= n -> add(binomial(2*n-k, k)*binomial(k, n-k), k=floor(n/2)..n):
a:= n -> `if`(n<2, 1, (3/(2))*binomial(2*n-1, n-1)-(1/2)*a(n-1)):
a:= n -> (-1/2)^(n+2)+(2/3)*add(4^(n-k)*(binomial(2*k, k)*(1/(1-2*k))
        *(1-(-1/8)^(n-k+1))), k=0..n):
a:= n -> (-1/2)^(n+2)+(3/4)*add(((-1/2)^(n-k))*(binomial(2*k, k)), k=0..n):
seq(a(n), n=0..30); # (End)
gf := log(1 + (1 - sqrt(1 - 4*x))/2) / x: ser := series(gf, x, 30):
seq((n + 1)*coeff(ser, x, n), n = 0..24);  # Peter Luschny, Mar 16 2024

f[n_]:= Sum[ Binomial[n+k, k]*Cos[Pi*(n+k)], {k, 0, n}]; Array[f, 25, 0] (* Robert G. Wilson v, Apr 02 2012 *)
CoefficientList[Series[2/(3*Sqrt[1-4*x]-1+4*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)
a[ n_]:= SeriesCoefficient[ D[ Log[1+(1-Sqrt[1-4x])/2], x], {x, 0, n}]; (* Michael Somos, May 18 2015 *)

a(n)=(-1)^n*sum(k=0,n,(-1)^k*binomial(n+k,k))

/* same as in A092566 but use */
steps=[[1,0], [0,2], [1,1]]; /* Joerg Arndt, Jun 30 2011 */

[(-1)^n*sum((-1)^k*binomial(n+k, k) for k in (0..n)) for n in (0..30)] # G. C. Greubel, Feb 12 2019

G.f. is logarithmic derivative of the generating function for the Catalan numbers A000108. So this sequence might be called the "log-Catalan" numbers. - Murray R. Bremner, Jan 25 2004
a(n) = Sum_{k=0..floor(n/2)} binomial(k+n, n-k)*binomial(n-k, k). - Detlef Pauly (dettodet(AT)yahoo.de), Nov 15 2001
G.f.: 2/(3*sqrt(1-4*z)-1+4*z). - Emeric Deutsch, Jul 09 2002
a(n) = (-1)^n*Sum_{k=0..n} (-1)^k*C(n+k, k). - Benoit Cloitre, Aug 20 2002
a(n) = Sum_{j=0..floor(n/2)} binomial(2*n-2*j-1, n-1). - Emeric Deutsch, Jan 28 2004
From Paul Barry, Dec 18 2004: (Start)
A Catalan transform of the Jacobsthal numbers A001045(n+1) under the mapping G(x)-> G(xc(x)), c(x) the g.f. of A000108. The inverse mapping is H(x)->H(x(1-x)).
a(n) = Sum_{k=0..n} (k/(2*n-k))*binomial(2*n-k, n-k)*A001045(k+1). (End)
a(n) = Sum_{k=0..n} binomial(2*n-k, k)*binomial(k, n-k). - Paul Barry, Jul 25 2005
a(n) = Sum_{k=0..n-1} A126093(n,k). - Philippe Deléham, Mar 08 2007
a(n) = (-1/2)^(n+2) + (2/3)*Sum_{k=0..n} ( (4^n-k)*binomial(2*k,k)*(1/(1-2*k))*(1-(-1/8)^(n-k+1)) ). - Yalcin Aktar, Jul 06 2007
a(n) = (-1/2)^(n+2) + (3/4)*Sum_{k=0..n} (-1/2)^(n-k)*binomial(2*k,k). - Yalcin Aktar, Jul 06 2007
From Richard Choulet, Jan 22 2010: (Start)
a(n) = (3*binomial(2*n-1,n-1) - d(n-1))/2, where d(n) = Sum_{k=floor(n/2)..n} binomial(2*n-k, k)*binomial(k, n-k).
a(n) = a(n-1) + (3/2)*Sum_{k=2..n} (1/(2*k-1))*binomial(2*k,k)*a(n-k).
a(n) = (2/3)*binomial(2*n,n) + (2/9)*((-2)^n/n!)*Sum_{k>=0} ( Product_{p=0..n-1} (k-2*p) /3^k).
a(n) = Sum_{k=0..n} (-1)^k*binomial(2*n-k,n).
a(n) = ( Sum_{k=0..n} (1/2)^(n-k+1)*binomial(n+k,k) )^2*(-1/2)^(n+2). (End)
From Gary W. Adamson, Nov 22 2011: (Start)
a(n) is the upper left term of M^n, M = an infinite square production matrix as follows:
  1, 3, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, ...
  ...
Also, a(n+1) is the sum of top row terms of M^n; e.g. top row of M^3 = (13, 21, 9, 3), sum = 46 = a(4), a(3) = 13. (End)
D-finite with recurrence: 2n*a(n) + (4-7n)*a(n-1) + 2*(1-2n)*a(n-2) = 0. - R. J. Mathar, Dec 17 2011 [The recurrence is proved with the Wilf-Zeilberger (WZ) method applied to Sum_{k=0..floor(n/2)} binomial(k+n, n-k)*binomial(n-k, k). - T. Amdeberhan, Jul 23 2012]
a(n) = A035317(2*n-1,n) for n > 0. - Reinhard Zumkeller, Jul 19 2012
a(n) ~ 2^(2*n+1) / (3*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 12 2014
a(n) = binomial(2*n,n)*hypergeom([1, -n], [-2*n], -1). - Peter Luschny, May 22 2014
G.f. is the derivative of the logarithm of the g.f. for A120588. - Michael Somos, May 18 2015
a(n) = [x^n] 1/((1 - x^2)*(1 - x)^n). - Ilya Gutkovskiy, Oct 25 2017
From Peter Bala, Feb 25 2019: (Start)
a(n) = Sum_{k = 0..n} binomial(2*n + 1, n + k + 1)*(-2)^k.
a(n-1) = (1/2)*binomial(2*n,n)*( 1 - 2*(n-1)/(n+1) + 4*(n-1)*(n-2)/((n+1)*(n+2)) - 8*(n-1)*(n-2)*(n-3)/((n+1)*(n+2)*(n+3)) + ...) = (1/2)*binomial(2*n,n)*hypergeom([1 - n, 1], [n + 1], 2). (End)
a(0)=1, a(1)=1, and a(n) = (2 - 1/n)*a(n-2) + (7/2 - 2/n)*a(n-1) for n > 1. - Reginald Robson, Nov 01 2022

A052952 a(n) = Fibonacci(n+2) - (1-(-1)^n)/2.

Original entry on oeis.org

1, 1, 3, 4, 8, 12, 21, 33, 55, 88, 144, 232, 377, 609, 987, 1596, 2584, 4180, 6765, 10945, 17711, 28656, 46368, 75024, 121393, 196417, 317811, 514228, 832040, 1346268, 2178309, 3524577, 5702887, 9227464, 14930352, 24157816, 39088169, 63245985, 102334155

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Equals row sums of triangle A173284. - Gary W. Adamson, Feb 14 2010
The Kn21 sums (see A180662 for definition) of the 'Races with Ties' triangle A035317 produce this sequence. - Johannes W. Meijer, Jul 20 2011
a(n-1), for n >= 1, gives the number of compositions of n with relative prime parts, and parts not exceeding 2. See the row sums of triangle A030528 where for even n the leading 1 is missing. - Wolfdieter Lang, Jul 27 2023

			G.f. = 1 + x + 3*x^2 + 4*x^3 + 8*x^4 + 12*x^5 + 21*x^6 + 33*x^7 + ...

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1023
K. Kuhapatanakul, On the Sums of Reciprocal Generalized Fibonacci Numbers, J. Int. Seq. 16 (2013) #13.7.1, eq (1).
Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, Journal of Integer Sequences, Vol. 15 (2012), #12.9.1.
H. Ohtsuka and S. Nakamura, On the sum of reciprocal sums of Fibonacci numbers, Fibonacci Quart. 46/47 (2008/2009), 153-159.
Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1).

Cf. A062114, A173284, A059841, A014217, A180662, A035317.
Partial sums of A008346, first differences of A129696.
Cf. also A000032, A000045, A030528.
Cf. A001595, A054450, A066983, A074331, A168309.

List([0..40], n-> Fibonacci(n+2) -(1-(-1)^n)/2); # G. C. Greubel, Jul 10 2019

a052952 n = a052952_list !! n
a052952_list = 1 : 1 : zipWith (+)
   a059841_list (zipWith (+) a052952_list $ tail a052952_list)
-- Reinhard Zumkeller, Jan 06 2012

[Fibonacci(n+2)-(1-(-1)^n)/2: n in [0..40]]; // Vincenzo Librandi, Dec 02 2016

A052952 :=proc(n)
    option remember;
    local t1;
    if n <= 1 then
        return 1 ;
    fi:
    if n mod 2 = 1 then
        t1:=0
    else
        t1:=1;
    fi:
    procname(n-1)+procname(n-2)+t1;
end proc;
seq(A052952(n), n=0..40) ; # N. J. A. Sloane, May 25 2008

Table[Fibonacci[n+2] -(1-(-1)^n)/2, {n, 0, 40}] (* Vincenzo Librandi, Dec 02 2016 *)
Sum[(-1)^k*Fibonacci[Range[2,41], 1-k], {k,0,1}] (* G. C. Greubel, Oct 21 2019 *)
CoefficientList[Series[1/((1-x-x^2)*(1-x^2)),{x,0,40}],x] (* Harvey P. Dale, Sep 12 2020 *)

PARI
```
{a(n) = fibonacci(n+2) - n%2};
```

[fibonacci(n+2) -(1-(-1)^n)/2 for n in (0..40)] # G. C. Greubel, Jul 10 2019

G.f.: 1/((1-x-x^2)*(1-x^2)).
a(n) = A074331(n+1).
a(n) = A054450(n+1, 1) (second column of triangle).
a(n) = 2*a(n-2) + a(n-3) + 1, with a(0)=1, a(1)=1, a(2)=3.
a(n) = Sum_{alpha=RootOf(-1+z+z^2)} (3+alpha)*alpha^(-1-n)/3 - Sum_{beta=RootOf(-1+z^2)} beta^(-1-n)/2.
a(2*k) = Sum_{j=0..k} F(2*j+1) = F(2*(k+1)) for k >= 0; a(2*k-1) = Sum_{j=0..k} F(2*j) = F(2*k+1)-1 for k >= 1 (F = A000045, Fibonacci numbers).
a(n) = a(n-1) + a(n-2) + (1+(-1)^n)/2.
a(n) = Sum_{k=0..floor(n/2)} binomial(n-k+1, k). - Paul Barry, Oct 23 2004
a(n) = floor(phi^(n+2) / sqrt(5)), where phi is the golden ratio: phi = (1+sqrt(5))/2. - Reinhard Zumkeller, Apr 19 2005
a(n) = Fibonacci(n+1) + a(n-2) with n>1, a(0)=a(1)=1. - Zerinvary Lajos, Mar 17 2008
a(n) = floor(Fibonacci(n+3)^2/Fibonacci(n+4)). - Gary Detlefs, Nov 29 2010
a(n) = (A001595(n+3) - A066983(n+4))/2. - Gary Detlefs, Dec 19 2010
a(4*n) = F(4*n+2); a(4*n+1) = F(4*n+3) - 1; a(4*n+2) = F(4*n+4); a(4*n+3) = F(4*n+5) - 1. - Johannes W. Meijer, Jul 20 2011
a(n+1) = a(n) + a(n-1) + A059841(n+1). - Reinhard Zumkeller, Jan 06 2012
a(n) = floor(|F((1+i)*(n+2))|), n >= 0, with the complex Fibonacci function F: C -> C, z -> F(z) with F(z) := (exp(log(phi)*z) - exp(i*Pi*z)*exp(-log(phi)*z))/(2*phi-1) with the modulus |z|, the imaginary unit i and the golden section phi:=(1+sqrt(5))/2. A Conjecture: For F(z) see, e.g., the T. Koshy reference. ch. 45, p. 523, where F is called f, given in A000045. - Wolfdieter Lang, Jul 24 2012
5*a(n) = (L(n+3)-1)*(L(n+4)+3) -14 -Sum_{k=0..n} L(k+1)*L(k+5) = (L(n+3)-1)*(L(n+4)+3) -L(2*n+7) +A168309(n), where L=A000032. - J. M. Bergot, Jun 13 2014
a(n) = floor(phi*Fibonacci(n+1)), where phi is the golden section. - Michel Dekking, Dec 02 2016
a(n) = -(-1)^n * a(-4-n) for all n in Z. - Michael Somos, Dec 03 2016
a(n) = Sum_{k=0..n} Sum_{i=0..n} C(n-k-1,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n) = floor(1/(Sum_{k>=n+4} 1/Fibonacci(k))) [Ohtsuka and Nakamura]. - Michel Marcus, Aug 09 2018
a(n) = floor(abs(chebyshevU(n/2, 3/2))). - Federico Provvedi, Feb 23 2022
E.g.f.: exp(x/2)*(5*cosh(sqrt(5)*x/2) + 3*sqrt(5)*sinh(sqrt(5)*x/2))/5 - sinh(x). - Stefano Spezia, Mar 09 2024

Additional formulas and more terms from Wolfdieter Lang, May 02 2000

Better description from Olivier Gérard, Jun 05 2001

A059259 Triangle read by rows giving coefficient T(i,j) of x^i y^j in 1/(1-x-x*y-y^2) = 1/((1+y)(1-x-y)) for (i,j) = (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ...

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 2, 0, 1, 3, 4, 2, 1, 1, 4, 7, 6, 3, 0, 1, 5, 11, 13, 9, 3, 1, 1, 6, 16, 24, 22, 12, 4, 0, 1, 7, 22, 40, 46, 34, 16, 4, 1, 1, 8, 29, 62, 86, 80, 50, 20, 5, 0, 1, 9, 37, 91, 148, 166, 130, 70, 25, 5, 1, 1, 10, 46, 128, 239, 314, 296, 200

Offset: 0

N. J. A. Sloane, Jan 23 2001

This sequence provides the general solution to the recurrence a(n) = a(n-1) + k*(k+1)*a(n-2), a(0)=a(1)=1. The solution is (1, 1, k^2 + k + 1, 2*k^2 + 2*k + 1, ...) whose coefficients can be read from the rows of the triangle. The row sums of the triangle are given by the case k=1. These are the Jacobsthal numbers, A001045. Viewed as a square array, its first row is (1,0,1,0,1,...) with e.g.f. cosh(x), g.f. 1/(1-x^2) and subsequent rows are successive partial sums given by 1/((1-x)^n * (1-x^2)). - Paul Barry, Mar 17 2003
Conjecture: every second column of this triangle is identical to a column in the square array A071921. For example, column 4 of A059259 (1, 3, 9, 22, 46, ...) appears to be the same as column 3 of A071921; column 6 of A059259 (1, 4, 16, 50, 130, 296, ...) appears to be the same as column 4 of A071921; and in general column 2k of A059259 appears to be the same as column k+1 of A071921. Furthermore, since A225010 is a transposition of A071921 (ignoring the latter's top row and two leftmost columns), there appears to be a correspondence between column 2k of A059259 and row k of A225010. - Mathew Englander, May 17 2014
T(n,k) is the number of n-tilings of a (one-dimensional) board that use k (1,1)-fence tiles and n-k squares. A (1,1)-fence is a tile composed of two pieces of width 1 separated by a gap of width 1. - Michael A. Allen, Jun 25 2020
See the Edwards-Allen 2020 paper, page 14, for proof of Englander's conjecture. - Michael De Vlieger, Dec 10 2020

			Triangle begins:
  1;
  1,  0;
  1,  1,  1;
  1,  2,  2,   0;
  1,  3,  4,   2,   1;
  1,  4,  7,   6,   3,   0;
  1,  5, 11,  13,   9,   3,   1;
  1,  6, 16,  24,  22,  12,   4,   0;
  1,  7, 22,  40,  46,  34,  16,   4,  1;
  1,  8, 29,  62,  86,  80,  50,  20,  5,  0;
  1,  9, 37,  91, 148, 166, 130,  70, 25,  5, 1;
  1, 10, 46, 128, 239, 314, 296, 200, 95, 30, 6, 0;
...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Joseph Briggs, Alex Parker, Coy Schwieder, and Chris Wells, Frogs, hats and common subsequences, arXiv:2404.07285 [math.CO], 2024. See p. 28.
Kenneth Edwards and Michael A. Allen, New Combinatorial Interpretations of the Fibonacci Numbers Squared, Golden Rectangle Numbers, and Jacobsthal Numbers Using Two Types of Tile, arXiv:2009.04649 [math.CO], 2020.

See A059260 for an explicit formula.
Diagonals of this triangle are given by A006498.
Similar to the triangles A035317, A080242, A108561, A112555.
Cf. A123521, A157897.

read transforms; 1/(1-x-x*y-y^2); SERIES2(%,x,y,12); SERIES2TOLIST(%,x,y,12);

T[n_, 0]:= 1; T[n_, n_]:= (1+(-1)^n)/2; T[n_, k_]:= T[n, k] = T[n-1, k] + T[n-1, k-1]; Table[T[n, k], {n, 0, 10} , {k, 0, n}]//Flatten (* G. C. Greubel, Jan 03 2017 *)

{T(n,k) = if(k==0, 1, if(k==n, (1+(-1)^n)/2, T(n-1,k) +T(n-1,k-1)) )};
for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Apr 29 2019

def A059259_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return (-1)^n
        if k==0: return 0
        return prec(n-1,k-1)-sum(prec(n,k+i-1) for i in (2..n-k+1))
    return [(-1)^(n-k+1)*prec(n+1, k) for k in (1..n)]
for n in (1..12): print(A059259_row(n)) # Peter Luschny, Mar 16 2016

G.f.: 1/(1 - x - x*y - y^2).
As a square array read by antidiagonals, this is T(n, k) = Sum_{i=0..n} (-1)^(n-i)*C(i+k, k). - Paul Barry, Jul 01 2003
T(2*n,n) = A026641(n). - Philippe Deléham, Mar 08 2007
T(n,k) = T(n-1,k) + T(n-2,k-1) + T(n-2,k-2), T(0,0) = T(1,0) = T(2,0) = T(2,1) = T(2,2)=1, T(1,1)=0, T(n,k)=0 if k < 0 or if k > n. - Philippe Deléham, Nov 24 2013
T(n,0) = 1, T(n,n) = (1+(-1)^n)/2, and T(n,k) = T(n-1,k) + T(n-1,k-1) for 0 < k < n. - Mathew Englander, May 24 2014
From Michael A. Allen, Jun 25 2020: (Start)
T(n,k) + T(n-1,k-1) = binomial(n,k) if n >= k > 0.
T(2*n-1,2*n-2) = T(2*n,2*n-1) = n, T(2*n,2*n-2) = n^2, T(2*n+1,2*n-1) = n*(n+1) for n > 0.
T(n,2) = binomial(n-2,2) + n - 1 for n > 1 and T(n,3) = binomial(n-3,3) + 2*binomial(n-2,2) for n > 2.
T(2*n-k,k) = A123521(n,k). (End)

A014301 Number of internal nodes of even outdegree in all ordered rooted trees with n edges.

Original entry on oeis.org

0, 1, 3, 11, 40, 148, 553, 2083, 7896, 30086, 115126, 442118, 1703052, 6577474, 25461493, 98759971, 383751472, 1493506534, 5820778858, 22714926826, 88745372992, 347087585824, 1358789148058, 5324148664846, 20878676356240, 81937643449468, 321786401450268

Offset: 1

Emeric Deutsch

nonn

Number of protected vertices in all ordered rooted trees with n edges. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants. - Emeric Deutsch, Aug 20 2008
1,3,11,... gives the diagonal sums of A111418. Hankel transform of a(n) is A128834. Hankel transform of a(n+1) is A187340. - Paul Barry, Mar 08 2011
a(n) = A035317(2*n-1,n-1) for n > 0. - Reinhard Zumkeller, Jul 19 2012
Apparently the number of peaks in all Dyck paths of semilength n+1 that are the same height as the preceding peak. - David Scambler, Apr 22 2013
Define an infinite triangle by T(n,0)=A001045(n) (the first column) and T(r,c) = Sum_{k=c-1..r} T(k,c-1) (the sum of all the terms in the preceding column down to row r). Then T(n,n)=a(n+1). The triangle is 0; 1,1; 1,2,3; 3,5,8,11; 5,10,18,29,40; 11,21,39,68,108,148;... Example: T(5,2)=39=the sum of the terms in column 1 from T(1,1) to T(5,1), namely, 1+2+5+10+21. - J. M. Bergot, May 17 2013
Also for n>=1 the number of unimodal functions f:[n]->[n] with f(1)<>1 and f(i)<>f(i+1). a(4) = 11: [2,3,2,1], [2,3,4,1], [2,3,4,2], [2,3,4,3], [2,4,2,1], [2,4,3,1], [2,4,3,2], [3,4,2,1], [3,4,3,1], [3,4,3,2], [4,3,2,1]. - Alois P. Heinz, May 23 2013

G. C. Greubel, Table of n, a(n) for n = 1..1000
Gi-Sang Cheon and Louis W. Shapiro, Protected points in ordered trees, Appl. Math. Letters, 21, 2008, 516-520.
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020, Corollary 3.4.
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
Index entries for sequences related to rooted trees

Cf. A059481, A026641, A143362, A143363.

[(1/2)*(&+[(-1)^(n-k)*Binomial(n+k-1,k): k in [0..n]]): n in [1..30]]; // G. C. Greubel, Jan 15 2018

Rest[CoefficientList[Series[(1-2*x-Sqrt[1-4*x])/(3*Sqrt[1-4*x]-1+4*x), {x, 0, 50}], x]] (* G. C. Greubel, Jan 15 2018 *)

x='x+O('x^30); Vec((1-2*x-sqrt(1-4*x))/(3*sqrt(1-4*x)-1+4*x)) \\ G. C. Greubel, Jan 15 2018

from itertools import count, islice
def A014301_gen(): # generator of terms
    yield from (0,1)
    a, b, c = 0, 3, 1
    for n in count(1):
        yield ((b:=b*((n<<1)+3<<1)//(n+2))-(a:=(c:=c*((n<<2)+2)//(n+2))-a>>1))//3
A014301_list = list(islice(A014301_gen(),20)) # Chai Wah Wu, Apr 27 2023

a(n) = binomial(2*n-1, n)/3 - A000957(n)/3;
a(n) = (1/2)*Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - Vladeta Jovovic, Aug 28 2002
From Emeric Deutsch, Jan 26 2004: (Start)
G.f.: (1-2*z-sqrt(1-4*z))/(3*sqrt(1-4*z)-1+4*z).
a(n) = [A026641(n) - A026641(n-1)]/3 for n>1. (End)
a(n) = (1/2)*Sum_{j=0..floor(n/2)} binomial(2n-2j-2, n-2).
a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n+k,k-1). - Paul Barry, Jul 18 2006
D-finite with recurrence: 2*n*a(n) +(-9*n+8)*a(n-1) +(3*n-16)*a(n-2) +2*(2*n-5)*a(n-3)=0. - R. J. Mathar, Dec 03 2012

A108561 Triangle read by rows: T(n,0)=1, T(n,n)=(-1)^n, T(n+1,k)=T(n,k-1)+T(n,k) for 0 < k < n.

Original entry on oeis.org

1, 1, -1, 1, 0, 1, 1, 1, 1, -1, 1, 2, 2, 0, 1, 1, 3, 4, 2, 1, -1, 1, 4, 7, 6, 3, 0, 1, 1, 5, 11, 13, 9, 3, 1, -1, 1, 6, 16, 24, 22, 12, 4, 0, 1, 1, 7, 22, 40, 46, 34, 16, 4, 1, -1, 1, 8, 29, 62, 86, 80, 50, 20, 5, 0, 1, 1, 9, 37, 91, 148, 166, 130, 70, 25, 5, 1, -1, 1, 10, 46, 128, 239, 314, 296, 200, 95, 30, 6, 0, 1, 1, 11, 56, 174, 367

Offset: 0

Reinhard Zumkeller, Jun 10 2005

Sum_{k=0..n} T(n,k) = A078008(n);
Sum_{k=0..n} abs(T(n,k)) = A052953(n-1) for n > 0;
T(n,1) = n - 2 for n > 1;
T(n,2) = A000124(n-3) for n > 2;
T(n,3) = A003600(n-4) for n > 4;
T(n,n-6) = A001753(n-6) for n > 6;
T(n,n-5) = A001752(n-5) for n > 5;
T(n,n-4) = A002623(n-4) for n > 4;
T(n,n-3) = A002620(n-1) for n > 3;
T(n,n-2) = A008619(n-2) for n > 2;
T(n,n-1) = n mod 2 for n > 0;
T(2*n,n) = A072547(n+1).
Sum_{k=0..n} T(n,k)*x^k = A232015(n), A078008(n), A000012(n), A040000(n), A001045(n+2), A140725(n+1) for x = 2, 1, 0, -1, -2, -3 respectively. - Philippe Deléham, Nov 17 2013, Nov 19 2013
(1,a^n) Pascal triangle with a = -1. - Philippe Deléham, Dec 27 2013
T(n,k) = A112465(n,n-k). - Reinhard Zumkeller, Jan 03 2014

			From _Philippe Deléham_, Nov 17 2013: (Start)
Triangle begins:
  1;
  1, -1;
  1,  0,  1;
  1,  1,  1, -1;
  1,  2,  2,  0,  1;
  1,  3,  4,  2,  1, -1;
  1,  4,  7,  6,  3,  0,  1; (End)

Reinhard Zumkeller, Rows n = 0..125 of triangle, flattened
C. Merino, S. D. Noble, M. Ramirez-Ibanez, R. Villarroel-Flores, On the structure of the h-vector of a paving matroid, Eur. J. Comb. 33, No. 8, 1787-1799 (2012).
Index entries for triangles and arrays related to Pascal's triangle

Cf. A007318 (a=1), A008949(a=2), A164844(a=10).
Similar to the triangles A035317, A059259, A080242, A112555.
Cf. A228196
Cf. A072547 (central terms).

Flat(List([0..13],n->List([0..n],k->Sum([0..k],i->Binomial(n,i)*(-2)^(k-i))))); # Muniru A Asiru, Feb 19 2018

a108561 n k = a108561_tabl !! n !! k
a108561_row n = a108561_tabl !! n
a108561_tabl = map reverse a112465_tabl
-- Reinhard Zumkeller, Jan 03 2014

A108561 := (n, k) -> add(binomial(n, i)*(-2)^(k-i), i = 0..k):
seq(seq(A108561(n,k), k = 0..n), n = 0..12); # Peter Bala, Feb 18 2018

Clear[t]; t[n_, 0] = 1; t[n_, n_] := t[n, n] = (-1)^Mod[n, 2]; t[n_, k_] := t[n, k] = t[n-1, k] + t[n-1, k-1]; Table[t[n, k], {n, 0, 13}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 06 2013 *)

def A108561_row(n):
    @cached_function
    def prec(n, k):
        if k==n: return 1
        if k==0: return 0
        return -prec(n-1,k-1)-sum(prec(n,k+i-1) for i in (2..n-k+1))
    return [(-1)^k*prec(n, k) for k in (1..n-1)]+[(-1)^(n+1)]
for n in (1..12): print(A108561_row(n)) # Peter Luschny, Mar 16 2016

G.f.: (1-y*x)/(1-x-(y+y^2)*x). - Philippe Deléham, Nov 17 2013
T(n,k) = T(n-1,k) + T(n-2,k-1) + T(n-2,k-2), T(0,0)=T(1,0)=1, T(1,1)=-1, T(n,k)=0 if k < 0 or if k > n. - Philippe Deléham, Nov 17 2013
From Peter Bala, Feb 18 2018: (Start)
T(n,k) = Sum_{i = 0..k} binomial(n,i)*(-2)^(k-i), 0 <= k <= n.
The n-th row polynomial is the n-th degree Taylor polynomial of the rational function (1 + x)^n/(1 + 2*x) about 0. For example, for n = 4, (1 + x)^4/(1 + 2*x) = 1 + 2*x + 2*x^2 + x^4 + O(x^5). (End)

Definition corrected by Philippe Deléham, Dec 26 2013

A055203 Number of different relations between n intervals on a line.

Original entry on oeis.org

1, 1, 13, 409, 23917, 2244361, 308682013, 58514835289, 14623910308237, 4659168491711401, 1843200116875263613, 886470355671907534969, 509366445167037318008557, 344630301458257894126724041, 271188703889907190388528763613, 245570692377888837925941696215449

Offset: 0

Sylviane R. Schwer (schwer(AT)lipn.univ-paris13.fr), Jun 22 2000

From Peter Bala, Jan 30 2018: (Start)
Number of alignments of n strings of length 2 (see Slowinski).
Conjectures: a(n) == 1 (mod 12); for fixed k, the sequence a(n) (mod k) eventually becomes periodic with exact period a divisor of phi(k), where phi(k) is Euler's totient function A000010. (End)

			In case n = 2 this is the Delannoy number a(2) = D(2,2) = 13.
a(2) = 13 because if you have two intervals [a1,a2] and [b1,b2], using a for a1 or a2 and b for b1 or b2 and writing c if an a is at the same place as a b, we get the following possibilities: aabb, acb, abab, cab, abc, baab, abba, cc, bac, cba, baba, bca, bbaa.

S. R. Schwer, Dépendances temporelles: les mots pour le dire, Journées Intelligence Artificielle, 1998.
S. R. Schwer, Enumerating and generating Allen's algebra, in preparation.

T. D. Noe, Table of n, a(n) for n = 0..100
Tim Fernando and Carl Vogel, Prior Probabilities of Allen Interval Relations over Finite Orders, 11th International Conference on Agents and Artificial Intelligence (NLPinAI 2019) Prague.
IBM Ponder This, Jan 01 2001
J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522
Peter Stockman, Upper Bounds on the Time Complexity of Temporal CSPs, Linköping University | Department of Computer science, Master's thesis, 30 ECTS | Datateknik 2016 | LIU-IDA/LITH-EX-A--16/022--SE.
David Adam Woods, Strings for Temporal Annotation and Semantic Representation of Events, Ph. D. Dissertation, Univ. of Dublin, Trinity College (Ireland, 2022).

Cf. A035317, A055809, A055810, A078739, A122193, A062208.

Row n=2 of A262809.

lambda := proc(p,n) option remember; if n = 1 then if p = 2 then RETURN(1) else RETURN(0) fi; else RETURN((p*(p-1)/2)*(lambda(p,n-1)+2*lambda(p-1,n-1)+lambda(p-2,n-1))) fi; end; A055203 := n->add(lambda(i,n),i=2..2*n);
A055203 := proc(n) local k; add(A078739(n,k)*k!,k=0..2*n)/2^n end:
seq(A055203(n),n=0..15); # Peter Luschny, Mar 25 2011
# second Maple program:
b:= proc(n) option remember; `if`(n=0, 1,
      add(b(n-j)*binomial(n, j), j=1..n))
    end:
a:= n-> ceil(add(b(n+k)*binomial(n, k), k=0..n)/2^(n+1)):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 10 2018

a[n_] := Sum[((m-1)*m)^n / 2^(m+n+1), {m, 0, Infinity}]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Oct 10 2011, after Vladeta Jovovic *)
With[{r = 2}, Flatten[{1, Table[Sum[Sum[(-1)^i*Binomial[j, i]*Binomial[j - i, r]^k, {i, 0, j}], {j, 0, k*r}], {k, 1, 15}]}]] (* Vaclav Kotesovec, Mar 22 2016 *)

a(n) = Sum_{i=2..2n} lambda(i, n), with lambda(p, 1) = 1 if p = 2, otherwise 0; lambda(p, n) = (p*(p-1)/2)*(lambda(p, n-1) + 2*lambda(p-1, n-1) + lambda(p-2, n-1)).
lambda(p, n) = Sum_k[( - 1)^(p + k) * C(p, k) * ((k - 1)*k/2)^n]. So if T(m, 0), T(m, 1), ..., T(m, m) is any row of A035317 with m >= 2n - 1 then a(n) = Sum_j[(-1)^j * T(m, j) * ((m - j + 1)*(m - j)/2)^n]; e.g., a(2) = 13 = 1*6^2 - 3*3^2 + 4*1^2 - 2*0^2 = 1*10^2 - 4*6^2 + 7*3^2 - 6*1^2 + 3*0^2 = 1*15^2 - 5*10^2 + 11*6^2 - 13*3^2 + 9*1^2 - 3*0^2 etc. while a(3) = 409 = 1*15^3 - 5*10^3 + 11*6^3 - 13*3^3 + 9*1^3 - 3*0^3 etc. - Henry Bottomley, Jan 03 2001
Row sums of A122193. - Vladeta Jovovic, Aug 24 2006
a(n) = Sum_{k=0..n} k!*Stirling2(n,k)*A121251(k). - Vladeta Jovovic, Aug 25 2006
E.g.f.: Sum_{m>=0} exp(x*binomial(m,2))/2^(m+1). - Vladeta Jovovic, Sep 24 2006
a(n) = Sum_{m>=0} binomial(m,2)^n/2^(m+1). - Vladeta Jovovic, Aug 17 2006
a(n) = (1/2^n)*Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A000670(n+k). - Vladeta Jovovic, Aug 17 2006
a(n) ~ n! * n^n * 2^(n-1) / (exp(n) * (log(2))^(2*n+1)). - Vaclav Kotesovec, Mar 15 2014
From Peter Bala, Jan 30 2018: (Start)
a(n) = Sum_{k = 2..2*n} Sum_{i = 0..k} (-1)^(k-i)*binomial(k,i)*(i*(i-1)/2)^n.
a(n) = (1/2^(n+1))*Sum_{k = 0..n} binomial(n,k)*A000670(n+k) for n >= 1. (End)

More terms from Larry Reeves (larryr(AT)acm.org), Oct 04 2000

More terms from N. J. A. Sloane, Jan 03 2001

A129696 Antidiagonal sums of triangular array T defined in A014430: T(j,k) = binomial(j+1, k) - 1 for 1 <= k <= j.

Original entry on oeis.org

1, 2, 5, 9, 17, 29, 50, 83, 138, 226, 370, 602, 979, 1588, 2575, 4171, 6755, 10935, 17700, 28645, 46356, 75012, 121380, 196404, 317797, 514214, 832025, 1346253, 2178293, 3524561, 5702870, 9227447, 14930334, 24157798, 39088150, 63245966

Offset: 1

Paul Curtz, Jun 01 2007

If T is construed as a lower triangular matrix M over the rational field, the inverse M^-1 is a lower triangular matrix containing fractions. Its row sums are the Bernoulli numbers. First column of M^-1 is 1, -1, 2/3, -1/4, -1/30, 1/12, 1/42, -1/12, ... . Multiplied by j! this gives 1, -2, 4, -6, -4, 60, 120, -3660, ... .
The Kn22 sums, see A180662 for the definition of these sums, of the 'Races with Ties' triangle A035317 lead to this sequence. - Johannes W. Meijer, Jul 20 2011
This sequence is the convolution of (1,1,2,3,5,8,13,21,...) and (1,1,2,2,3,3,4,4,5,5,...), i.e., the Fibonacci numbers (A000045) and A008619. - Clark Kimberling, May 28 2012
a(n) is the sum of the first summands over all Arndt compositions of n (see the Checa link). - Daniel Checa, Jan 01 2024

Paul Curtz, Intégration numérique des systèmes différentiels à conditions initiales. Note no. 12 du Centre de Calcul Scientifique de l'Armement, 1969.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Daniel F. Checa, Arndt Compositions: Connections with Fibonacci Numbers, Statistics, and Generalizations, 2023, p. 31.
Larry Ericksen, Problem 7, Problem Section, The Fibonacci Quarterly, Vol. 57, No. 5 (2019), pp. 172, 175-183.
Index entries for linear recurrences with constant coefficients, signature (2,1,-3,0,1).

Cf. A000045, A000071, A001924, A008619, A014430, A027641, A035317, A052952 (first differences), A180662.

Cf. A000120, A002487.

m:=36; M:=ZeroMatrix(IntegerRing(), m, m); for j:=1 to m do for k:=1 to j do M[j, k]:=Binomial(j+1, k)-1; end for; end for; [ &+[ M[j-k+1, k]: k in [1..(j+1) div 2] ]: j in [1..m] ]; // Klaus Brockhaus, Jun 11 2007

[Fibonacci(n+3)-2-Floor(n/2): n in [1..40]]; // Vincenzo Librandi, Nov 23 2014

with(combinat): a := proc (n) options operator, arrow: fibonacci(n+3)-2-floor((1/2)*n) end proc: seq(a(n), n = 1 .. 34); # Emeric Deutsch, Nov 22 2014

a[n_]:= a[n]= If[n<3, n, a[n-1] + a[n-2] + (n + Mod[n, 2])/2];
Table[a[n], {n,40}] (* Jean-François Alcover, Mar 04 2013 *)
Table[Fibonacci[n+3] -2 -Floor[n/2], {n, 100}] (* Vincenzo Librandi, Nov 23 2014 *)

prpr = 1
prev = 2
for n in range(2,100):
    print(prpr, end=", ")
    curr = prpr+prev + 1 + n//2
    prpr = prev
    prev = curr
# Alex Ratushnyak, Jul 30 2012

[fibonacci(n+3) -2 -(n//2) for n in range(1,41)] # G. C. Greubel, Mar 17 2023

From Paul Barry, Jan 18 2009: (Start)
a(n) = Sum_{k=0..floor(n/2)} A000071(n-2*k+3).
a(n) = Sum_{k=0..floor(n/2)} (Sum_{j=0..n-2*k} Fibonacci(j+1)). (End)
a(n+1) = a(n-1) + a(n) + 1 + floor(n/2) for n>1, a(0)=1, a(1)=2. - Alex Ratushnyak, Jul 30 2012
From R. J. Mathar, Jul 25 2013: (Start)
G.f.: x/((1 + x)*(1 - x)^2*(1 - x - x^2)).
a(n) + a(n+1) = A001924(n+1). (End)
a(n) = Fibonacci(n+3) - 2 - floor(n/2). - Emeric Deutsch, Nov 22 2014
a(n) = (-5/4 - (-1)^n/4 + (2^(-n)*((1 - t)^n*(-2 + t) + (1 + t)^n*(2 + t)))/t + (-1 - n)/2), where t=sqrt(5). - Colin Barker, Feb 09 2017
E.g.f.: (4*exp(x/2)*(5*cosh(sqrt(5)*x/2) + 2*sqrt(5)*sinh(sqrt(5)*x/2)) - 5*(4 + x)*cosh(x) - 5*(3 + x)*sinh(x))/10. - Stefano Spezia, Apr 06 2024
a(n) = max_{k = 2^(n+1)..2^(n+2)-1} (A002487(k) - A000120(k)) (Ericksen, 2019). - Amiram Eldar, Jan 30 2025

Edited and extended by Klaus Brockhaus, Jun 11 2007

A181971 Triangle read by rows: T(n,0) = 1, T(n,n) = floor((n+3)/2) and T(n,k) = T(n-1,k-1) + T(n-1,k), 0 < k < n.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 1, 4, 5, 3, 1, 5, 9, 8, 3, 1, 6, 14, 17, 11, 4, 1, 7, 20, 31, 28, 15, 4, 1, 8, 27, 51, 59, 43, 19, 5, 1, 9, 35, 78, 110, 102, 62, 24, 5, 1, 10, 44, 113, 188, 212, 164, 86, 29, 6, 1, 11, 54, 157, 301, 400, 376, 250, 115, 35, 6, 1, 12, 65, 211, 458, 701, 776, 626, 365, 150, 41, 7

Offset: 0

Reinhard Zumkeller, Jul 09 2012

Another variant of Pascal's triangle;
row sums: A081254; central terms: T(2*n,n) = A128082(n+1);
T(n,0) = 1;
T(n,1) = n + 1 for n > 0;
T(n,2) = A000096(n-1) for n > 1;
T(n,3) = A105163(n-2) for n > 2;
T(n,n-2) = A005744(n-1) for n > 1;
T(n,n-1) = A024206(n) for n > 0;
T(n,n) = A008619(n+1).

			The triangle begins:
.  0:                              1
.  1:                           1     2
.  2:                        1     3     2
.  3:                     1     4     5     3
.  4:                  1     5     9     8     3
.  5:               1     6    14    17    11     4
.  6:            1     7    20    31    28    15     4
.  7:         1     8    27    51    59    43    19     5
.  8:      1     9    35    78   110   102    62    24     5
.  9:   1    10    44   113   188   212   164    86    29     6.

Reinhard Zumkeller, Rows n=0..150 of triangle, flattened
Index entries for triangles and arrays related to Pascal's triangle

Cf. A035317, A007318, A074909.

a181971 n k = a181971_tabl !! n !! k
a181971_row n = a181971_tabl !! n
a181971_tabl = map snd $ iterate f (1, [1]) where
   f (i, row) = (1 - i, zipWith (+) ([0] ++ row) (row ++ [i]))

T[n_ /; n >= 0, k_ /; k >= 0] := T[n, k] = If[n == k, Quotient[n + 3, 2], If[k == 0, 1, If[n > k, T[n - 1, k - 1] + T[n - 1, k]]]];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 12 2021 *)

{T(n,k)=if(n==k,(n+3)\2,if(k==0,1,if(n>k,T(n-1,k-1)+T(n-1,k))))}
for(n=0,12,for(k=0,n,print1(T(n,k),","));print("")) \\ Paul D. Hanna, Jul 18 2012

Showing 1-10 of 23 results. Next

cp's OEIS Frontend

A080239 Antidiagonal sums of triangle A035317.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

A001654 Golden rectangle numbers: F(n) * F(n+1), where F(n) = A000045(n) (Fibonacci numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Python

Formula

Extensions

A026641 Number of nodes of even outdegree (including leaves) in all ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

A052952 a(n) = Fibonacci(n+2) - (1-(-1)^n)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A059259 Triangle read by rows giving coefficient T(i,j) of x^i y^j in 1/(1-x-x*y-y^2) = 1/((1+y)(1-x-y)) for (i,j) = (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs