A025250 -id:A025250 - cp's OEIS frontend

A107131 A Motzkin related triangle.

1, 0, 1, 0, 1, 1, 0, 0, 3, 1, 0, 0, 2, 6, 1, 0, 0, 0, 10, 10, 1, 0, 0, 0, 5, 30, 15, 1, 0, 0, 0, 0, 35, 70, 21, 1, 0, 0, 0, 0, 14, 140, 140, 28, 1, 0, 0, 0, 0, 0, 126, 420, 252, 36, 1, 0, 0, 0, 0, 0, 42, 630, 1050, 420, 45, 1, 0, 0, 0, 0, 0, 0, 462, 2310, 2310, 660, 55, 1

Offset: 0

Paul Barry, May 12 2005

Row sums are Motzkin numbers A001006. Diagonal sums are A025250(n+1).
Inverse binomial transform of Narayana number triangle A001263. - Paul Barry, May 15 2005
T(n,k)=number of Motzkin paths of length n with k steps U=(1,1) or H=(1,0). Example: T(3,2)=3 because we have HUD, UDH and UHD (here D=(1,-1)). T(n,k) = number of bushes with n+1 edges and k+1 leaves (a bush is an ordered tree in which the outdegree of each nonroot node is at least two). - Emeric Deutsch, May 29 2005
Row reverse of A055151. - Peter Bala, May 07 2012
Rows of A088617 are shifted columns of A107131, whose reversed rows are the Motzkin polynomials of A055151, which give the row polynomials (mod signs) of the o.g.f. that is the compositional inverse for an o.g.f. of the Fibonacci polynomials of A011973. The diagonals of A055151 give the rows of A088671, and the antidiagonals (top to bottom) of A088617 give the rows of A107131. The diagonals of A107131 give the columns of A055151. From the relation between A088617 and A107131, the o.g.f. of this entry is (1 - t*x - sqrt((1-t*x)^2 - 4*t*x^2))/(2*t*x^2). - Tom Copeland, Jan 21 2016

			Triangle begins
  1;
  0,  1;
  0,  1,  1;
  0,  0,  3,  1;
  0,  0,  2,  6,  1;
  0,  0,  0, 10, 10,   1;
  0,  0,  0,  5, 30,  15,   1;
  0,  0,  0,  0, 35,  70,  21,   1;
  0,  0,  0,  0, 14, 140, 140,  28,  1;
  0,  0,  0,  0,  0, 126, 420, 252, 36, 1;

Michael De Vlieger, Table of n, a(n) for n = 0..11475 (rows 0 <= n <= 150, flattened).
Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Consecutive patterns in restricted permutations and involutions, arXiv:1902.02213 [math.CO], 2019.
Paul Barry, On the duals of the Fibonacci and Catalan-Fibonacci polynomials and Motzkin paths, arXiv:2101.10218 [math.CO], 2021.
Paul Barry and A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.

Cf. A001006 (row sums), A025250 (diag. sums), A055151 (row reverse).

Cf. A001263, A011973, A025250, A055151, A088617, A088671, A107131.

[Binomial(n, 2*(n-k))*Catalan(n-k): k in [0..n], n in [0..13]]; // G. C. Greubel, May 22 2022

egf := exp(t*x)*hypergeom([],[2],t*x^2);
s := n -> n!*coeff(series(egf,x,n+2),x,n);
seq(print(seq(coeff(s(n),t,j),j=0..n)),n=0..9); # Peter Luschny, Oct 29 2014

T[n_, k_] := Binomial[k+1, n-k+1] Binomial[n, k]/(k+1);
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* Jean-François Alcover, Jun 19 2018 *)

