A005672 -id:A005672 - cp's OEIS frontend

A054143 Triangular array T given by T(n,k) = Sum_{0 <= j <= i-n+k, n-k <= i <= n} C(i,j) for n >= 0 and 0 <= k <= n.

1, 1, 3, 1, 4, 7, 1, 5, 11, 15, 1, 6, 16, 26, 31, 1, 7, 22, 42, 57, 63, 1, 8, 29, 64, 99, 120, 127, 1, 9, 37, 93, 163, 219, 247, 255, 1, 10, 46, 130, 256, 382, 466, 502, 511, 1, 11, 56, 176, 386, 638, 848, 968, 1013, 1023, 1, 12, 67, 232, 562, 1024, 1486, 1816, 1981, 2036, 2047

Offset: 0

Clark Kimberling, Mar 18 2000

Row sums given by A001787.
T(n, n) = -1 + 2^(n+1).
T(2*n, n) = 4^n.
T(2*n+1, n) = A000346(n).
T(2*n-1, n) = A032443(n).
A054143 is the fission of the polynomial sequence ((x+1)^n) by the polynomial sequence (q(n,x)) given by q(n,x) = x^n + x^(n-1) + ... + x + 1. See A193842 for the definition of fission. - Clark Kimberling, Aug 07 2011

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
  1;
  1,  3;
  1,  4,  7;
  1,  5, 11, 15;
  1,  6, 16, 26, 31;
  1,  7, 22, 42, 57, 63;

G. C. Greubel, Rows n = 0..100 of triangle, flattened

Cf. A000346, A001787, A032443.

Diagonal sums give A005672. - Paul Barry, Feb 07 2003

Flat(List([0..12], n-> List([0..n], k-> Sum([n-k..n], i-> Sum([0..i-n+k], j-> Binomial(i,j) ))))); # G. C. Greubel, Aug 01 2019

T:= func< n,k | (&+[ (&+[ Binomial(i,j): j in [0..i-n+k]]): i in [n-k..n]]) >;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Aug 01 2019

A054143_row := proc(n) add(add(binomial(n,n-i)*x^(k+1),i=0..k),k=0..n-1); coeffs(sort(%)) end; seq(print(A054143_row(n)),n=1..6); # Peter Luschny, Sep 29 2011

(* First program *)
z=10;
p[n_,x_]:=(x+1)^n;
q[0,x_]:=1;q[n_,x_]:=x*q[n-1,x]+1;
p1[n_,k_]:=Coefficient[p[n,x],x^k];p1[n_,0]:=p[n,x]/.x->0;
d[n_,x_]:=Sum[p1[n,k]*q[n-1-k,x],{k,0,n-1}]
h[n_]:=CoefficientList[d[n,x],{x}]
TableForm[Table[Reverse[h[n]],{n,0,z}]]
Flatten[Table[Reverse[h[n]],{n,-1,z}]] (* A054143 *)
TableForm[Table[h[n],{n,0,z}]]
Flatten[Table[h[n],{n,-1,z}]] (* A104709 *)
(* Second program *)
Table[Sum[Binomial[i, j], {i, n-k, n}, {j,0,i-n+k}], {n,0,12}, {k,0,n}]// Flatten (* G. C. Greubel, Aug 01 2019 *)

