A114495 -id:A114495 - cp's OEIS frontend

A236918 Triangle read by rows: Catalan triangle of the k-Fibonacci sequence.

1, 1, 1, 1, 2, 3, 1, 3, 7, 8, 1, 4, 12, 22, 24, 1, 5, 18, 43, 73, 75, 1, 6, 25, 72, 156, 246, 243, 1, 7, 33, 110, 283, 564, 844, 808, 1, 8, 42, 158, 465, 1092, 2046, 2936, 2742, 1, 9, 52, 217, 714, 1906, 4178, 7449, 10334, 9458, 1, 10, 63, 288, 1043, 3096, 7670, 15904, 27231, 36736, 33062

Offset: 1

N. J. A. Sloane, Feb 09 2014

Reversal of the Riordan array (f(x), x*f(x)) where f(x) is the g.f. of A000958. - Philippe Deléham, Feb 10 2014

Row sums are in A109262. - Philippe Deléham, Feb 10 2014

			Triangle begins:
  1;
  1,  1;
  1,  2,  3;
  1,  3,  7,   8;
  1,  4, 12,  22,   24;
  1,  5, 18,  43,   73,   75;
  1,  6, 25,  72,  156,  246,  243;
  1,  7, 33, 110,  283,  564,  844,   808;
  1,  8, 42, 158,  465, 1092, 2046,  2936,  2742;
  1,  9, 52, 217,  714, 1906, 4178,  7449, 10334,  9458;
  1, 10, 63, 288, 1043, 3096, 7670, 15904, 27231, 36736, 33062;
  ... - Extended by _Philippe Deléham_, Feb 10 2014

G. C. Greubel, Rows n = 1..50 of the triangle, flattened
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832.

Diagonals give A000958, A114495.

Cf. A109262 (row sums).

P[n_, x_]:= P[n,x]= If[n==0, 1, Sum[(j/(2*n-j))*Binomial[2*n-j, n-j]*Fibonacci[j, 1/x] *x^(n-1), {j,0,n}]];
T[n_, k_]:= Coefficient[P[n, x], x, k];
Table[T[n, k], {n,10}, {k, 0, n-1}]//Flatten (* G. C. Greubel, Jun 14 2022 *)