flatten([[binomial(n, 2*(n-k))*catalan_number(n-k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, May 22 2022

Number triangle T(n, k) = binomial(k+1, n-k+1)*binomial(n, k)/(k+1).
T(n, k) = Sum_{j=0..n} (-1)^(n-j)C(n, j)*C(j+1, k)*C(j+1, k+1)/(j+1). - Paul Barry, May 15 2005
G.f.: G = G(t, z) satisfies G = 1 + t*z*G + t*z^2*G^2. - Emeric Deutsch, May 29 2005
Coefficient array for the polynomials x^n*Hypergeometric2F1((1-n)/2, -n/2; 2; 4/x). - Paul Barry, Oct 04 2008
From Paul Barry, Jan 12 2009: (Start)
G.f.: 1/(1-xy(1+x)/(1-x^2*y/(1-xy(1+x)/(1-x^2y/(1-xy(1+x).... (continued fraction).
T(n,k) = C(n, 2n-2k)*A000108(n-k). (End)

A346049 a(0) = ... = a(4) = 1; a(n) = Sum_{k=1..n-5} a(k) * a(n-k-5).

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 2, 3, 4, 4, 4, 6, 10, 16, 24, 30, 37, 50, 74, 116, 175, 245, 332, 456, 654, 981, 1471, 2146, 3056, 4320, 6203, 9119, 13540, 19986, 29134, 42113, 61047, 89398, 132021, 195272, 287547, 421235, 616418, 905161, 1335648, 1976407, 2922982, 4313230

Offset: 0

Ilya Gutkovskiy, Jul 02 2021

nonn

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

Cf. A025250, A307972, A343305, A346047, A346048.

a[0] = a[1] = a[2] = a[3] = a[4] = 1; a[n_] := a[n] = Sum[a[k] a[n - k - 5], {k, 1, n - 5}]; Table[a[n], {n, 0, 48}]
nmax = 48; A[] = 0; Do[A[x] = 1 + x + x^2 + x^3 + x^4 + x^5 A[x] (A[x] - 1) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

@CachedFunction
def a(n): # a = A346049
    if (n<5): return 1
    else: return sum(a(k)*a(n-k-5) for k in range(1,n-4))
[a(n) for n in range(51)] # G. C. Greubel, Nov 28 2022

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

A025273 a(n) = a(1)a(n-1) + a(2)a(n-2) + ...+ a(n-1)*a(1) for n >= 5, starting 1,0,1,1.

Original entry on oeis.org

1, 0, 1, 1, 2, 5, 12, 29, 72, 182, 466, 1207, 3158, 8334, 22158, 59299, 159614, 431838, 1173710, 3203244, 8774780, 24118522, 66497316, 183858411, 509670494, 1416231616, 3944027402, 11006186760, 30772507128, 86191006746, 241815195292, 679488418879

Offset: 1

Clark Kimberling

nonn

The binomial transform of A025250(n+1) is A025273(n+2). - Paul Barry, May 11 2005

Robert Israel, Table of n, a(n) for n = 1..2140
Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.

f:= gfun:-rectoproc({(n+1)*a(n) +2*(-2*n+1)*a(n-1) +4*(n-2)*a(n-2) +2*(-2*n+7)*a(n-3) +4*(n-5)*a(n-4)=0, a(0)=1,a(1)=0,a(2)=1,a(3)=1},a(n),remember):
map(f, [$0..50]); # Robert Israel, Nov 02 2016
# alternative
A025273 := proc(n)
    option remember ;
    if n < 5 then
        op(n,[1,0,1,1]) ;
    else
        add( procname(i)*procname(n-i),i=1..n-1) ;
    end if;
end proc:
seq(A025273(n),n=1..20) ; # R. J. Mathar, Jan 13 2025

nmax = 30; aa = ConstantArray[0,nmax]; aa[[1]] = 1; aa[[2]] = 0; aa[[3]] = 1; aa[[4]] = 1; Do[aa[[n]] = Sum[aa[[k]]*aa[[n-k]],{k,1,n-1}],{n,5,nmax}]; aa (* Vaclav Kotesovec, Jan 25 2015 *)
CoefficientList[Series[(1-Sqrt[1-4*x+4*x^2-4*x^3+4*x^4])/(2*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 01 2015 *)

G.f. (with offset 0 instead of 1): (1-sqrt(1-4*x+4*x^2-4*x^3+4*x^4))/(2*x). - Paul Barry, May 11 2005
Conjecture: (with offset 0 instead of 1) (n+1)*a(n) +2*(-2*n+1)*a(n-1) +4*(n-2)*a(n-2) +2*(-2*n+7)*a(n-3) +4*(n-5)*a(n-4)=0. - R. J. Mathar, Nov 24 2012
Conjecture follows from the differential equation 4*x^3-3*x^2+2*x-1+(-4*x^4+2*x^3-2*x+1)*g(x)+(4*x^5-4*x^4+4*x^3-4*x^2+x)*g'(x)=0 satisfied by the g.f. - Robert Israel, Nov 02 2016

A160565 Diagonal sums of number triangle [k<=n]*C(n,2n-2k)2^(n-k)A000108(n-k).

Original entry on oeis.org

1, 0, 1, 2, 1, 6, 9, 12, 41, 60, 121, 310, 505, 1162, 2577, 4760, 11089, 23256, 47089, 107274, 223345, 476366, 1061017, 2237796, 4888313, 10745748, 23048169, 50792638, 111180265, 241786898, 534219297

Offset: 0

Paul Barry, May 19 2009

Hankel transform is A160566(n+1).

a(0)=1 followed by A025252. [From R. J. Mathar, May 20 2009]

Cf.: A025250.

G.f.: (1-x^2-sqrt(1-2x^2-8x^3+x^4))/(4x^3);
G.f.: 1/(1-x^2-2*x^3/(1-x^2-2*x^3/(1-x^2-2*x^3/(1-x^2-2*x^3/(1-... (continued fraction).
a(n)=sum{k=0..floor(n/2), C(n-k,2n-4k)*2^(n-2k)*A000108(n-2k)};
a(n)=sum{k=0..n, C(n-k/2,2(n-k))*2^(n-k)*A000108(n-k)*(1+(-1)^k)/2};
a(n)=sum{k=0..n, C((n+k)/2,2k)*2^k*A000108(k)(1+(-1)^(n-k))/2}.
G.f.: (1/(1-x^2))c(2x^3/(1-x^2)^2) where c(x) is the g.f. of A000108. [From Paul Barry, May 20 2009]

A346047 a(0) = a(1) = a(2) = 1; a(n) = Sum_{k=1..n-3} a(k) * a(n-k-3).

Original entry on oeis.org

1, 1, 1, 0, 1, 2, 2, 2, 4, 8, 10, 13, 24, 42, 61, 90, 156, 265, 410, 646, 1093, 1834, 2948, 4789, 8050, 13475, 22129, 36570, 61435, 103039, 171384, 286156, 481691, 810502, 1359194, 2284789, 3856974, 6512001, 10982193, 18550116, 31406597, 53194727, 90082902

Offset: 0

Ilya Gutkovskiy, Jul 02 2021

nonn

Cf. A025250, A050253, A307970, A343304, A346048, A346049.

a[0] = a[1] = a[2] = 1; a[n_] := a[n] = Sum[a[k] a[n - k - 3], {k, 1, n - 3}]; Table[a[n], {n, 0, 42}]
nmax = 42; A[] = 0; Do[A[x] = 1 + x + x^2 + x^3 A[x] (A[x] - 1) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = 1 + x + x^2 + x^3 * A(x) * (A(x) - 1).

a(n) ~ sqrt((3 - 3*r^3 - 4*r^4 - 2*r^5)/(8*Pi)) / (n^(3/2) * r^(n+3)), where r = 0.5701490701528437821032230160646366013461622472504286581627... is the root of the equation 1 - 2*r^3 - 4*r^4 - 4*r^5 + r^6 = 0. - Vaclav Kotesovec, Jul 03 2021

A346048 a(0) = ... = a(3) = 1; a(n) = Sum_{k=1..n-4} a(k) * a(n-k-4).

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 2, 3, 3, 3, 5, 9, 15, 19, 24, 35, 59, 95, 137, 191, 280, 445, 706, 1071, 1575, 2357, 3663, 5755, 8890, 13483, 20518, 31759, 49658, 77267, 119135, 183523, 284793, 444883, 694798, 1080865, 1679142, 2616399, 4092497, 6408249, 10021176, 15657643

Offset: 0

Ilya Gutkovskiy, Jul 02 2021

nonn

Cf. A025250, A307971, A343304, A343305, A346047, A346049.

a:= proc(n) option remember; `if`(n<4, 1,
      add(a(j)*a(n-4-j), j=1..n-4))
    end:
seq(a(n), n=0..45);  # Alois P. Heinz, Jul 03 2021

a[0] = a[1] = a[2] = a[3] = 1; a[n_] := a[n] = Sum[a[k] a[n - k - 4], {k, 1, n - 4}]; Table[a[n], {n, 0, 45}]
nmax = 45; A[] = 0; Do[A[x] = 1 + x + x^2 + x^3 + x^4 A[x] (A[x] - 1) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = 1 + x + x^2 + x^3 + x^4 * A(x) * (A(x) - 1).

A160568 Diagonal sums of number triangle [k<=n]*C(n,2n-2k)3^(n-k)A000108(n-k).

Original entry on oeis.org

1, 0, 1, 3, 1, 9, 19, 18, 91, 165, 271, 990, 1765, 3843, 11467, 21630, 53299, 140724, 287119, 736101, 1818235, 3982044, 10225117, 24521409, 56584243, 143641017, 341948179, 816095982, 2045559205, 4888806237, 11897144767, 29540684052

Offset: 0

Paul Barry, May 19 2009

Hankel transform is A160569(n+1).

Cf.: A025250, A160565.

G.f.: (1-x^2-sqrt(1-2x^2-12x^3+x^4))/(6*x^3);
G.f.: 1/(1-x^2-3*x^3/(1-x^2-3*x^3/(1-x^2-3*x^3/(1-x^2-3*x^3/(1-... (continued fraction).
a(n)=sum{k=0..floor(n/2), C(n-k,2n-4k)*3^(n-2k)*A000108(n-2k)};
a(n)=sum{k=0..n, C(n-k/2,2(n-k))*3^(n-k)*A000108(n-k)*(1+(-1)^k)/2};
a(n)=sum{k=0..n, C((n+k)/2,2k)*3^k*A000108(k)(1+(-1)^(n-k))/2}.

A246181 Triangle read by rows: T(n,k) is the number of weighted lattice paths B(n) having k (1,0)-steps of weight 1. B(n) is the set of lattice paths of weight n that start in (0,0), end on the horizontal axis and never go below this axis, whose steps are of the following four kinds: a (1,0)-step of weight 1; a (1,0)-step of weight 2; a (1,1)-step of weight 2; a (1,-1)-step of weight 1. The weight of a path is the sum of the weights of its steps.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 3, 3, 0, 1, 3, 3, 6, 4, 0, 1, 3, 12, 6, 10, 5, 0, 1, 6, 14, 30, 10, 15, 6, 0, 1, 11, 30, 40, 60, 15, 21, 7, 0, 1, 15, 65, 90, 90, 105, 21, 28, 8, 0, 1, 31, 95, 225, 210, 175, 168, 28, 36, 9, 0, 1, 50, 216, 350, 595, 420, 308, 252, 36, 45, 10, 0, 1

Offset: 0

Emeric Deutsch, Aug 23 2014

Number of entries in row n is n+1.
Sum of entries in row n is A004148(n+1) (the 2ndary structure numbers).
T(n,0) = A025250(n+3).
Sum(k*T(n,k), k>=0) = A110320(n) (n>=1).

			Row 3 is 1,2,0,1. Indeed, denoting by h (H) the (1,0)-step of weight 1 (2), and u=(1,1), d=(1,-1), the four paths of weight 3 are: ud, hH, Hh, and hhh, having 0, 1, 1, and 3 (1,0)-steps of weight 1, respectively.
Triangle starts:
1;
0,1;
1,0,1;
1,2,0,1;
1,3,3,0,1;
3,3,6,4,0,1;

Alois P. Heinz, Rows n = 0..140, flattened
M. Bona and A. Knopfmacher, On the probability that certain compositions have the same number of parts, Ann. Comb., 14 (2010), 291-306.

Cf. A004148, A025250, A246177.

eq := G = 1+t*z*G+z^2*G+z^3*G^2: G := RootOf(eq, G): Gser := simplify(series(G, z = 0, 22)): for n from 0 to 17 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 15 do seq(coeff(P[n], t, k), k = 0 .. n) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, y) option remember; `if`(y<0 or y>n, 0,
      `if`(n=0, 1, expand(b(n-1, y)*x+ `if`(n>1,
       b(n-2, y)+b(n-2, y+1), 0) +b(n-1, y-1))))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..12); # Alois P. Heinz, Aug 24 2014

b[n_, y_] := b[n, y] = If[y<0 || y>n, 0, If[n==0, 1, Expand[b[n-1, y]*x + If[n>1, b[n-2, y] + b[n-2, y+1], 0] + b[n-1, y-1]]]]; T[n_] := Function[{p}, Table[ Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jun 29 2015, after Alois P. Heinz *)

G.f. G=G(t,z) satisfies G = 1 + t*z*G + z^2*G + z^3*G^2.

A247170 Expansion of (-3/2+(x^3+3x)/(sqrt(x^4-4x^3-2x^2+1)2*x)).

Original entry on oeis.org

0, 2, 3, 2, 10, 11, 21, 50, 66, 152, 275, 467, 988, 1717, 3283, 6386, 11560, 22556, 42465, 79832, 154122, 290039, 554323, 1060259, 2012310, 3859286, 7365423, 14072333, 26980788, 51580271, 98873291, 189567090, 363277676, 697348910

Offset: 1

Vladimir Kruchinin, Nov 21 2014

nonn

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A025250.

R:=PowerSeriesRing(Rationals(), 36); [0] cat Coefficients(R!( (-3/2+(x^3+3*x)/(Sqrt(x^4-4*x^3-2*x^2+1)*2*x)))); // Marius A. Burtea, Feb 11 2020

[n*&+[Binomial(k,n-2*k)*Binomial(n-k-1,k-1)/k:k in [1..n]]:n in [1..35]]; // Marius A. Burtea, Feb 11 2020

Table[n*Sum[(Binomial[k,n-2k]Binomial[n-k-1,k-1])/k,{k,n}],{n,40}] (* Harvey P. Dale, Oct 04 2017 *)

a(n):=n*sum((binomial(k,n-2*k)*binomial(n-k-1,k-1))/k,k,1,n);

a(n) = n*Sum_{k=1..n} binomial(k,n-2*k)*binomial(n-k-1,k-1)/k.
From R. J. Mathar, Jan 25 2020: (Start)
D-finite with recurrence: +3*n*a(n) +3*(n-1)*a(n-1) +(-5*n+2)*a(n-2) +(-17*n+25)*a(n-3) +(-11*n+34)*a(n-4) +(-3*n+25)*a(n-5) +(-3*n+20)*a(n-6) +(n-7)*a(n-7) = 0.
Conjectured: +n*(2*n-7)*a(n) +(n-1)*(2*n-9)*a(n-1) +2*(-2*n^2+9*n-6)*a(n-2) +2*(-6*n^2+33*n-38)*a(n-3) +3*(-2*n^2+15*n-26)*a(n-4) +(2*n-5)*(n-5)*a(n-5) = 0.
(End)

A361313 a(n) = a(1)a(n-1) + a(2)a(n-2) + ... + a(n-5)*a(5) for n >= 6, with a(1)=0 and a(2)=a(3)=a(4)=a(5)=1.

Original entry on oeis.org

0, 1, 1, 1, 1, 0, 1, 1, 2, 3, 4, 8, 11, 20, 31, 52, 88, 143, 247, 408, 700, 1184, 2017, 3462, 5909, 10196, 17518, 30281, 52365, 90704, 157556, 273742, 476893, 831298, 1451603, 2537736, 4441262, 7782934, 13650555, 23969794, 42126241, 74105773, 130476070

Offset: 1

J. Conrad, Mar 08 2023

Shifts left 5 places under the INVERT transform.

			a(11) = a(1)*a(10) + a(2)*a(9) + a(3)*a(8) + a(4)*a(7) + a(5)*a(6) = 0*3 + 1*2 + 1*1 + 1*1 + 1*0 = 4.

J. Conrad, Table of n, a(n) for n = 1..3000

Cf. A025250.

def A361313(l):
    s = [0, 1, 1, 1, 1][:l]
    for n in range(5, l):
        s.append(sum([s[k] * s[n-k-1] for k in range(n-4)]))
    return s

cp's OEIS Frontend

A107131 A Motzkin related triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A346049 a(0) = ... = a(4) = 1; a(n) = Sum_{k=1..n-5} a(k) * a(n-k-5).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

SageMath

Formula

A025273 a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-1)*a(1) for n >= 5, starting 1,0,1,1.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

Formula

A160565 Diagonal sums of number triangle [k<=n]*C(n,2n-2k)2^(n-k)A000108(n-k).

Views

Author

Keywords

Comments

Crossrefs

Formula

A346047 a(0) = a(1) = a(2) = 1; a(n) = Sum_{k=1..n-3} a(k) * a(n-k-3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A346048 a(0) = ... = a(3) = 1; a(n) = Sum_{k=1..n-4} a(k) * a(n-k-4).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

Formula

A160568 Diagonal sums of number triangle [k<=n]*C(n,2n-2k)3^(n-k)A000108(n-k).

Views

Author

Keywords

Comments

Crossrefs

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A247170 Expansion of (-3/2+(x^3+3*x)/(sqrt(x^4-4*x^3-2*x^2+1)*2*x)).

Views

Author

A025273 a(n) = a(1)a(n-1) + a(2)a(n-2) + ...+ a(n-1)*a(1) for n >= 5, starting 1,0,1,1.

A247170 Expansion of (-3/2+(x^3+3x)/(sqrt(x^4-4x^3-2x^2+1)2*x)).

A361313 a(n) = a(1)a(n-1) + a(2)a(n-2) + ... + a(n-5)*a(5) for n >= 6, with a(1)=0 and a(2)=a(3)=a(4)=a(5)=1.