A129696 -id:A129696 - cp's OEIS frontend

A192744 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

1, 1, 3, 8, 29, 133, 762, 5215, 41257, 369032, 3676209, 40333241, 483094250, 6271446691, 87705811341, 1314473334832, 21017294666173, 357096406209005, 6424799978507178, 122024623087820183, 2439706330834135361, 51219771117454755544

Offset: 0

Clark Kimberling, Jul 09 2011

nonn

The titular polynomial is defined recursively by p(n,x)=x*p(n-1,x)+n! for n>0, where p(0,x)=1; see the Example.  For an introduction to polynomial reduction, see A192232.  The discussion at A192232 Comments continues here:
...
Let R(p,q,s) denote the "reduction of polynomial p by q->s" as defined at A192232.  Suppose that q(x)=x^k for some k>0 and that s(x)=s(k,0)*x^(k-1)+s(k,1)*x^(k-2)+...+s(k,k-2)x+s(k,k-1).
...
First, we shall take p(x)=x^n, where n>=0; the results will be used to formulate R(p,q,s) for general p.  Represent R(x^n,q,s) by
...
R(x^n)=s(n,0)*x^(k-1)+s(n,1)*x^(k-2)+...+s(n,k-2)*x+s(n,k-1).
...
Then each of the sequences u(n)=s(n,h), for h=0,1,...,k-1, satisfies this linear recurrence relation:
...
u(n)=s(k,0)*u(n-1)+s(k,1)*u(n-2)+...+s(k,k-2)*u(n-k-1)+s(k,k-1)*u(n-k), with initial values tabulated here:
...
n: ..s(n,0)...s(n,1)..s(n,2).......s(n,k-2)..s(n,k-1)
0: ....0........0.......0..............0.......1
1: ....0........0.......0..............1.......0
...
k-2: ..0........1.......0..............0.......0
k-1: ..0........0.......0..............0.......0
k: ..s(k,0)...s(k,1)..s(k,2).......s(k,k-2)..s(k,k-1)
...
That completes the formulation for p(x)=x^n.  Turning to the general case, suppose that
...
p(n,x)=p(n,0)*x^n+p(n,1)*x^(n-1)+...+p(n,n-1)*x+p(n,n)
...
is a polynomial of degree n>=0.  Then the reduction denoted by (R(p(n,x) by x^k -> s(x)) is the polynomial of degree k-1 given by the matrix product P*S*X, where P=(p(n,0)...p(n,1).........p(n-k)...p(n,n-k+1); X has all 0's except for main diagonal (x^(k-1), x^(k-2)...x,1); and S has
...
row 1: ... s(n,0) ... s(n,1) ...... s(n,k-2) . s(n,k-1)
row 2: ... s(n-1,0) . s(n-1,1) .... s(n-1,k-2) s(n-1,k-1)
...
row n-k+1: s(k,0).... s(k,1) ...... s(k,k-2) ..s(k,k-1)
row n-k+2: p(n,n-k+1) p(n,n-k+2) .. p(n,n-1) ..p(n,n)
*****
As a class of examples, suppose that (v(n)), for n>=0, is a sequence, that p(0,x)=1, and p(n,x)=v(n)+p(n-1,x) for n>0.  If q(x)=x^2 and s(x)=x+1, and we write the reduction R(p(n,x)) as u1(n)*x+u2(n), then the sequences u1 and u2 are convolutions with the Fibonacci sequence, viz., let F=(0,1,1,2,3,5,8,...)=A000045 and let G=(1,0,1,1,2,3,5,8...); then u1=G**v and u2=F**v, where ** denotes convolution.  Examples (with a few exceptions for initial terms):
...
If v(n)=n! then u1=A192744, u2=A192745.
If v(n)=n+1 then u1=A000071, u2=A001924.
If v(n)=2n then u1=A014739, u2=A027181.
If v(n)=2n+1 then u1=A001911, u2=A001891.
If v(n)=3n+1 then u1=A027961, u2=A023537.
If v(n)=3n+2 then u1=A192746, u2=A192747.
If v(n)=3n then u1=A154691, u2=A192748.
If v(n)=4n+1 then u1=A053311, u2=A192749.
If v(n)=4n+2 then u1=A192750, u2=A192751.
If v(n)=4n+3 then u1=A192752, u2=A192753.
If v(n)=4n then u1=A147728, u2=A023654.
If v(n)=5n+1 then u1=A192754, u2=A192755.
If v(n)=5n then u1=A166863, u2=A192756.
If v(n)=floor((n+1)tau) then u1=A192457, u2=A023611.
If v(n)=floor((n+2)/2) then u1=A052952, u2=A129696.
If v(n)=floor((n+3)/3) then u1=A004695, u2=A178982.
If v(n)=floor((n+4)/4) then u1=A080239, u2=A192758.
If v(n)=floor((n+5)/5) then u1=A124502, u2=A192759.
If v(n)=n+2 then u1=A001594, u2=A192760.
If v(n)=n+3 then u1=A022318, u2=A192761.
If v(n)=n+4 then u1=A022319, u2=A192762.
If v(n)=2^n then u1=A027934, u2=A008766.
If v(n)=3^n then u1=A106517, u2=A094688.

			The first five polynomials and their reductions:
1 -> 1
1+x -> 1+x
2+x+x^2 -> 3+2x
6+2x+x^2+x^3 -> 8+5x
24+6x+2x^2+x^3+x^4 -> 29+13x, so that
A192744=(1,1,3,8,29,...) and A192745=(0,1,2,5,13,...).

Cf. A192232.

A192744p := proc(n,x)
    option remember;
    if n = 0 then
        1;
    else
        x*procname(n-1,x)+n! ;
        expand(%) ;
    end if;
end proc:
A192744 := proc(n)
    local p;
    p := A192744p(n,x) ;
    while degree(p,x) > 1 do
        p := algsubs(x^2=x+1,p) ;
        p := expand(p) ;
    end do:
    coeftayl(p,x=0,0) ;
end proc: # R. J. Mathar, Dec 16 2015

q = x^2; s = x + 1; z = 40;
p[0, n_] := 1; p[n_, x_] := x*p[n - 1, x] + n!;
Table[Expand[p[n, x]], {n, 0, 7}]
reduce[{p1_, q_, s_, x_}] :=
FixedPoint[(s PolynomialQuotient @@ #1 +
       PolynomialRemainder @@ #1 &)[{#1, q, x}] &, p1]
t = Table[reduce[{p[n, x], q, s, x}], {n, 0, z}];
u1 = Table[Coefficient[Part[t, n], x, 0], {n, 1, z}]
  (* A192744 *)
u2 = Table[Coefficient[Part[t, n], x, 1], {n, 1, z}]
  (* A192745 *)

G.f.: (1-x)/(1-x-x^2)/Q(0), where Q(k)= 1 - x*(k+1)/(1 - x*(k+1)/Q(k+1)); (continued fraction). - Sergei N. Gladkovskii, May 20 2013
Conjecture: a(n) +(-n-2)*a(n-1) +2*(n-1)*a(n-2) +3*a(n-3) +(-n+2)*a(n-4)=0. - R. J. Mathar, May 04 2014
Conjecture: (-n+2)*a(n) +(n^2-n-1)*a(n-1) +(-n^2+3*n-3)*a(n-2) -(n-1)^2*a(n-3)
=0. - R. J. Mathar, Dec 16 2015

A001924 Apply partial sum operator twice to Fibonacci numbers.

Original entry on oeis.org

0, 1, 3, 7, 14, 26, 46, 79, 133, 221, 364, 596, 972, 1581, 2567, 4163, 6746, 10926, 17690, 28635, 46345, 75001, 121368, 196392, 317784, 514201, 832011, 1346239, 2178278, 3524546, 5702854, 9227431, 14930317, 24157781, 39088132, 63245948, 102334116, 165580101

Offset: 0

N. J. A. Sloane

Leading coefficients in certain rook polynomials (for n>=2; see p. 18 of the Riordan paper). - Emeric Deutsch, Mar 08 2004
(1, 3, 7, 14, ...) = row sums of triangle A141289. - Gary W. Adamson, Jun 22 2008
a(n) is the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is at most 2. See example below. Generally, the o.g.f. for the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is <= k is: x/((1-x)*(1-2*x+x^(k+1))). Cf. A000217 the case for k=1, A001477 the case for k=0 (counts singleton subsets). - Geoffrey Critzer, Feb 17 2012
-Fibonacci(n-2) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Dec 31 2012
a(n) is the number of bit strings of length n+1 with the pattern 00 and without the pattern 011, see example. - John M. Campbell, Feb 10 2013
From Jianing Song, Apr 28 2025: (Start)
For n >= 2, a(n-2) is the number of subsets of {1,2,...,n} with 2 or more elements that contain no consecutive elements (i.e., such that the difference of successive elements is at least 2). Note that the number of such subsets with k elements is binomial(n+1-k,k), and Sum_{k=2..floor((n+1)/2)} binomial(n+1-k,k) = F(n+2) - binomial(n+1,0) - binomial(n,1) = F(n+2) - (n+1).
If subsets of {1,2,...,n} are required to contain no consecutive elements module n, then the result is A023548(n-3). (End)

			a(5) = 26 because there are 31 nonempty subsets of {1,2,3,4,5} but 5 of these have successive elements that differ by 3 or more: {1,4}, {1,5}, {2,5}, {1,2,5}, {1,4,5}. - _Geoffrey Critzer_, Feb 17 2012
From _John M. Campbell_, Feb 10 2013: (Start)
There are a(5) = 26 bit strings with the pattern 00 and without the pattern 011 of length 5+1:
   000000, 000001, 000010, 000100, 000101, 001000,
   001001, 001010, 010000, 010001, 010010, 010100,
   100000, 100001, 100010, 100100, 100101, 101000, 101001,
   110000, 110001, 110010, 110100, 111000, 111001, 111100.
(End)

J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.
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).

T. D. Noe, Table of n, a(n) for n = 0..500
Bader AlBdaiwi, On the Number of Cycles in a Graph, arXiv preprint arXiv:1603.01807 [cs.DM], 2016.
Jean-Luc Baril and Jean-Marcel Pallo, Motzkin subposet and Motzkin geodesics in Tamari lattices, 2013.
Ning-Ning Cao and Feng-Zhen Zhao, Some Properties of Hyperfibonacci and Hyperlucas Numbers, J. Int. Seq. 13 (2010) # 10.8.8.
Hung Viet Chu, Various Sequences from Counting Subsets, arXiv:2005.10081 [math.CO], 2020.
Hung Viet Chu, Partial Sums of the Fibonacci Sequence, arXiv:2106.03659 [math.CO], 2021.
Ligia Loretta Cristea, Ivica Martinjak, and Igor Urbiha, Hyperfibonacci Sequences and Polytopic Numbers, arXiv:1606.06228 [math.CO], 2016.
Emrah Kiliç and Pantelimon Stănică, Generating matrices for weighted sums of second order linear recurrences, JIS 12 (2009) 09.2.7.
Wolfdieter Lang, Problem B-858, Fibonacci Quarterly, 36 (1998), 373-374, Solution, ibid. 37 (1999) 183-184.
Candice A. Marshall, Construction of Pseudo-Involutions in the Riordan Group, Dissertation, Morgan State University, 2017.
Igor Pak, Boris Shapiro, Ilya Smirnov, and Ken-ichi Yoshida, Hilbert-Kunz multiplicity of quadrics via the Ehrhart theory, Stockholm Univ. (Sweden, 2025). See p. 6.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
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.
J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy]
Stacey Wagner, Enumerating Alternating Permutations with One Alternating Descent, DePaul Discoveries: Vol. 2: Iss. 1, Article 2.
Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Cf. A000045, A023548, A001891, A133640, A141289.
Right-hand column 4 of triangle A011794.
Cf. A014162, A039834, A077880, A122595, A129696.
Cf. A065220.

List([0..40], n-> Fibonacci(n+4) -n-3); # G. C. Greubel, Jul 08 2019

a001924 n = a001924_list !! n
a001924_list = drop 3 $ zipWith (-) (tail a000045_list) [0..]
-- Reinhard Zumkeller, Nov 17 2013

[Fibonacci(n+4)-(n+3): n in [0..40]]; // Vincenzo Librandi, Jun 23 2016

A001924:=-1/(z**2+z-1)/(z-1)**2; # Conjectured by Simon Plouffe in his 1992 dissertation.
##
a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.
         <<0, 1, 3, 7>>)[1, 1]:
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 05 2012

a[n_]:= Fibonacci[n+4] -3-n; Array[a, 40, 0]  (* Robert G. Wilson v *)
LinearRecurrence[{3,-2,-1,1},{0,1,3,7},40] (* Harvey P. Dale, Jan 24 2015 *)
Nest[Accumulate,Fibonacci[Range[0,40]],2] (* Harvey P. Dale, Jun 15 2016 *)

a(n)=fibonacci(n+4)-n-3 \\ Charles R Greathouse IV, Feb 24 2011

[fibonacci(n+4) -n-3 for n in (0..40)] # G. C. Greubel, Jul 08 2019

From Wolfdieter Lang: (Start)
G.f.: x/((1-x-x^2)*(1-x)^2).
Convolution of natural numbers n >= 1 with Fibonacci numbers F(k).
a(n) = Fibonacci(n+4) - (3+n). (End)
From Henry Bottomley, Jan 03 2003: (Start)
a(n) = a(n-1) + a(n-2) + n = a(n-1) + A000071(n+2).
a(n) = A001891(n) - a(n-1) = n + A001891(n-1).
a(n) = A065220(n+4) + 1 = A000126(n+1) - 1. (End)
a(n) = Sum_{k=0..n} Sum_{i=0..k} Fibonacci(i). - Benoit Cloitre, Jan 26 2003
a(n) = (sqrt(5)/2 + 1/2)^n*(7*sqrt(5)/10 + 3/2) + (3/2 - 7*sqrt(5)/10)*(sqrt(5)/2 - 1/2)^n*(-1)^n - n - 3. - Paul Barry, Mar 26 2003
a(n) = Sum_{k=0..n} Fibonacci(k)*(n-k). - Benoit Cloitre, Jun 07 2004
A107909(a(n)) = A000225(n) = 2^n - 1. - Reinhard Zumkeller, May 28 2005
a(n) - a(n-1) = A101220(1,1,n). - Ross La Haye, May 31 2006
F(n) + a(n-3) = A133640(n). - Gary W. Adamson, Sep 19 2007
a(n) = A077880(-3-n) = 2*a(n-1) - a(n-3) + 1. - Michael Somos, Dec 31 2012
INVERT transform is A122595. PSUM transform is A014162. PSUMSIGN transform is A129696. BINOMIAL transform of A039834 with 0,1 prepended is this sequence. - Michael Somos, Dec 31 2012
a(n) = A228074(n+1,3) for n > 1. - Reinhard Zumkeller, Aug 15 2013
a(n) = Sum_{k=0..n} Sum_{i=0..n} i * C(n-k,k-i). - Wesley Ivan Hurt, Sep 21 2017
E.g.f.: exp(x/2)*(15*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x)*(3 + x). - Stefano Spezia, Jun 25 2022

Description improved by N. J. A. Sloane, Jan 01 1997

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

A035317 Pascal-like triangle associated with A000670.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane

From Johannes W. Meijer, Jul 20 2011: (Start)
The triangle sums, see A180662 for their definitions, link this "Races with Ties" triangle with several sequences, see the crossrefs. Observe that the Kn4 sums lead to the golden rectangle numbers A001654 and that the Fi1 and Fi2 sums lead to the Jacobsthal sequence A001045.
The series expansion of G(x, y) = 1/((y*x-1)*(y*x+1)*((y+1)*x-1)) as function of x leads to this sequence, see the second Maple program. (End)
T(2n,k) = the number of hatted frog arrangements with k frogs on the 2xn grid. See the linked paper "Frogs, hats and common subsequences". - Chris Cox, Apr 12 2024

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

Vincenzo Librandi, Rows n = 0..100, flattened
Joseph Briggs, Alex Parker, Coy Schwieder, and Chris Wells, Frogs, hats and common subsequences, arXiv preprint arXiv:2404.07285 [math.CO], 2024. See p. 28.
A. Hlavác, M. Marvan, Nonlocal conservation laws of the constant astigmatism equation, arXiv preprint arXiv:1602.06861 [nlin.SI], 2016.
E. Mendelson, Races with Ties, Math. Mag. 55 (1982), 170-175.
Index entries for triangles and arrays related to Pascal's triangle

Row sums are A000975, diagonal sums are A080239.
Central terms are A014300.
Similar to the triangles A059259, A080242, A108561, A112555.
Cf. A059260.
Triangle sums (see the comments): A000975 (Row1), A059841 (Row2), A080239 (Kn11), A052952 (Kn21), A129696 (Kn22), A001906 (Kn3), A001654 (Kn4), A001045 (Fi1, Fi2), A023435 (Ca2), Gi2 (A193146), A190525 (Ze2), A193147 (Ze3), A181532 (Ze4). - Johannes W. Meijer, Jul 20 2011
Cf. A181971.

a035317 n k = a035317_tabl !! n !! k
a035317_row n = a035317_tabl !! n
a035317_tabl = map snd $ iterate f (0, [1]) where
   f (i, row) = (1 - i, zipWith (+) ([0] ++ row) (row ++ [i]))
-- Reinhard Zumkeller, Jul 09 2012

A035317 := proc(n,k): add((-1)^(i+k) * binomial(i+n-k+1, i), i=0..k) end: seq(seq(A035317(n,k), k=0..n), n=0..10); # Johannes W. Meijer, Jul 20 2011
A035317 := proc(n,k): coeff(coeftayl(1/((y*x-1)*(y*x+1)*((y+1)*x-1)), x=0, n), y, k) end: seq(seq(A035317(n,k), k=0..n), n=0..10); # Johannes W. Meijer, Jul 20 2011

t[n_, k_] := (-1)^k*(((-1)^k*(n+2)!*Hypergeometric2F1[1, n+3, k+2, -1])/((k+1)!*(n-k+1)!) + 2^(k-n-2)); Flatten[ Table[ t[n, k], {n, 0, 11}, {k, 0, n}]] (* Jean-François Alcover, Dec 14 2011, after Johannes W. Meijer *)

{T(n,k)=if(n==k,(n+2)\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

def A035317_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+2, k) for k in (1..n)]
for n in (1..11): print(A035317_row(n)) # Peter Luschny, Mar 16 2016

T(n,k) = Sum_{j=0..floor(n/2)} binomial(n-2j, k-2j). - Paul Barry, Feb 11 2003
From Johannes W. Meijer, Jul 20 2011: (Start)
T(n, k) = Sum_{i=0..k}((-1)^(i+k) * binomial(i+n-k+1,i)). (Mendelson)
T(n, k) = T(n-1, k-1) + T(n-1, k) with T(n, 0) = 1 and T(n, n) = floor(n/2) + 1. (Mendelson)
Sum_{k = 0..n}((-1)^k * (n-k+1)^n * T(n, k)) = A000670(n). (Mendelson)
T(n, n-k) = A128176(n, k); T(n+k, n-k) = A158909(n, k); T(2*n-k, k) = A092879(n, k). (End)
T(2*n+1,n) = A014301(n+1); T(2*n+1,n+1) = A026641(n+1). - Reinhard Zumkeller, Jul 19 2012

More terms from James Sellers

A014473 Pascal's triangle - 1: Triangle read by rows: T(n, k) = A007318(n, k) - 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 5, 3, 0, 0, 4, 9, 9, 4, 0, 0, 5, 14, 19, 14, 5, 0, 0, 6, 20, 34, 34, 20, 6, 0, 0, 7, 27, 55, 69, 55, 27, 7, 0, 0, 8, 35, 83, 125, 125, 83, 35, 8, 0, 0, 9, 44, 119, 209, 251, 209, 119, 44, 9, 0, 0, 10, 54, 164, 329, 461, 461, 329, 164, 54, 10, 0

Offset: 0

N. J. A. Sloane

Indexed as a square array A(n,k): If X is an (n+k)-set and Y a fixed k-subset of X then A(n,k) is equal to the number of n-subsets of X intersecting Y. - Peter Luschny, Apr 20 2012

			Triangle begins:
   0;
   0, 0;
   0, 1,  0;
   0, 2,  2,  0;
   0, 3,  5,  3,  0;
   0, 4,  9,  9,  4,  0;
   0, 5, 14, 19, 14,  5, 0;
   0, 6, 20, 34, 34, 20, 6, 0;
   ...
Seen as a square array read by antidiagonals:
  [0] 0, 0,  0,  0,   0,   0,   0,    0,    0,    0,    0,     0, ... A000004
  [1] 0, 1,  2,  3,   4,   5,   6,    7,    8,    9,   10,    11, ... A001477
  [2] 0, 2,  5,  9,  14,  20,  27,   35,   44,   54,   65,    77, ... A000096
  [3] 0, 3,  9, 19,  34,  55,  83,  119,  164,  219,  285,   363, ... A062748
  [4] 0, 4, 14, 34,  69, 125, 209,  329,  494,  714, 1000,  1364, ... A063258
  [5] 0, 5, 20, 55, 125, 251, 461,  791, 1286, 2001, 3002,  4367, ... A062988
  [6] 0, 6, 27, 83, 209, 461, 923, 1715, 3002, 5004, 8007, 12375, ... A124089

Reinhard Zumkeller, Rows n=0..100 of triangle, flattened
Milan Janjic, Two Enumerative Functions

Triangle without zeros: A014430.
Related: A323211 (A007318(n, k) + 1).
A000295 (row sums), A059841 (alternating row sums), A030662(n-1) (central terms).
Columns include A000096, A062748, A062988, A063258.
Diagonals of A(n, n+d): A030662 (d=0), A010763 (d=1), A322938 (d=2).
Cf. A000004, A001477, A007318, A030662, A059841, A109128, A124089, A129696.

a014473 n k = a014473_tabl !! n !! k
a014473_row n = a014473_tabl !! n
a014473_tabl = map (map (subtract 1)) a007318_tabl
-- Reinhard Zumkeller, Apr 10 2012

[Binomial(n,k)-1: k in [0..n], n in [0..12]]; // G. C. Greubel, Apr 08 2024

with(combstruct): for n from 0 to 11 do seq(-1+count(Combination(n), size=m), m = 0 .. n) od; # Zerinvary Lajos, Apr 09 2008
# The rows of the square array:
Arow := proc(n, len) local gf, ser;
gf := (x - 1)^(-n - 1) + (-1)^(n + 1)/(x*(x - 1));
ser := series(gf, x, len+2): seq((-1)^(n+1)*coeff(ser, x, j), j=0..len) end:
for n from 0 to 9 do lprint([n], Arow(n, 12)) od; # Peter Luschny, Feb 13 2019

Table[Binomial[n,k] -1, {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 08 2024 *)

flatten([[binomial(n,k)-1 for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Apr 08 2024

G.f.: x^2*y/((1 - x)*(1 - x*y)*(1 - x*(1 + y))). - Ralf Stephan, Jan 24 2005
T(n,k) = A109128(n,k) - A007318(n,k), 0 <= k <= n. - Reinhard Zumkeller, Apr 10 2012
T(n, k) = T(n-1, k-1) + T(n-1, k) + 1, 0 < k < n with T(n, 0) = T(n, n) = 0. - Reinhard Zumkeller, Jul 18 2015
If seen as a square array read by antidiagonals the generating function of row n is: G(n) = (x - 1)^(-n - 1) + (-1)^(n + 1)/(x*(x - 1)). - Peter Luschny, Feb 13 2019
From G. C. Greubel, Apr 08 2024: (Start)
T(n, n-k) = T(n, k).
Sum_{k=0..floor(n/2)} T(n-k, k) = A129696(n-2).
Sum_{k=0..floor(n/2)} (-1)^k*T(n-k, k) = b(n-1), where b(n) is the repeating pattern {0, 0, -1, -2, -1, 1, 1, -1, -2, -1, 0, 0}_{n=0..11}, with b(n) = b(n-12). (End)

More terms from Erich Friedman

A014430 Subtract 1 from Pascal's triangle, read by rows.

Original entry on oeis.org

1, 2, 2, 3, 5, 3, 4, 9, 9, 4, 5, 14, 19, 14, 5, 6, 20, 34, 34, 20, 6, 7, 27, 55, 69, 55, 27, 7, 8, 35, 83, 125, 125, 83, 35, 8, 9, 44, 119, 209, 251, 209, 119, 44, 9, 10, 54, 164, 329, 461, 461, 329, 164, 54, 10, 11, 65, 219, 494, 791, 923, 791, 494, 219, 65, 11

Offset: 0

N. J. A. Sloane

Each value of the sequence (T(x,y)) is equal to the sum of all values in Pascal's Triangle that are in the rectangle defined by the tip (0,0) and the position (x,y). - Florian Kleedorfer (florian.kleedorfer(AT)austria.fm), May 23 2005
To clarify T(n,k) and A129696: We subtract I = Identity matrix from Pascal's triangle to obtain the beheaded variant, A074909. Then take column sums starting from the top of A074909 to get triangle A014430. Row sums of the inverse of triangle T(n,k) gives the Bernoulli numbers, A027641/A026642. Alternatively, triangle T(n,k) as an infinite lower triangular matrix * [the Bernoulli numbers as a vector] = [1, 1, 1, ...]. Given the B_n version starting (1, 1/2, 1/6, ...) triangle T(n,k) * the B_n vector [1, 1/2, 1/6, 0, -1/30, ...] = the triangular numbers. - Gary W. Adamson, Mar 13 2012
From R. J. Mathar, Apr 25 2016: (Start)
If regarded as a symmetric array of the form
  1  2   3   4    5  ...
  2  5   9  14   20  ...
  3  9  19  34   55  ...
  4 14  34  69  125  ...
  5 20  55 125  251  ...
  6 27  83 209  461  ...
  7 35 119 329  791  ...
  8 44 164 494 1286  ...
  9 54 219 714 2001  ...
it contains the rows (and columns) A000096, A062748, A063258, A062988, A124089, ..., A035927 and so on and counts the multisets of digits of numbers in base b>=2 with d>=1 digits (equivalent to the comment in A035927). (End)
Proof of Florian Kleedorfer's formula:  Take sums of the columns of the rectangle - these are all binomial coefficients by the Hockey Stick Identity. Note the locations of these coefficients:  They form a row going almost all the way to the edge, only missing the 1 - apply the Hockey Stick Identity again. - James East, Jul 03 2020

			Triangle begins:
  1;
  2,  2;
  3,  5,  3;
  4,  9,  9,   4;
  5, 14, 19,  14,   5;
  6, 20, 34,  34,  20,  6;
  7, 27, 55,  69,  55, 27,  7;
  8, 35, 83, 125, 125, 83, 35, 8;

Reinhard Zumkeller, Rows n=0..100 of triangle, flattened

Cf. A000096, A007318, A014430, A026642, A027641, A027642, A035927.
Cf. A062748, A063258, A062988, A074909, A124089, A124326, A129696.
Triangle with zeros: A014473.
Cf. A000295 (row sums).

a014430 n k = a014430_tabl !! n !! k
a014430_row n = a014430_tabl !! n
a014430_tabl = map (init . tail) $ drop 2 a014473_tabl
-- Reinhard Zumkeller, Apr 10 2012

[Binomial(n+2,k+1)-1: k in [0..n], n in [0..13]]; // G. C. Greubel, Feb 25 2023

Table[Sum[Sum[Binomial[m, j], {m, j, j+(n-k)}], {j,0,k}], {n,0,10}, {k, 0,n}]//Flatten (* Michael De Vlieger, Sep 01 2020 *)
Table[Binomial[n+2,k+1] -1, {n,0,13}, {k,0,n}]//Flatten (* G. C. Greubel, Feb 25 2023 *)

flatten([[binomial(n+2,k+1)-1 for k in range(n+1)] for n in range(14)]) # G. C. Greubel, Feb 25 2023

T(n, k) = T(n-1, k) + T(n-1, k-1) + 1, T(0, 0)=1. - Ralf Stephan, Jan 23 2005
G.f.: 1 / ((1-x)*(1-x*y)*(1-x*(1+y))). - Ralf Stephan, Jan 24 2005
T(n, k) = Sum_{j=0..k} Sum_{m=j..j+(n-k)} binomial(m, j). - Florian Kleedorfer (florian.kleedorfer(AT)austria.fm), May 23 2005
T(n, k) = binomial(n+2, k+1) - 1. - G. C. Greubel, Feb 25 2023

More terms from Erich Friedman

Offset fixed by Reinhard Zumkeller, Apr 10 2012

A129378 Row sums of coefficients of Bernoulli twin number polynomials.

Original entry on oeis.org

1, 1, 4, 20, 116, 744, 5160, 39360, 350784, 3749760, 42940800, 442713600, 4650877440, 109244298240, 2833294464000, -3487131648000, -2166903606067200, 51809012320665600, 6808619561103360000, -131306587205713920000, -26982365129174827008000, 595860034297401409536000

Offset: 0

Paul Curtz, Jun 08 2007

sign

The origin of the sequence are polynomials on pages 61 and 69 of the CCSA paper. The first few of the polynomials have been noted in the 1992 Gazette paper.
We construct Bernoulli twin numbers polynomials C(n,x) = Sum_{j=1..n} binomial(n-1,j-1)*B(j,x) where B(n,x) are the Bernoulli polynomials of A048998 and A048999 and where binomial(.,.) is the Pascal triangle A007318: C(0,x)=B(0,x); C(1,x)=B(1,x); C(2,x)=B(2,x)+B(1,x); C(3,x)=B(3,x)+2B(2,x)+B(1,x).
The triangle of coefficients [x^m] C(n,x) for rows n=0,1,2,.. and decreasing power m=n,...,0 along each row starts
  1;
  1, -1/2;
  1,    0, -1/3;
  1,  1/2, -1/2, -1/6;
The rightmost fraction in row n, that is, the absolute term C(n,0), is the Bernoulli twin number C(n) of A129826(n), i.e., C(n) = A129826(n)/(n+1)!.
If rows are multiplied by (n+1)!, the triangle becomes
    1;
    2,  -1;
    6,   0,  -2;
   24,  12, -12,  -4;
  120, 120, -60, -60, -4;
The sequence a(n) gives the row sums of this triangle. The sums of antidiagonals are 1, 2, 5, 24, 130, 828, 6056.... The first column of the inverse of the triangle is 1, 2, 3, 3, 0, (0 continued).

P. Curtz, Integration numerique ..., Note no. 12 CCSA (later CELAR), 1969. (See A129841, A129696.)
P. Curtz, Gazette des Mathematiciens, 1992, no. 52, p. 44.

G. C. Greubel, Table of n, a(n) for n = 0..300

Cf. A000142, A007318, A048998, A048999, A129724, A129826.

f:= func< n | n le 2 select (-1)^Floor((n+1)/2)/(n+1) else (-1)^n*BernoulliNumber(Floor(n - (1-(-1)^n)/2)) >;
A129378:= func< n | n eq 0 select 1 else Factorial(n+1)*(f(n)+1) >;
[A129378(n): n in [0..30]]; // G. C. Greubel, Feb 01 2024

c[n_?EvenQ] := BernoulliB[n]; c[n_?OddQ] := -BernoulliB[n-1]; c[1] = -1/2; c[2] = -1/3; a[n_] := (n+1)!*(1+c[n]); a[0]=1; Table[a[n], {n, 0, 21}] (* Jean-François Alcover, Aug 08 2012, after given formula *)

def f(n): return (-1)^((n+1)//2)/(n+1) if n<3 else (-1)^n*bernoulli(n-(n%2))
def A129378(n): return 1 if n==0 else factorial(n+1)*(f(n)+1)
[A129378(n) for n in range(31)] # G. C. Greubel, Feb 01 2024

a(n) = (n+1)!*(1 + C(n)) = A129826(n) + A000142(n+1), n>0.

Edited and extended by R. J. Mathar, Aug 06 2008

A129891 Sum of coefficients of polynomials defined in comments lines.

Original entry on oeis.org

1, 2, 4, 9, 20, 44, 96, 209, 455, 991, 2159, 4704, 10249, 22330, 48651, 105997, 230938, 503150, 1096225, 2388372, 5203604, 11337218, 24700671, 53815949, 117250109, 255455647, 556567394, 1212606837, 2641935832, 5756049469, 12540844137

Offset: 0

Paul Curtz, Jun 04 2007

nonn

At the same time that I introduced the polynomials P(n,x) defined by P(0,x)=1 and for n>0, P(n,x) = (-1)^n/(n+1) + x*Sum_{ i=0..n-1 } ( (-1)^i/(i+1) )*P(n-1-i,x) (Gazette des Mathematiciens 1992), I gave the generalization P(0,x) = u(0), P(n,x) = u(n) + x*Sum_{ i=0..n-1 } u(i)*P(n-1-i,x).
For u(n), n>=0, = 1 1 1 2 3 4 5 6 7 8 ... the array of coefficients of the polynomials P(n,x) is:
  1
  1  1
  1  2  1
  2  3  3  1
  3  6  6  4  1
  4 11 13 10  5  1
  5 18 27 24 15  6  1
  6 28 51 55 40 21  7  1
whose row sums are the present sequence.
The alternating row sums are 1 0 0 1 0 0 0 -1 ...
The antidiagonal sums are 1 1 2 4 7 13 23 41 73 ...
The first column of the inverse matrix is 1 -1 1 -2 5 -11 25 -63 ...

Paul Curtz, Gazette des Mathématiciens, 1992, no. 52, p. 44.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Sums of coefficients of polynomials defined in A140530.

Cf. A129841, A129696, A130620.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x+x^3)/(1-3*x+2*x^2-x^4) )); // G. C. Greubel, Oct 24 2023

a:= n-> (Matrix([1, 1, 0, 1]). Matrix(4, (i, j)-> if i=j-1 then 1 elif j=1 then [3, -2, 0, 1][i] else 0 fi)^n)[1, 1]:
seq(a(n), n=0..50);  # Alois P. Heinz, Oct 14 2009

u[n_ /; n < 3] = 1; u[n_] := n-1;
p[0][x_] := u[0]; p[n_][x_] := p[n][x] = u[n] + x*Sum[ u[i]*p[n-i-1][x] , {i, 0, n-1}] // Expand;
row[n_] := CoefficientList[ p[n][x], x];
Table[row[n] // Total, {n, 0, 30}] (* Jean-François Alcover, Oct 02 2012 *)

def A129891_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-x+x^3)/(1-3*x+2*x^2-x^4) ).list()
A129891_list(40) # G. C. Greubel, Oct 24 2023

G.f.: (1-x+x^3)/(1-3*x+2*x^2-x^4). - Alois P. Heinz, Oct 14 2009

Edited by N. J. A. Sloane, Jul 05 2007

More terms from Alois P. Heinz, Oct 14 2009

A215005 a(n) = a(n-2) + a(n-1) + floor(n/2) + 1 for n > 1 and a(0)=0, a(1)=1.

Original entry on oeis.org

0, 1, 3, 6, 12, 21, 37, 62, 104, 171, 281, 458, 746, 1211, 1965, 3184, 5158, 8351, 13519, 21880, 35410, 57301, 92723, 150036, 242772, 392821, 635607, 1028442, 1664064, 2692521, 4356601, 7049138, 11405756, 18454911, 29860685, 48315614, 78176318, 126491951, 204668289

Offset: 0

Alex Ratushnyak, Jul 31 2012

If the seed is {1,1}: 1, 1, 4, 7, 14, 24, 42, 70, 117, 192, 315, 513, 835, 1355, 2198, 3561, 5768, 9338, 15116, 24464, 39591, 64066, 103669, 167747, ...
If the seed is {1,2}: A129696.
Same seed, but -1 in the formula instead of +1: b(n)=a(n-2)+1 for n>=2, i.e. 0, 1, 1, 2, 4, 7, 13, 22, 38, 63, 105, 172, 282, 459, 747, 1212, 1966, 3185, 5159, 8352, 13520, 21881, 35411, 57302, 92724, 150037, 242773, 392822, ...

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,1,-3,0,1).

Cf. A129696 (same formula, seed {1,2}).
Cf. A000071 (a(n+1) = a(n-1) + a(n) + 1).
Cf. A000045.

[2*Fibonacci(n+2) -(2*n+9-(-1)^n)/4: n in [0..50]]; // G. C. Greubel, Apr 05 2024

LinearRecurrence[{2,1,-3,0,1}, {0,1,3,6,12}, 39] (* Jean-François Alcover, Oct 05 2017 *)
nxt[{n_,a_,b_}]:={n+1,b,a+b+Floor[(n+1)/2]+1}; NestList[nxt,{1,0,1},40][[;;,2]] (* Harvey P. Dale, Feb 20 2025 *)

concat(0, Vec(x*(1+x-x^2)/((1-x)^2*(1+x)*(1-x-x^2)) + O(x^100))) \\ Colin Barker, Sep 16 2015

prpr = 0
prev = 1
for n in range(2,100):
    print(prpr, end=', ')
    curr = prpr+prev + 1 + n//2
    prpr = prev
    prev = curr

[2*fibonacci(n+2) -(n+4+(n%2))//2 for n in range(51)] # G. C. Greubel, Apr 05 2024

a(n) = 2*Fibonacci(n+2) - (2*n + 9 - (-1)^n)/4. - Vaclav Kotesovec, Aug 11 2012
From Colin Barker, Sep 16 2015: (Start)
a(n) = 2*a(n-1) + a(n-2) - 3*a(n-3) + a(n-5) for n>4.
G.f.: x*(1+x-x^2) / ((1-x)^2*(1+x)*(1-x-x^2)). (End)
E.g.f.: 2*exp(x/2)*(cosh(sqrt(5)*x/2) + (3/sqrt(5))*sinh(sqrt(5)*x/2)) - (1/2)*((x+4)*cosh(x) + (x+5)*sinh(x)). - G. C. Greubel, Apr 05 2024

A344004 Number of ordered subsequences of {1,...,n} containing at least three elements and such that the first differences contain only odd numbers.

Original entry on oeis.org

0, 0, 1, 3, 8, 17, 34, 63, 113, 196, 334, 560, 930, 1532, 2511, 4099, 6674, 10845, 17600, 28535, 46235, 74880, 121236, 196248, 317628, 514032, 831829, 1346043, 2178068, 3524321, 5702614, 9227175, 14930045, 24157492, 39087826, 63245624, 102333774, 165579740

Offset: 1

N. J. A. Sloane, Jun 02 2021

			For n = 3 there is just one subset, {1,2,3}, whose first differences, {1,1}, contain only odd numbers.
a(4) = 3 from {1,2,3}, {2,3,4}, {1,2,3,4}.

Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Hung Viet Chu, Various sequences from counting subsets, arXiv:2005.10081 [math.CO], 2020-2021.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-4,3,1,-1).

Cf. A000045, A052952, A129696.

Column k=3 of A345123.

a:= n-> (<<0|1|0|0|0|0>, <0|0|1|0|0|0>, <0|0|0|1|0|0>,
          <0|0|0|0|1|0>, <0|0|0|0|0|1>, <-1|1|3|-4|-1|3>>^n)[3, 6]:
seq(a(n), n=1..38);  # Alois P. Heinz, Jun 02 2021

A344004[n_] := Fibonacci[n+3] - (2*n*(n+4) + (-1)^n + 15)/8; Array[A344004, 50] (* or *)
LinearRecurrence[{3, -1, -4, 3, 1, -1}, {0, 0, 1, 3, 8, 17}, 50] (* Paolo Xausa, Mar 28 2025 *)

G.f.: x^3/((x-1)^3*(x+1)*(x^2+x-1)). - Alois P. Heinz, Jun 02 2021
Comment from N. J. A. Sloane, Jun 03 2021. (Start)
Theorem: This sequence has g.f. G_1(x) = x^3/((1-x)^3*(1+x)*(1-x-x^2)) = x^3/(1-2*x-x^2+3*x^3-x^5), which implies a linear recurrence with constant coefficients and signature (3,-1,-4,3,1,-1).
Proof: We will not give a complete proof, but we will do enough, we hope, to convince the reader.
Let b(n) be the number of ordered subsequences S of {1,...,n} containing at least three elements, such that the first differences contain only odd numbers, and in which the largest term is n.
Then the a(n) are the partial sums of the b(n), and we claim that b(n) has generating function (1-x)*G_1(x).
We obtain a recurrence for b(n) as follows.
If we remove n from the subsequence S, there are two possibilities. Either we obtain a subsequence of {1,...,n-i} with largest term n-r (r odd) containing at least three elements, or we obtain a pair j, n-r with r and n-r-j odd. In this case j can be chosen in floor((n-r)/2) ways.
So, setting r = 2*i+1, we have shown that b(n) satisfies the recurrence
b(n) = Sum_{i = 0..(floor(n/2)-1)} (b(n-(2*i+1)) + floor((n-(2*i+1))/2)),
with initial conditions b(1)=b(2)=0, b(3)=1.
It turns out that b(n) is a fairly well-known sequence, A129696, whose generating function is known to equal (1-x)*G_1(x), and whose first differences (A052952) are essentially the Fibonacci numbers F_k with 1 subtracted if k is even. (End)
a(n) = Fibonacci(n+3) - (1/8)(15 + 8*n + 2*n^2 + (-1)^n). - Greg Dresden, Jun 20 2021

a(13)-a(38) from Alois P. Heinz, Jun 02 2021

cp's OEIS Frontend

A192744 Constant term of the reduction by x^2->x+1 of the polynomial p(n,x) defined below in Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A001924 Apply partial sum operator twice to Fibonacci numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

A035317 Pascal-like triangle associated with A000670.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A014473 Pascal's triangle - 1: Triangle read by rows: T(n, k) = A007318(n, k) - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

SageMath

Formula