def f(n,x): return sum( binomial(n-j-1, j)*x^(n-2*j-1) for j in (0..(n-1)//2) )
def p(n,x):
    if (n==0): return 1
    else: return sum( (j/(2*n-j))*binomial(2*n-j, n-j)*x^(n-1)*f(j, 1/x) for j in (0..n) )
def A236918(n,k): return ( p(n,x) ).series(x, n+1).list()[k]
flatten([[A236918(n,k) for k in (0..n-1)] for n in (1..12)]) # G. C. Greubel, Jun 14 2022

T(n, k) = coefficient of [x^k]( p(n, x) ), where p(n, x) = Sum_{j=0..n} (j/(2*n-j))*binomial(2*n-j, n-j)*x^(n-1)*Fibonacci(j, 1/x) with p(0, x) = 1 and Fibonacci(n, x) are the Fibonacci polynomials. - G. C. Greubel, Jun 14 2022

More terms from Philippe Deléham, Feb 09 2014

A114494 Triangle read by rows: T(n,k) is number of hill-free Dyck paths of semilength n and having k returns to the x-axis. (A Dyck path is said to be hill-free if it has no peaks at level 1.)

Original entry on oeis.org

0, 1, 2, 5, 1, 14, 4, 42, 14, 1, 132, 48, 6, 429, 165, 27, 1, 1430, 572, 110, 8, 4862, 2002, 429, 44, 1, 16796, 7072, 1638, 208, 10, 58786, 25194, 6188, 910, 65, 1, 208012, 90440, 23256, 3808, 350, 12, 742900, 326876, 87210, 15504, 1700, 90, 1, 2674440, 1188640

Offset: 1

Emeric Deutsch, Dec 01 2005

Row 1 contains one term; row n contains floor(n/2) terms (n >= 2). Row sums are the Fine numbers (A000957). Column 1 yields the Catalan numbers (n >= 2). Sum_{k=1..floor(n/2)} k*T(n,k) = A114495(n).
From Colin Defant, Sep 15 2018: (Start)
Let theta_{n-1,k-1} be the permutation k(k-1)...1(k+1)(k+2)...(n-1) obtained by concatenating the decreasing string k...1 with the increasing string (k+1)...(n-1). T(n,k) is the number of preimages of theta_{n-1,k-1} under West's stack-sorting map.
If pi is any permutation of [n-1] with exactly k-1 descents, then |s^{-1}(pi)| <= T(n,k), where s denotes West's stack-sorting map. (End)

			T(5,2)=4 because we have UUD(D)UUDUD(D), UUD(D)UUUDD(D), UUDUD(D)UUD(D) and UUUDD(D)UUD(D), where U=(1,1), D=(1,-1) (returns to the axis are shown between parentheses).
Triangle starts:
    0;
    1;
    2;
    5,   1;
   14,   4;
   42,  14,   1;
  132,  48,   6;
  429, 165,  27,   1;

C. Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018.
C. Defant, Preimages under the stack-sorting algorithm, Graphs Combin., 33 (2017), 103-122.
C. Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Cf. A000957, A000108, A114495.

/* except 0 as triangle */ [[(k/(n-k))*Binomial(2*n-2*k, n-2*k): k in [1..n div 2]]: n in [2.. 15]]; // Vincenzo Librandi, Sep 15 2018

T:=proc(n,k) if k<=floor(n/2) then k*binomial(2*n-2*k,n-2*k)/(n-k) else 0 fi end: 0; for n from 2 to 15 do seq(T(n,k),k=1..floor(n/2)) od; # yields sequence in triangular form

Join[{0}, t[n_, k_]:=(k/(n - k)) Binomial [2 n - 2 k, n - 2 k]; Table[t[n, k], {n, 1, 20}, {k, n/2}]//Flatten] (* Vincenzo Librandi, Sep 15 2018 *)

T(n, k) = (k/(n-k))*binomial(2*n-2*k, n-2*k) (1 <= k <= floor(n/2)).

G.f.: 1/(1-tz^2*C^2)-1, where C=(1-sqrt(1-4z))/(2z) is the Catalan function.

A114626 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having k peaks at level 2; 0<= k<=n-1, n>=2 (a Dyck path is said to be hill-free if it has no peaks at level 1).

Original entry on oeis.org

0, 1, 1, 0, 1, 2, 2, 1, 1, 6, 6, 3, 2, 1, 19, 17, 12, 5, 3, 1, 61, 56, 36, 20, 8, 4, 1, 202, 185, 120, 66, 31, 12, 5, 1, 683, 624, 409, 224, 110, 46, 17, 6, 1, 2348, 2144, 1408, 784, 385, 172, 66, 23, 7, 1, 8184, 7468, 4920, 2760, 1380, 624, 257, 92, 30, 8, 1, 28855, 26317

Offset: 2

Emeric Deutsch, Dec 18 2005

Row n has n terms (n>=2). Row sums yield the Fine numbers (A000957). T(n,0)=A114627(n-3). Sum(kT(n,k),k=0..n-1)=A114495(n).

			T(5,2)=3 because we have U(UD)(UD)UUDDD, UUUDD(UD)(UD)D and U(UD)UUDD(UD)D, where U=(1,1), D=(1,-1) (the peaks at level 2 are shown between parentheses).
Triangle begins:
0,1;
1,0,1;
2,2,1,1;
6,6,3,2,1;
19,17,12,5,3,1;

Cf. A000957, A114627, A114495.

C:=(1-sqrt(1-4*z))/2/z: G:=(1+z-t*z-z*C)/(1+z+z^2-t*z-t*z^2-z*(1+z)*C): Gser:=simplify(series(G,z=0,15)): for n from 2 to 12 do P[n]:=coeff(Gser,z^n) od: for n from 2 to 12 do seq(coeff(t*P[n],t^j),j=1..n) od; # yields sequence in triangular form

G.f.=(1+z-tz-zC)/[1+z+z^2-tz-tz^2-z(1+z)C], where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

A237596 Convolution triangle of A000958(n+1).

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 8, 7, 3, 1, 24, 22, 12, 4, 1, 75, 73, 43, 18, 5, 1, 243, 246, 156, 72, 25, 6, 1, 808, 844, 564, 283, 110, 33, 7, 1, 2742, 2936, 2046, 1092, 465, 158, 42, 8, 1, 9458, 10334, 7449, 4178, 1906, 714, 217, 52, 9, 1, 33062, 36736, 27231, 15904, 7670, 3096, 1043, 288, 63, 10, 1

Offset: 0

Philippe Deléham, Feb 09 2014

Riordan array (f(x)/x, f(x)) where f(x) is the g.f. of A000958.
Reversal of A236918.
Row sums are A109262(n+1).
Diagonal sums are A033297(n+2).

			Triangle begins:
    1;
    1,   1;
    3,   2,   1;
    8,   7,   3,   1;
   24,  22,  12,   4,   1;
   75,  73,  43,  18,   5,  1;
  243, 246, 156,  72,  25,  6, 1;
  808, 844, 564, 283, 110, 33, 7, 1;
  ...

G. C. Greubel, Rows n = 0..50 of the triangle, flattened
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832.

Columns give A000958, A114495.

Cf. A033297 (diagonal sums), A109262 (row sums), A236918 (row reversal).

# Uses function PMatrix from A357368. Adds column 1,0,0,0,... to the left.
PMatrix(10, n -> A000958(n)); # Peter Luschny, Oct 19 2022

P[n_, x_]:= P[n, x]= If[n==0, 1, Sum[(j/(2*n-j))*Binomial[2*n-j, n-j]*Fibonacci[j, x], {j,0,n}]];
T[n_, k_] := Coefficient[P[n+1, x], x, k];
Table[T[n, k], {n,0,13}, {k,0,n}]//Flatten (* G. C. Greubel, Jun 14 2022 *)

def f(n,x): return sum( binomial(n-j-1, j)*x^(n-2*j-1) for j in (0..(n-1)//2) )
def p(n,x):
    if (n==0): return 1
    else: return sum( (j/(2*n-j))*binomial(2*n-j, n-j)*f(j, x) for j in (0..n) )
def A237596(n,k): return ( p(n+1,x) ).series(x, n+1).list()[k]
flatten([[A237596(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Jun 14 2022

G.f. for the column k-1: ((1-sqrt(1-4*x))^k/(1+sqrt(1-4*x) + 2*x)^k)/x.
Sum_{k=0..n} T(n,k) = A109262(n+1).
From G. C. Greubel, Jun 14 2022: (Start)
T(n, k) = coefficient of [x^k]( p(n+1, x) ), where p(n, x) = Sum_{j=0..n} (j/(2*n-j))*binomial(2*n-j, n-j)*Fibonacci(j, x) with p(0, x) = 1 and Fibonacci(n, x) are the Fibonacci polynomials.
T(n, k) = A236918(n, n-k). (End)

cp's OEIS Frontend

A236918 Triangle read by rows: Catalan triangle of the k-Fibonacci sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

SageMath

Formula

Extensions

A114494 Triangle read by rows: T(n,k) is number of hill-free Dyck paths of semilength n and having k returns to the x-axis. (A Dyck path is said to be hill-free if it has no peaks at level 1.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A114626 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having k peaks at level 2; 0<= k<=n-1, n>=2 (a Dyck path is said to be hill-free if it has no peaks at level 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A237596 Convolution triangle of A000958(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula