A001871 -id:A001871 - cp's OEIS frontend

A121486 Number of peaks at even level in all nondecreasing Dyck paths of semilength n. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.

0, 1, 4, 13, 43, 132, 400, 1184, 3461, 9999, 28634, 81383, 229860, 645731, 1805582, 5028189, 13952221, 38590922, 106434540, 292792026, 803565215, 2200694791, 6015268164, 16412564173, 44708036568, 121600924117, 330277253560

Offset: 1

Emeric Deutsch, Aug 02 2006

nonn

			a(3)=4 because in UDUDUD, UDUU|DD, UU|DDUD, UU|DU|DD and UUUDDD we have altogether 4 peaks at even level (shown by a |); here U=(1,1) and D=(1,-1).

E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
Index entries for linear recurrences with constant coefficients, signature (6,-9,-5,15,-1,-4,1).

Cf. A121484, A121483, A038731.

G:=z^2*(1-z)*(1-z-3*z^2+3*z^3-z^4)/(1+z)/(1-z-z^2)/(1-3*z+z^2)^2: Gser:=series(G,z=0,33): seq(coeff(Gser,z,n),n=1..30);

Rest[CoefficientList[Series[x^2*(1-x)*(1-x-3*x^2+3*x^3-x^4)/(1+x)/(1-x-x^2)/(1-3*x+x^2)^2, {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 20 2014 *)

a(n) = Sum(k*A121484(n,k),k=0..n-1).
G.f.: z^2*(1-z)(1-z-3z^2+3z^3-z^4)/[(1+z)(1-z-z^2)(1-3z+z^2)^2].
a(n) ~ (sqrt(5)-1) * (3+sqrt(5))^n * n / (5 * 2^(n+2)). - Vaclav Kotesovec, Mar 20 2014
20*a(n) = -8*(-1)^n +10*(2*A001871(n)-5*A001871(n-1))+5*(4*A000045(n+1)-7*A000045(n))-3*(4*A001906(n+1)+9*A001906(n)). - R. J. Mathar, Jul 26 2022

A165206 a(n) = (3-4n)F(2n-2) + (4-7n)F(2n-1).

Original entry on oeis.org

1, -3, -25, -112, -416, -1411, -4537, -14085, -42653, -126794, -371554, -1076423, -3089555, -8799207, -24897121, -70052356, -196151492, -546916555, -1519249933, -4206274089, -11611243109, -31967026718, -87796880710

Offset: 0

Paul Barry, Sep 07 2009

Hankel transform of A165205.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Cf. A000045.

F:=Fibonacci;; List([0..30], n-> (3-4*n)*F(2*n-2)+(4-7*n)*F(2*n-1) ); # G. C. Greubel, Jul 18 2019

F:=Fibonacci; [(3-4*n)*F(2*n-2)+(4-7*n)*F(2*n-1): n in [0..30]]; // G. C. Greubel, Jul 18 2019

Table[(3-4n)Fibonacci[2n-2]+(4-7n)Fibonacci[2n-1],{n,0,30}] (* or *) LinearRecurrence[{6,-11,6,-1},{1,-3,-25,-112},30] (* Harvey P. Dale, Aug 25 2013 *)

vector(30, n, n--; f=fibonacci; (3-4*n)*f(2*n-2)+(4-7*n)*f(2*n-1)) \\ G. C. Greubel, Jul 18 2019

f=fibonacci; [(3-4*n)*f(2*n-2)+(4-7*n)*f(2*n-1) for n in (0..30)] # G. C. Greubel, Jul 18 2019

G.f.: (1-9*x+4*x^2-x^3)/(1-3*x+x^2)^2 = (1-x)/(1-3*x+x^2) - 5*x/(1-3*x+x^2)^2.

a(n) = -5*A001871(n-1) + A001519(n+1). - R. J. Mathar, Dec 16 2024

A167423 Hankel transform of a simple Catalan convolution.

Original entry on oeis.org

1, -1, -11, -50, -186, -631, -2029, -6299, -19075, -56704, -166164, -481391, -1381691, -3935125, -11134331, -31328366, -87721614, -244588519, -679429225, -1881102959, -5192705779, -14296088956, -39263958696, -107601905375, -294291714551, -803416991401

Offset: 0

Paul Barry, Nov 03 2009

Hankel transform of A167422.

G. C. Greubel, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

Cf. A167422, A000045, A000032.

[Fibonacci(2*n)*(1-3*n)/2 + Lucas(2*n)*(1-n)/2: n in [0..30]]; // Vincenzo Librandi, Jun 13 2016

Table[((1-3n) Fibonacci[2n] + (1-n) LucasL[2n])/2, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 28 2015 *)
LinearRecurrence[{6, -11, 6, -1}, {1, -1, -11, -50}, 50] (* G. C. Greubel, Jun 12 2016 *)

Vec((1-7*x+6*x^2-x^3)/(1-6*x+11*x^2-6*x^3+x^4) + O(x^100)) \\ Altug Alkan, Oct 29 2015

G.f.: ( 1-7*x+6*x^2-x^3 ) / (x^2-3*x+1)^2 .
a(n) = F(2*n)*(1-3*n)/2 + L(2*n)*(1-n)/2. - Paul Barry, Feb 22 2010
a(n) = 3*A001871(n-1) - 2*A001871(n) + F(2*n+4). - Ralf Stephan, May 21 2014
a(n) = 1 - Sum_{k=1..n} k*F(2*k+1), where F(n) = A000045(n). - Vladimir Reshetnikov, Oct 28 2015

A167477 Expansion of (1-3x+5x^2-x^3)/(1-3x+x^2)^2.

Original entry on oeis.org

1, 3, 12, 44, 149, 479, 1487, 4503, 13386, 39226, 113641, 326173, 928957, 2628459, 7395624, 20708264, 57739517, 160391483, 444068171, 1225831551, 3374848806, 9268963318, 25401364177, 69472849849, 189661024249, 516904018899

Offset: 0

Paul Barry, Nov 04 2009

Hankel transform of A033297 (when this starts 1,1,4,...).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-11,6,-1).

LinearRecurrence[{6, -11, 6, -1}, {1, 3, 12, 44}, 100] (* G. C. Greubel, Jun 13 2016 *)

a(n) = 4*A001871(n-1) - A001871(n) + A001519(n+2). - R. J. Mathar, Jun 28 2011

A226431 The number of permutations of length n in a particular geometric grid class.

Original entry on oeis.org

1, 2, 6, 21, 73, 244, 786, 2458, 7510, 22527, 66579, 194408, 561988, 1610900, 4584426, 12966225, 36476173, 102132412, 284785878, 791182318, 2190833086, 6048706947, 16655647911, 45752451536, 125405039368, 343040546984, 936651104466, 2553146783253, 6948573570145

Offset: 1

Jay Pantone, Jun 06 2013

nonn

This geometric grid class is given by the array [[0,0,1,0],[0,0,0,1],[0,1,-1,0],[1,0,0,-1]]. A picture is given in the LINKS section.

The simple permutations in this class are A226432.

Jay Pantone, The Enumeration of Permutations Avoiding 3124 and 4312, arXiv:1309.0832 [math.CO], 2013-2015.
Jay Pantone, Picture of the geometric grid class
Index entries for linear recurrences with constant coefficients, signature (9,-31,51,-41,15,-2).

LinearRecurrence[{9, -31, 51, -41, 15, -2}, {1, 2, 6, 21, 73, 244}, 29] (* Jean-François Alcover, Oct 30 2018 *)

x=x='x+O('x^66); Vec((x-7*x^2+19*x^3-22*x^4+9*x^5-x^6)/((1-x)*(1-2*x)*(1-3*x+x^2)^2) ) \\ Joerg Arndt, Jun 19 2013

G.f.: x*(1-7*x+19*x^2-22*x^3+9*x^4-x^5)/((1-x)*(1-2*x)*(1-3*x+x^2)^2).

a(n) = 3*A001871(n-1)-A001871(n) +2*A001906(n) +2^(n-1)+1. - R. J. Mathar, Aug 31 2013

A238419 a(n) = the Wiener index of the Fibonacci cube G_n.

Original entry on oeis.org

0, 1, 4, 16, 54, 176, 548, 1667, 4968, 14592, 42348, 121728, 347112, 983173, 2768812, 7758928, 21648546, 60172784, 166687436, 460356359, 1267964496, 3483818880, 9550754520, 26129950080, 71356349520, 194529354505, 529485228244, 1439096616976, 3906061968654, 10588691040176, 28670559059444

Offset: 0

Emeric Deutsch, Mar 26 2014

The Fibonacci cube G_n is defined in the Klavzar and Mollard reference (as Gamma_n).

			a(2)=4 because the Fibonacci cube G_2 is the path P_3 having Wiener index 1 + 1 + 2 = 4.

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. Klavzar, M. Mollard, Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes, MATCH Commun. Math. Comput. Chem., 68, 2012, 311-324.
Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
Eric Weisstein's World of Mathematics, Wiener Index
Index entries for linear recurrences with constant coefficients, signature (4,0,-10,0,4,-1).

Cf. A000045.

[(4*(n+1)*Fibonacci(n)^2 + (9*n+2)*Fibonacci(n)*Fibonacci(n+1) + 6*n*Fibonacci(n+1)^2)/25: n in [0..30]]; // Vincenzo Librandi, Mar 27 2014

with(combinat): F := proc (n) options operator, arrow: Fibonacci(n) end proc: a := proc (n) options operator, arrow: (1/25)*(4*n+4)*F(n)^2+(1/25)*(9*n+2)*F(n)*F(n+1)+(6/25)*n*F(n+1)^2 end proc: seq(a(n), n = 0 .. 30);

wifc[n_]:=Module[{f1=Fibonacci[n],f2=Fibonacci[n+1]},(4*(n+1)*f1^2+ (9*n+2)*f1*f2+ 6*n*f2^2)/25]; wifc[Range[0, 30]] (* Harvey P. Dale, Sep 22 2014 *)
LinearRecurrence[{4, 0, -10, 0, 4, -1}, {0, 1, 4, 16, 54, 176}, 100] (* G. C. Greubel, Mar 27 2016 *)
CoefficientList[Series[x/(1 - 2 x - 2 x^2 + x^3)^2, {x, 0, 20}], x] (* Eric W. Weisstein, Sep 07 2017 *)
Table[(n LucasL[2 (n + 2)] + 2 Fibonacci[2 n + 1] - (n + 2) (-1)^n)/25, {n, 0, 20}] (* Eric W. Weisstein, Sep 07 2017 *)

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,4,0,-10,0,4]^n*[0;1;4;16;54;176])[1,1] \\ Charles R Greathouse IV, Sep 07 2017