T(n,k) = sum(i=n-k,n, sum(j=0,i-n+k, binomial(i,j)));
for(n=0,12, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, Aug 01 2019

def T(n, k): return sum(sum( binomial(i,j) for j in (0..i-n+k)) for i in (n-k..n))
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Aug 01 2019

T(n,k) = Sum_{0 <= j <= i-n+k, n-k <= i <= n} binomial(i,j).
T(n,k) = T(n-1,k) + 3*T(n-1,k-1) - 2*T(n-2,k-1) - 2*T(n-2,k-2), T(0,0) = 1, T(n,k) = 0 if k < 0 or if k > n. - Philippe Deléham, Nov 30 2013
From Petros Hadjicostas, Jun 05 2020: (Start)
Bivariate o.g.f.: Sum_{n,k >= 0} T(n,k)*x^n*y^k = 1/(1 - x - 3*x*y + 2*x^2*y + 2*x^2*y^2) = 1/((1 - 2*x*y)*(1 - x*(y+1))).
n-th row o.g.f.: ((1 + y)^(n+1) - (2*y)^(n+1))/(1 - y). (End)

Name edited by Petros Hadjicostas, Jun 04 2020

A132890 Triangle read by rows: T(n,k) is the number of left factors of Dyck paths of length n that have height k (1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 4, 1, 1, 1, 7, 5, 5, 1, 1, 1, 7, 13, 6, 6, 1, 1, 1, 15, 18, 20, 7, 7, 1, 1, 1, 15, 39, 26, 27, 8, 8, 1, 1, 1, 31, 57, 73, 35, 35, 9, 9, 1, 1, 1, 31, 112, 99, 109, 44, 44, 10, 10, 1, 1, 1, 63, 169, 253, 152, 154, 54, 54, 11, 11, 1, 1

Offset: 1

Emeric Deutsch, Sep 08 2007

Sum of terms in row n = binomial(n, floor(n/2)) = A001405(n).
T(n,2) = A052551(n-2) (n >= 2).
T(n,3) = A005672(n) = Fibonacci(n+1) - 2^floor(n/2).
Sum_{k=1..n} k*T(n,k) = A132891(n).

			T(5,3)=4 because we have UDUUU, UUDUU, UUUDD and UUUDU, where U=(1,1) and D=(1,-1).
Triangle starts:
  1;
  1, 1;
  1, 1, 1;
  1, 3, 1, 1;
  1, 3, 4, 1; 1;
  1, 7, 5, 5, 1, 1;

Alois P. Heinz, Rows n = 1..141, flattened
Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.
R. Kemp, On the average depth of a prefix of the Dycklanguage D_1, Discrete Math., 36, 1981, 155-170.
Toufik Mansour, Gokhan Yilidirim, Longest increasing subsequences in involutions avoiding patterns of length three, Turkish Journal of Mathematics (2019), Section 2.2

Cf. A001405, A052551, A005672, A132891, A068914.

v := ((1-sqrt(1-4*z^2))*1/2)/z: g := proc (k) options operator, arrow: v^k*(1+v)*(1+v^2)/((1+v^(k+1))*(1+v^(k+2))) end proc: T := proc (n, k) options operator, arrow: coeff(series(g(k), z = 0, 50), z, n) end proc: for n from 0 to 12 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, k) option remember; `if`(x=0, z^k, `if`(y>0,
      b(x-2, y-1, k), 0)+ b(x-2, y+1, max(y+1, k)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..n))(b(2*n, 0$2)):
seq(T(n), n=1..16);  # Alois P. Heinz, Sep 05 2017

b[x_, y_, k_] := b[x, y, k] = If[x == 0, z^k, If[y > 0, b[x - 2, y - 1, k], 0] + b[x - 2, y + 1, Max[y + 1, k]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 1, n}]][b[2n, 0, 0]];
Table[T[n], {n, 1, 16}] // Flatten (* Jean-François Alcover, Apr 01 2018, after Alois P. Heinz *)

The g.f. of column k is g(k, z) = v^k*(1+v)*(1+v^2)*/((1+v^(k+1))*(1+v^(k+2))), where v = (1-sqrt(1-4*z^2))/(2*z). (Obtained as the difference G(k,z)-G(k-1,z), where G(k,z) is given in the R. Kemp reference (p. 159).)

Keyword tabl added by Michel Marcus, Apr 09 2013

A079284 Diagonal sums of triangle A008949.

Original entry on oeis.org

1, 1, 3, 4, 9, 13, 26, 39, 73, 112, 201, 313, 546, 859, 1469, 2328, 3925, 6253, 10434, 16687, 27633, 44320, 72977, 117297, 192322, 309619, 506037, 815656, 1329885, 2145541, 3491810, 5637351, 9161929, 14799280, 24026745, 38826025, 62983842, 101809867, 165055853, 266865720

Offset: 0

Paul Barry, Feb 08 2003

a(2n) - a(2n-1) = Fibonacci(2n+1).

Diagonal sums of triangle A054450. - Paul Barry, Oct 23 2004

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Donatella Merlini, Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
Index entries for linear recurrences with constant coefficients, signature (1,3,-2,-2).

Cf. A000045, A005672, A008949, A061667, A079284, A102517.

[Fibonacci(n+3)-2^Floor((n+1)/2): n in [0..40]]; // Vincenzo Librandi, Aug 05 2013

