Search: a114495 -id:a114495
|
| |
|
|
A236918
|
|
Triangle read by rows: Catalan triangle of the k-Fibonacci sequence.
|
|
+10
2
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,5
|
|
|
COMMENTS
|
|
|
|
LINKS
|
|
|
|
FORMULA
|
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
|
|
|
EXAMPLE
|
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;
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(SageMath)
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]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
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.)
|
|
+10
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
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).
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)
|
|
|
LINKS
|
|
|
|
FORMULA
|
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.
|
|
|
EXAMPLE
|
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;
|
|
|
MAPLE
|
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
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(Magma) /* 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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
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).
|
|
+10
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,6
|
|
|
COMMENTS
|
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).
|
|
|
LINKS
|
|
|
|
FORMULA
|
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.
|
|
|
EXAMPLE
|
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;
|
|
|
MAPLE
|
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Riordan array (f(x)/x, f(x)) where f(x) is the g.f. of A000958.
|
|
|
LINKS
|
|
|
|
FORMULA
|
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).
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.
|
|
|
EXAMPLE
|
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;
...
|
|
|
MAPLE
|
# Uses function PMatrix from A357368. Adds column 1, 0, 0, 0, ... to the left.
|
|
|
MATHEMATICA
|
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 *)
|
|
|
PROG
|
(SageMath)
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]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.009 seconds
|