a(n) = ( 4*(n + 1)*F(n)^2 + (9*n + 2)*F(n)*F(n+1) + 6*n*F(n+1)^2 )/25, where F = A000045 (Fibonacci numbers).
a(n) = sum( F(i)*F(i+1)*F(n-i+1)*F(n-i+2), i=1..n ), where F = A000045.
Empirical g.f.: x / ((x+1)^2*(x^2-3*x+1)^2). - Colin Barker, Mar 26 2014
The g.f. above is correct because a(n) is the convolution of F(n)F(n+1) by F(n+1)F(n+2) (see Klavzar and Mollard paper). - Michel Mollard, Aug 20 2014.
The g.f. above is correct because it is equal to (dG/dt)A246173.%20-%20_Emeric%20Deutsch">{t=1}, where G is the bivariate g.f. given in A246173. - _Emeric Deutsch, Oct 01 2014
a(n+3) = (2*(n+3)*a(n+2)+2*(n+4)*a(n+1)-(n+5)*a(n))/(n+2). - Robert Israel, Aug 29 2014
25*a(n) = n*Lucas(2*(n+2))+2*Fibonacci(2*n+1)-(n+2)*(-1)^n. - Ehren Metcalfe, Mar 26 2016
a(n) = 4*a(n-1) - 10*a(n-3) + 4*a(n-5) - a(n-6). - G. C. Greubel, Mar 27 2016
25*a(n) = -A001906(n+2) +5*A001871(n) -(n+2)*(-1)^n. - R. J. Mathar, Jul 24 2022

A181371 Triangle read by rows: T(n,k) is the number of ternary words (i.e., finite sequences of 0's, 1's and 2's) of length n having k occurrences of 01's (0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 3, 8, 1, 21, 6, 55, 25, 1, 144, 90, 9, 377, 300, 51, 1, 987, 954, 234, 12, 2584, 2939, 951, 86, 1, 6765, 8850, 3573, 480, 15, 17711, 26195, 12707, 2305, 130, 1, 46368, 76500, 43398, 10008, 855, 18, 121393, 221016, 143682, 40426, 4740, 183, 1, 317811

Offset: 0

Emeric Deutsch, Oct 31 2010

Row n contains 1 + floor(n/2) entries.
Sum of entries in row n is 3^n = A000244(n).
T(n,0) = F(2n+2) = A001906(n+1) (even-subscripted Fibonacci numbers).
T(n,1) = A001871(n-2).
Sum_{k>=0}k*T(n,k) = (n-1)*3^(n-2) = A027471(n) (n>=1).

			T(3,1)=6 because we have 010, 011, 012, 001, 101 and 201.
T(4,2)=1 because we have 0101.
Triangle starts:
    1;
    3;
    8,  1;
   21,  6;
   55, 25,  1;
  144, 90,  9;

Alois P. Heinz, Rows n = 0..200, flattened
Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

Cf. A000244, A001871, A001906, A027471.

G := 1/(1-3*z+z^2-t*z^2): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 13 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 13 do seq(coeff(P[n], t, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

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

A238941 Triangle T(n,k), read by rows given by (1, 1, 1, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (1, 0, -1, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 5, 8, 4, 1, 13, 21, 13, 6, 1, 34, 55, 40, 25, 7, 1, 89, 144, 120, 90, 33, 9, 1, 233, 377, 354, 300, 132, 51, 10, 1, 610, 987, 1031, 954, 483, 234, 62, 12, 1, 1597, 2584, 2972, 2939, 1671, 951, 308, 86, 13, 1, 4181, 6765, 8495, 8850, 5561, 3573, 1345, 480, 100, 15, 1

Offset: 0

Philippe Deléham, Mar 07 2014

Row sums are A025192(n).

			Triangle begins:
1;
1, 1;
2, 3, 1;
5, 8, 4, 1;
13, 21, 13, 6, 1;
34, 55, 40, 25, 7, 1;
89, 144, 120, 90, 33, 9, 1;
233, 377, 354, 300, 132, 51, 10, 1;

Indranil Ghosh, Rows 0..100, flattened

Cf. Columns: A001519, A001906, A238846, A001871.

Cf. Diagonals: A000012, A032766.

nmax=10; Column[CoefficientList[Series[CoefficientList[Series[(1 - 2*x + x*y)/(1 - 3*x + x^2 - x^2*y^2), {x, 0, nmax }], x], {y, 0, nmax}], y]] (* Indranil Ghosh, Mar 14 2017 *)

G.f. for the column k: x^k*(1-2*x)^A059841(k)/(1-3*x+x^2)^A008619(k).
G.f.: (1-2*x+x*y)/(1-3*x+x^2-x^2*y^2).
T(n,k) = 3*T(n-1,k) + T(n-2,k-2) - T(n-2,k), T(0,0) = T(1,0) = T(1,1) = 1, T(n,k) = 0 if k<0 or if k>n.
Sum_{k = 0..n} T(n,k)*x^k = A000007(n), A001519(n), A025192(n), A030195(n+1) for x = -1, 0, 1, 2 respectively.
Sum_{k = 0..n} T(n,k)*3^k = A015525(n) + A015525(n+1).

Data section corrected and extended by Indranil Ghosh, Mar 14 2017

A246175 The hyper-Wiener index of the Fibonacci cube Gamma(n) (n>=1).

Original entry on oeis.org

1, 5, 23, 89, 325, 1123, 3750, 12174, 38682, 120750, 371478, 1128810, 3394159, 10112987, 29892425, 87737471, 255912115, 742272853, 2142128604, 6153811500, 17605105380, 50174676300, 142501128540, 403422149220, 1138714934125, 3205372562369, 8999834877995, 25209180070037

Offset: 1

Emeric Deutsch, Aug 18 2014

The Fibonacci cube Gamma(n) can be defined as the graph whose vertices are the binary strings of length n without two consecutive 1's and in which two vertices are adjacent when their Hamming distance is exactly 1.

G. G. Cash, Relationship between the Hosoya polynomial and the hyper-Wiener index, Appl. Math. Letters, 15, 2002, 893-895.
S. Klavzar, M. Mollard, Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes, MATCH Commun. Math. Comput. Chem., 68, 2012, 311-324.
Index entries for linear recurrences with constant coefficients, signature (6,-6,-19,24,24,-19,-6,6,-1).

Cf. A246176

G := z*(1-z-z^2)/((1+z)^3*(1-3*z+z^2)^3): Gser := series(G, z = 0, 40): seq(coeff(Gser, z, j), j = 1 .. 35);

CoefficientList[Series[z (1-z-z^2)/((1+z)^3(1-3z+z^2)^3),{z,0,30}],z] (* Harvey P. Dale, Mar 05 2019 *)

G.f.: z*(1-z-z^2)/((1+z)^3*(1-3*z+z^2)^3).

625*a(n) = -1/2*(-1)^n*(74+45*n+5*n^2) -5*(2*A001871(n)-3*A001871(n-1)) +17*A001906(n)-53*A001906(n+1) +50*(2*A246178(n)-3*A246178(n-1)). - R. J. Mathar, Jul 22 2022

A246178 Expansion of 1/(1 - 3*x + x^2)^3.

Original entry on oeis.org

1, 9, 51, 234, 951, 3573, 12707, 43398, 143682, 464148, 1469778, 4578102, 14063653, 42695127, 128301453, 382144446, 1129360689, 3314619171, 9668400839, 28045947996, 80949547380, 232589050920, 665532883380, 1897176603420, 5389368930505, 15260830474869, 43085718922071, 121310066722194, 340684392838971, 954497114903169

Offset: 0

Emeric Deutsch, Aug 23 2014

a(n) is the number of words of length n + 4 over the alphabet {0,1,2} which contain the subword 01 exactly twice. - Leidy Espitia, Sep 10 2020

Index entries for linear recurrences with constant coefficients, signature (9,-30,45,-30,9,-1).

Cf. A000045, A001906, A001871.

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( 1/(1 - 3*x + x^2)^3 )); // Wesley Ivan Hurt, Oct 02 2020

S := series(1/(1-3*x+x^2)^3, x = 0, 30): seq(coeff(S, x, j), j = 0 .. 30);

Table[(2 (25 + 39 n + 20 n^2) Fibonacci[2n+1] + (38 + 51 n + 25 n^2) Fibonacci[2n])/50, {n, 0, 24}] (* Emanuele Munarini, Mar 08 2018 *)
CoefficientList[Series[1/(1-3x+x^2)^3,{x,0,50}],x] (* or *) LinearRecurrence[ {9,-30,45,-30,9,-1},{1,9,51,234,951,3573},50] (* Harvey P. Dale, Jan 16 2022 *)

makelist(((38+51*n+25*n^2)*fib(2*n)+2*(25+39*n+20*n^2)*fib(1+2*n))/50, n, 0, 30); /* Emanuele Munarini, Mar 08 2018 */

my(x='x+O('x^30)); Vec(1/(1-3*x+x^2)^3) \\ Altug Alkan, Mar 08 2018

a(n) = (2*(25 + 39*n + 20*n^2)*F(2*n+1) + (38 + 51*n + 25*n^2)*F(2*n))/50, where F = A000045. - Emanuele Munarini, Mar 08 2018
a(n) = Sum_{t=0..n} Sum_{i=0..n-t} f(i)*f(t)*f(n-i-t), where f(n) = Fibonacci(2*n+2) = A001906(n+1). - Leidy Espitia, Sep 10 2020
a(n) = 9*a(n-1) - 30*a(n-2) + 45*a(n-3) - 30*a(n-4) + 9*a(n-5) - a(n-6). - Wesley Ivan Hurt, Sep 30 2020

cp's OEIS Frontend

A121486 Number of peaks at even level in all nondecreasing Dyck paths of semilength n. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A165206 a(n) = (3-4*n)*F(2*n-2) + (4-7*n)*F(2*n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A167423 Hankel transform of a simple Catalan convolution.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A167477 Expansion of (1-3x+5x^2-x^3)/(1-3x+x^2)^2.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

Formula

A226431 The number of permutations of length n in a particular geometric grid class.

Views

Author

Keywords

Comments

Links

Programs

Mathematica

PARI

Formula

A238419 a(n) = the Wiener index of the Fibonacci cube G_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A181371 Triangle read by rows: T(n,k) is the number of ternary words (i.e., finite sequences of 0's, 1's and 2's) of length n having k occurrences of 01's (0 <= k <= floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A165206 a(n) = (3-4n)F(2n-2) + (4-7n)F(2n-1).