with (combinat):a[0]:=0:a[1]:=1:a[2]:=1:for n from 2 to 50 do a[n]:=fibonacci(n-1)+2*a[n-2] od: seq(a[n], n=1..31); # Zerinvary Lajos, Mar 17 2008

CoefficientList[Series[(1 - x^2) / ((1 - x - x^2) (1 - 2 x^2)), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 05 2013 *)
LinearRecurrence[{1,3,-2,-2},{1,1,3,4},40] (* Harvey P. Dale, Nov 30 2018 *)

a(n) = Sum_{j=0..floor(n/2)} Sum_{i=0..j} binomial(n-j, i).
a(n) = Fibonacci(n+3) - 2^floor((n+1)/2). - Vladeta Jovovic, Feb 12 2003
G.f.: (1-x^2)/((1-x-x^2)(1-2x^2)). - Paul Barry, Jan 13 2005

A295717 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 5, a(3) = 7.

Original entry on oeis.org

1, 3, 5, 7, 14, 19, 37, 52, 97, 141, 254, 379, 665, 1012, 1741, 2689, 4558, 7119, 11933, 18796, 31241, 49525, 81790, 130291, 214129, 342372, 560597, 898873, 1467662, 2358343, 3842389, 6184348, 10059505, 16211085, 26336126, 42481675, 68948873, 111299476

Offset: 0

Clark Kimberling, Nov 29 2017

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1, 3, -2, -2)

Cf. A001622, A000045, A005672.

LinearRecurrence[{1, 3, -2, -2}, {1, 3, 5, 7}, 100]

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 3, a(2) = 5, a(3) = 7.

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

A295718 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 4, a(3) = 5.

Original entry on oeis.org

1, 3, 4, 5, 9, 10, 19, 21, 40, 45, 85, 98, 183, 217, 400, 489, 889, 1122, 2011, 2621, 4632, 6229, 10861, 15042, 25903, 36849, 62752, 91409, 154161, 229186, 383347, 579765, 963112, 1477341, 2440453, 3786722, 6227175, 9751753, 15978928, 25206393, 41185321

Offset: 0

Clark Kimberling, Nov 29 2017

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1, 3, -2, -2)

Cf. A001622, A000045, A005672.

LinearRecurrence[{1, 3, -2, -2}, {1, 3, 4, 5}, 100]

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 3, a(2) = 4, a(3) = 5.

G.f.: (1 + 2 x - 2 x^2 - 6 x^3)/(1 - x - 3 x^2 + 2 x^3 + 2 x^4).

A295719 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 6, a(3) = 10.

Original entry on oeis.org

1, 3, 6, 10, 20, 32, 60, 96, 172, 276, 480, 772, 1316, 2120, 3564, 5748, 9568, 15444, 25524, 41224, 67772, 109508, 179328, 289860, 473284, 765192, 1246668, 2015956, 3279008, 5303156, 8614932, 13934472, 22614940, 36582180, 59328192, 95975908, 155566244

Offset: 0

Clark Kimberling, Nov 29 2017

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1, 3, -2, -2)

Cf. A001622, A000045, A005672.

LinearRecurrence[{1, 3, -2, -2}, {1, 3, 6, 10}, 100]

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 3, a(2) = 6, a(3) = 10.

G.f.: (1 + 2 x - 3 x^3)/(1 - x - 3 x^2 + 2 x^3 + 2 x^4).

A295720 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 4, a(2) = 9, a(3) = 16.

Original entry on oeis.org

1, 4, 9, 16, 33, 55, 104, 171, 307, 502, 873, 1423, 2424, 3943, 6623, 10758, 17893, 29035, 47952, 77755, 127755, 207046, 338897, 549015, 896104, 1451263, 2363751, 3827302, 6223821, 10075699, 16365056, 26489907, 42986035, 69574246, 112822425, 182593279

Offset: 0

Clark Kimberling, Nov 29 2017

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1, 3, -2, -2)

Cf. A001622, A000045, A005672.

LinearRecurrence[{1, 3, -2, -2}, {1, 4, 9, 16}, 100]

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 1, a(1) = 4, a(2) = 9, a(3) = 16.

G.f.: (1 + 3 x + 2 x^2 - 3 x^3)/(1 - x - 3 x^2 + 2 x^3 + 2 x^4).

A295721 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = -1, a(1) = 2, a(2) = 3, a(3) = 4.

Original entry on oeis.org

-1, 2, 3, 4, 11, 13, 32, 41, 89, 122, 243, 349, 656, 973, 1757, 2666, 4679, 7217, 12408, 19369, 32801, 51658, 86507, 137141, 227744, 362837, 598773, 957514, 1572671, 2521993, 4127432, 6633041, 10826009, 17426282, 28383363, 45744109, 74389616, 120002653

Offset: 0

Clark Kimberling, Nov 29 2017

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1, 3, -2, -2)

Cf. A001622, A000045, A005672.

LinearRecurrence[{1, 3, -2, -2}, {-1, 2, 3, 4}, 100]

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = -1, a(1) = 2, a(2) = 3, a(3) = 4.

G.f.: (-1 + 3 x + 4 x^2 - 7 x^3)/(1 - x - 3 x^2 + 2 x^3 + 2 x^4).

A295722 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = -1, a(1) = -1, a(2) = 2, a(3) = 3.

Original entry on oeis.org

-1, -1, 2, 3, 13, 20, 49, 77, 158, 251, 473, 756, 1357, 2177, 3790, 6095, 10397, 16748, 28169, 45429, 75646, 122099, 201841, 325988, 536021, 866105, 1418510, 2292807, 3744085, 6053276, 9862897, 15948941, 25942910, 41957387, 68162441, 110250900, 178937629

Offset: 0

Clark Kimberling, Nov 29 2017

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1, 3, -2, -2)

Cf. A001622, A000045, A005672.

LinearRecurrence[{1, 3, -2, -2}, {-1, -1, 2, 3}, 100]

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = -1, a(1) = -2, a(2) = 2, a(3) = 3.

G.f.: (-1 + 6 x^2 + 2 x^3)/(1 - x - 3 x^2 + 2 x^3 + 2 x^4).

A295723 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 3.

Original entry on oeis.org

0, 1, 2, 3, 7, 10, 21, 31, 60, 91, 167, 258, 457, 715, 1236, 1951, 3315, 5266, 8837, 14103, 23452, 37555, 62031, 99586, 163665, 263251, 431012, 694263, 1133467, 1827730, 2977581, 4805311, 7815660, 12620971, 20502167, 33123138, 53756377, 86879515, 140898036

Offset: 0

Clark Kimberling, Nov 29 2017

a(n)/a(n-1) -> (1 + sqrt(5))/2 = golden ratio (A001622), so that a( ) has the growth rate of the Fibonacci numbers (A000045).

Clark Kimberling, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1, 3, -2, -2)

Cf. A001622, A000045, A005672.

LinearRecurrence[{1, 3, -2, -2}, {0, 1, 2, 3}, 100]

a(n) = a(n-1) + a(n-3) + a(n-4), where a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 3.

G.f.: (x + x^2 - 2 x^3)/(1 - x - 3 x^2 + 2 x^3 + 2 x^4).

cp's OEIS Frontend

A054143 Triangular array T given by T(n,k) = Sum_{0 <= j <= i-n+k, n-k <= i <= n} C(i,j) for n >= 0 and 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A132890 Triangle read by rows: T(n,k) is the number of left factors of Dyck paths of length n that have height k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A079284 Diagonal sums of triangle A008949.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A295717 a(n) = a(n-1) + 3*a(n-2) -2*a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 5, a(3) = 7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A295718 a(n) = a(n-1) + 3*a(n-2) -2*a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 4, a(3) = 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A295719 a(n) = a(n-1) + 3*a(n-2) -2*a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 6, a(3) = 10.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A295720 a(n) = a(n-1) + 3*a(n-2) -2*a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 4, a(2) = 9, a(3) = 16.

Views

Author

Keywords

Comments

Links

Crossrefs

A295717 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 5, a(3) = 7.

A295718 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 4, a(3) = 5.

A295719 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 3, a(2) = 6, a(3) = 10.

A295720 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 1, a(1) = 4, a(2) = 9, a(3) = 16.

A295721 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = -1, a(1) = 2, a(2) = 3, a(3) = 4.

A295722 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = -1, a(1) = -1, a(2) = 2, a(3) = 3.

A295723 a(n) = a(n-1) + 3a(n-2) -2a(n-3) - 2*a(n-4), where a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 3.