A101785 -id:A101785 - cp's OEIS frontend

A212382 Number A(n,k) of Dyck n-paths all of whose ascents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 5, 1, 1, 1, 1, 2, 14, 1, 1, 1, 1, 1, 5, 42, 1, 1, 1, 1, 1, 2, 12, 132, 1, 1, 1, 1, 1, 1, 6, 30, 429, 1, 1, 1, 1, 1, 1, 2, 16, 79, 1430, 1, 1, 1, 1, 1, 1, 1, 7, 37, 213, 4862, 1, 1, 1, 1, 1, 1, 1, 2, 22, 83, 584, 16796, 1

Offset: 0

Alois P. Heinz, May 12 2012

Lengths of descents are unrestricted.

For p>0 is column p asymptotic to a(n) ~ s^2 / (n^(3/2) * r^(n-1/2) * sqrt(2*Pi*p*(s-1)*(1+s/(1+p*(s-1))))), where r and s are real roots (0 < r < 1) of the system of equations r = p*(s-1)^2 / (s*(1-p+p*s)), (r*s)^p = (s-1-r*s)/(s-1). - Vaclav Kotesovec, Jul 16 2014

			A(0,k) = 1: the empty path.
A(3,0) = 1: UDUDUD.
A(3,1) = 5: UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD.
A(3,2) = 2: UDUDUD, UUUDDD.
A(5,3) = 6: UDUDUDUDUD, UDUUUUDDDD, UUUUDDDDUD, UUUUDDDUDD, UUUUDDUDDD, UUUUDUDDDD.
Square array A(n,k) begins:
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   1,  1,  1,  1,  1,  1,  1, ...
  1,   2,  1,  1,  1,  1,  1,  1, ...
  1,   5,  2,  1,  1,  1,  1,  1, ...
  1,  14,  5,  2,  1,  1,  1,  1, ...
  1,  42, 12,  6,  2,  1,  1,  1, ...
  1, 132, 30, 16,  7,  2,  1,  1, ...
  1, 429, 79, 37, 22,  8,  2,  1, ...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Vaclav Kotesovec, Asymptotic of subsequences of A212382

Columns k=0-10 give: A000012, A000108, A101785, A212383, A212384, A212385, A212386, A212387, A212388, A212389, A212390.

A(2n,n) gives A323229.

b:= proc(x, y, k, u) option remember;
      `if`(x<0 or y `if`(k=0, 1, b(n, n, k, true)):
seq(seq(A(n, d-n), n=0..d), d=0..15);
# second Maple program
A:= (n, k)-> `if`(k=0, 1, coeff(series(RootOf(
               A||k=1+x*A||k/(1-(x*A||k)^k), A||k), x, n+1), x, n)):
seq(seq(A(n, d-n), n=0..d), d=0..15);

b[x_, y_, k_, u_] := b[x, y, k, u] = If[x<0 || yJean-François Alcover, Jan 15 2014, translated from first Maple program *)

G.f. of column k>0 satisfies: A_k(x) = 1+x*A_k(x)/(1-(x*A_k(x))^k), g.f. of column k=0: A_0(x) = 1/(1-x).

G.f. of column k>0 is series_reversion(B(x))/x where B(x) = x/(1 + x + x^(k+1) + x^(2*k+1) + x^(3*k+1) + ... ) = x/(1+x/(1-x^k)); for Dyck paths with allowed ascent lengths {u_1, u_2, ...} use B(x) = x/( 1 + sum(k>=1, x^{u_k} ) ). - Joerg Arndt, Apr 23 2016

A365243 G.f. satisfies A(x) = 1 + xA(x)/(1 - x^3A(x)^2).

Original entry on oeis.org

1, 1, 1, 1, 2, 5, 11, 22, 45, 99, 226, 515, 1168, 2670, 6186, 14467, 33985, 80105, 189636, 451060, 1077225, 2580979, 6201602, 14942480, 36098349, 87417956, 212159347, 515937882, 1257048536, 3068146679, 7500995555, 18366760161, 45037590888, 110588510089

Offset: 0

Seiichi Manyama, Aug 28 2023

nonn

Cf. A101785, A106228, A112805.

a(n) = sum(k=0, n\3, binomial(n-2*k-1, k)*binomial(n-k+1, n-3*k)/(n-k+1));

a(n) = Sum_{k=0..floor(n/3)} binomial(n-2*k-1,k) * binomial(n-k+1,n-3*k)/(n-k+1).

A365693 G.f. satisfies A(x) = 1 + xA(x) / (1 - x^2A(x)^5).

Original entry on oeis.org

1, 1, 1, 2, 8, 30, 103, 368, 1407, 5531, 21905, 87689, 355929, 1461022, 6046160, 25194331, 105661615, 445692621, 1889454880, 8045796200, 34398989998, 147606568810, 635481458969, 2744158752772, 11882687400375, 51584960268914, 224465280616995, 978851595046223

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A101785, A365244, A365692.

Cf. A365691.

a(n) = sum(k=0, n\2, binomial(n-k-1, k)*binomial(n+3*k+1, n-2*k)/(n+3*k+1));

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1,k) * binomial(n+3*k+1,n-2*k) / (n+3*k+1).

A113337 Number of noncrossing partitions of [n] with all blocks of odd size and 1 and n in the same block.

Original entry on oeis.org

0, 1, 0, 1, 2, 4, 10, 26, 68, 183, 504, 1408, 3982, 11386, 32856, 95551, 279778, 824124, 2440440, 7260888, 21694352, 65066660, 195825872, 591217344, 1790081702, 5434311914, 16537576560, 50439949711, 154163497958, 472094359708, 1448302047274

Offset: 0

Louis Shapiro, Jan 07 2006

nonn

If we only require blocks of odd size we get A101785. If G is the o.g.f. for A101785 then the o.g.f. for this sequence is (G-1)/(x*G). [corrected by David Callan, Nov 14 2021]

For n>=1, a(n) is the number of Dyck paths of semilength n-1 in which the last descent is of even length and all other descents are of odd length. For example, a(1) = 1 counts the empty path and a(5) = 4 counts UUUUDDDD, UUDUDUDD, UDUUDUDD, UDUDUUDD. - David Callan, Nov 14 2021

			a(4)=4 with the 4 partitions being 125/3/4, 135/2/4, 145/2/3 and 12345.

G. C. Greubel, Table of n, a(n) for n = 0..1000
David Callan, Dyck path interpretation for sequences A101785, A113337 and A143017 in OEIS
Helmut Prodinger, Partial Dyck path interpretation for three sequences in the Encyclopedia of Integer Sequences, arXiv:2408.01290 [math.CO], 2024.

Cf. A101785.

[0,1,0] cat [(&+[2^(n-3*j)*Binomial(n-2,j-1)*Binomial(n-2*j-1, j-1)/j: j in [1..Floor(n/3)]]): n in [3..30]]; // G. C. Greubel, Apr 03 2019

Table[(-1)^n * Sum[((-1)^k*Binomial[n + k - 2, k - 1] * Binomial[2*n - 1, n - k] * Sum[Binomial[k, m] * (-1)^m * Sum[Binomial[n - j, -2*m + k + j - 1] * Binomial[n + 2*m - k - 2*j + 1, k - 1], {j, 2*m - k + 1, n}], {m, 0, n/2}])/k, {k, 1, n}], {n, 0, 30}] (* Vaclav Kotesovec, Sep 08 2016, after Vladimir Kruchinin *)
Join[{0, 1}, Table[Sum[2^(n-3*j)*Binomial[n-2, j-1]*Binomial[n-2*j-1, j- 1]/j, {j,1,Floor[n/3]}], {n,2,30}]] (* G. C. Greubel, Apr 03 2019 *)

a(n):=(-1)^n*sum(((-1)^k*binomial(n+k-2,k-1)*binomial(2*n-1,n-k)*sum(binomial(k,m)*(-1)^m*sum(binomial(n-j,-2*m+k+j-1)*binomial(n+2*m-k-2*j+1,k-1),j,2*m-k+1,n),m,0,n/2))/k,k,1,n); /* Vladimir Kruchinin, Sep 08 2016 */

a(n):=if n=1 then 1 else sum(2^(n-3*j)*binomial(n-2,j-1)*binomial(n-2*j-1,j-1)/j,j,1,floor((n)/3)); /* Vladimir Kruchinin, Apr 04 2019 */

a(n) = (-1)^n*sum(k=1, n, (-1)^k*binomial(n+k-2,k-1)*binomial(2*n-1,n-k)*sum(m=0,n/2, binomial(k,m)*(-1)^m*sum(j=2*m-k+1,n,(binomial(n-j,-2*m+k+j-1)*binomial(n+2*m-k-2*j+1,k-1))))/k); \\ Michel Marcus, Sep 08 2016

[0,1]+[sum(2^(n-3*j)*binomial(n-2,j-1)*binomial(n-2*j-1,j-1)/j for j in (1..floor(n/3))) for n in (2..30)] # G. C. Greubel, Apr 03 2019

a(n) = (-1)^n*Sum_{k=1..n} (((-1)^k*binomial(n+k-2,k-1)*binomial(2*n-1,n-k)*Sum_{m=0..n/2} (binomial(k,m)*(-1)^m*Sum_{j=2*m-k+1..n} (binomial(n-j,-2*m+k+j-1)*binomial(n+2*m-k-2*j+1,k-1))))/k). - Vladimir Kruchinin, Sep 08 2016
From Vaclav Kotesovec, Sep 08 2016: (Start)
Recurrence: 4*(n-1)*n*(91*n^2 - 543*n + 788)*a(n) = 6*(n-1)*(182*n^3 - 1359*n^2 + 3228*n - 2432)*a(n-1) - 4*(91*n^4 - 907*n^3 + 3119*n^2 - 4259*n + 1776)*a(n-2) + 12*(n-4)*(182*n^3 - 1359*n^2 + 3189*n - 2332)*a(n-3) - 5*(n-5)*(n-4)*(91*n^2 - 361*n + 336)*a(n-4).
a(n) ~ c * d^n / (sqrt(Pi) * n^(3/2)), where d = 3.2287049510945017293478492558... is the real root of the equation 5 - 24*d + 4*d^2 - 12*d^3 + 4*d^4 = 0 and c = 0.22436685378343740500658458471908821... is the positive real root of the equation -1 + 32*c^2 - 264*c^4 + 364*c^6 + 1820*c^8 = 0.
(End)
a(n) = Sum_{j=1..floor(n/3)} 2^(n-3*j)*C(n-2,j-1)*C(n-2*j-1,j-1)/j, a(1)=1. - Vladimir Kruchinin, Apr 04 2019

A143017 Number of {2-1-3, 2'^e-31}-avoiding permutations of size n (see definition in the Elizalde paper).

Original entry on oeis.org

1, 2, 4, 9, 22, 56, 147, 396, 1088, 3036, 8582, 24524, 70727, 205594, 601756, 1771937, 5245544, 15602496, 46606356, 139753120, 420520000, 1269361000, 3842722454, 11663928644, 35490451807, 108232655126, 330760284892

Offset: 1

Emeric Deutsch, Jul 17 2008

nonn

a(n) is the number of Dyck paths of semilength n for which all non-terminal descents are of odd length. For example, a(3) = 4 counts all 5 Dyck paths of semilength 3 except UUDDUD and a(4) = 9 counts, among others, UUUDUDDD and UUDUDUDD but not UUDDUUDD. - David Callan, Nov 13 2021

David Callan, Dyck path interpretation for sequences A101785, A113337 and A143017 in OEIS
S. Elizalde, Generating trees for permutations avoiding generalized patterns, arXiv:0707.4633 [math.CO], 2007; Annals of Combinatorics 11 (2007), 435-458.
Helmut Prodinger, Partial Dyck path interpretation for three sequences in the Encyclopedia of Integer Sequences, arXiv:2408.01290 [math.CO], 2024.

a:=proc(n) options operator, arrow: (sum(2*binomial(n,2*k)*binomial(n-k,k-1)+n*binomial(n,2*k+1)*binomial(n-k,k)/(n-k),k=0..floor((1/2)*n)))/n end proc: seq(a(n),n=1..27);

Table[1/n*Sum[2*Binomial[n,2k]*Binomial[n-k,k-1]+ n*Binomial[n,2k+1] *Binomial[n-k,k]/(n-k),{k,0,n-1}],{n,1,20}] (* Vaclav Kotesovec, Mar 20 2014 *)

a(n) = (1/n)*Sum_{k=0..floor(n/2)} 2*binomial(n,2k)*binomial(n-k,k-1) + n*binomial(n,2k+1)*binomial(n-k,k)/(n-k).
G.f. G(x) satisfies x*G^3 + (4x-2)*G^2 + (4x-1)*G + x = 0.
Conjecture: -8*n*(n+1)*a(n) + 4*n*(2*n+5)*a(n-1) + 4*n*(n+7)*a(n-2) + 2*(70*n^2-395*n+564)*a(n-3) + 2*(25*n^2-143*n+222)*a(n-4) + 4*(49*n-228)*(n-5)*a(n-5) - 45*(n-5)*(n-6)*a(n-6) = 0. - R. J. Mathar, Mar 14 2014
Recurrence (of order 4): 4*n*(n+1)*(91*n^2 - 217*n + 102)*a(n) = 6*n*(182*n^3 - 525*n^2 + 365*n - 78)*a(n-1) - 4*(91*n^4 - 399*n^3 - 136*n^2 + 990*n - 450)*a(n-2) + 12*(n-3)*(182*n^3 - 525*n^2 + 92*n + 140)*a(n-3) - 5*(n-4)*(n-3)*(91*n^2 - 35*n - 24)*a(n-4). - Vaclav Kotesovec, Mar 20 2014

A365692 G.f. satisfies A(x) = 1 + xA(x) / (1 - x^2A(x)^4).

Original entry on oeis.org

1, 1, 1, 2, 7, 23, 72, 238, 831, 2959, 10645, 38824, 143492, 535700, 2016020, 7641574, 29152015, 111841263, 431209723, 1669945778, 6493144143, 25338440143, 99204579648, 389570145288, 1534026813892, 6055885764548, 23962654178012, 95023123291680

Offset: 0

Seiichi Manyama, Sep 16 2023

nonn

Cf. A101785, A365244, A365693.

Cf. A365690.

a(n) = sum(k=0, n\2, binomial(n-k-1, k)*binomial(n+2*k+1, n-2*k)/(n+2*k+1));

a(n) = Sum_{k=0..floor(n/2)} binomial(n-k-1,k) * binomial(n+2*k+1,n-2*k) / (n+2*k+1).

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

Original entry on oeis.org

1, 1, 1, 3, 9, 25, 77, 247, 801, 2657, 8969, 30635, 105785, 368745, 1295493, 4582767, 16309953, 58357313, 209798289, 757461011, 2745281705, 9984464761, 36428252541, 133293594343, 489028250465, 1798543861537, 6629635284505

Offset: 0

Paul D. Hanna, Dec 16 2004

nonn

Formula may be derived using the Lagrange Inversion theorem (cf. A049124).

			Generated from Fibonacci polynomials (A011973) and coefficients of odd powers of 1/(1-x):
a(1) = 1*1/1
a(2) = 1*1/1 + 0*1*2/3
a(3) = 1*1/1 + 1*3*2/3
a(4) = 1*1/1 + 2*6*2/3 + 0*1*2^2/5
a(5) = 1*1/1 + 3*10*2/3 + 1*5*2^2/5
a(6) = 1*1/1 + 4*15*2/3 + 3*15*2^2/5 + 0*1*2^3/7
a(7) = 1*1/1 + 5*21*2/3 + 6*35*2^2/5 + 1*7*2^3/7
a(8) = 1*1/1 + 6*28*2/3 + 10*70*2^2/5 + 4*28*2^3/7 + 0*1*2^4/9
This process is equivalent to the formula:
a(n) = Sum_{k=0..[(n-1)/2]} C(n-k-1,k)*C(n,2*k)*2^k/(2*k+1).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A011973, A001045, A049124, A101785.

Flatten[{1,Table[Sum[Binomial[n-k-1,k]*Binomial[n,2*k]*2^k/(2*k+1),{k,0,Floor[(n-1)/2]}],{n,1,20}]}] (* Vaclav Kotesovec, Sep 17 2013 *)
ShiftedReversion[ser_, n_, sgn_] := CoefficientList[(sgn/x)InverseSeries[Series[x sgn ser, {x, 0, n}]],x];
Jacobsthal := (2x^2 - 1)/((x + 1)(2x - 1)); (* with A001045(0) = 1 *)
ShiftedReversion[Jacobsthal, 27, -1] (* Peter Luschny, Jan 10 2019 *)

{a(n)=if(n==0,1,sum(k=0,(n-1)\2, binomial(n-k-1,k)*binomial(n,2*k)*2^k/ (2*k+1)))}

a(n) = Sum_{k=0..[(n-1)/2]} C(n-k-1, k)*C(n, 2*k)*2^k/(2*k+1) for n>0, with a(0)=1.
G.f.: A(x) = (1/x)*Series_Reversion( x*(1 - 2*x^2)/(1+x - 2*x^2) ).
Recurrence: 2*n*(n+1)*(31*n^2 - 127*n + 120)*a(n) = 3*n*(62*n^3 - 285*n^2 + 359*n - 88)*a(n-1) + (62*n^4 - 378*n^3 + 1009*n^2 - 1425*n + 792)*a(n-2) + (n-3)*(682*n^3 - 3135*n^2 + 4133*n - 1272)*a(n-3) - 9*(n-4)*(n-3)*(31*n^2 - 65*n + 24)*a(n-4). - Vaclav Kotesovec, Sep 17 2013
a(n) ~ c*d^n/(sqrt(Pi)*n^(3/2)), where d = 3/4 + 1/(4*sqrt(3/(35 - (176*2^(2/3))/(9959 + 465*sqrt(465))^(1/3) + 2*(19918 + 930*sqrt(465))^(1/3)))) + 1/2*sqrt(35/6 + (44*2^(2/3))/(3*(9959 + 465*sqrt(465))^(1/3)) - (9959 + 465*sqrt(465))^(1/3)/(3*2^(2/3)) + 127/2*sqrt(3/(35 - (176*2^(2/3))/ (9959 + 465*sqrt(465))^(1/3) + 2*(19918 + 930*sqrt(465))^(1/3)))) = 3.9027270552404829297969 = ... is the root of the equation 9 - 22*d - 2*d^2 - 6*d^3 + 2*d^4 = 0 and c = 0.68546565145612597016100560323891887595749... - Vaclav Kotesovec, Sep 17 2013

A143950 Triangle read by rows: T(n,k) is the number of Dyck n-paths containing k even-length ascents (0 <= k <= floor(n/2)).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 5, 7, 2, 12, 20, 10, 30, 61, 36, 5, 79, 182, 133, 35, 213, 547, 488, 168, 14, 584, 1668, 1728, 756, 126, 1628, 5116, 6020, 3240, 750, 42, 4600, 15752, 20812, 13200, 3960, 462, 13138, 48709, 71376, 52030, 19360, 3267, 132, 37871, 151164

Offset: 0

Emeric Deutsch, Oct 05 2008

Row n contains 1 + floor(n/2) entries.
Row sums are the Catalan numbers (A000108).
T(n,0) = A101785(n).
Sum_{k=0..floor(n/2)} k*T(n,k) = A014301(n).
For the Dyck path statistic "number of odd-length ascents" see A096793.

			T(4,1)=7 because we have UDUD(UU)DD, UD(UU)DDUD, UD(UU)DUDD, (UU)DDUDUD, (UU)DUDDUD, (UU)DUDUDD and (UUUU)DDDD (the even-length ascents are shown between parentheses).
Triangle starts:
   1;
   1;
   1,  1;
   2,  3;
   5,  7,  2;
  12, 20, 10;
  30, 61, 36,  5;

Cf. A000108, A014301, A096793, A101785.

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

G.f. G=G(s,z) satisfies G = 1 + zG(1 + szG)/(1 - z^2*G^2).

The trivariate g.f. H=H(t,s,z), where t (s) marks odd-length (even-length) ascents satisfies H = 1 + zH(t+szH)/(1-z^2*H^2).

A365250 G.f. satisfies A(x) = 1 + xA(x)^3/(1 - x^2A(x)^6).

Original entry on oeis.org

1, 1, 3, 13, 67, 379, 2271, 14158, 90875, 596506, 3985661, 27018149, 185356123, 1284502886, 8978432666, 63225825415, 448131632123, 3194452061366, 22886882317758, 164718040282975, 1190311371951321, 8633251770618136, 62825467894307447

Offset: 0

Seiichi Manyama, Aug 28 2023

nonn

Cf. A101785, A365246.

Cf. A002293.

a[n_]:=Sum[Binomial[n-k-1,k]*Binomial[3*n+1,n-2*k],{k,0,Floor[n/2]}]/(3*n+1); Table[a[n],{n,0,22}] (* Robert P. P. McKone, Aug 29 2023 *)

a(n) = sum(k=0, n\2, binomial(n-k-1, k)*binomial(3*n+1, n-2*k))/(3*n+1);

a(n) = (1/(3*n+1)) * Sum_{k=0..floor(n/2)} binomial(n-k-1,k) * binomial(3*n+1,n-2*k).

cp's OEIS Frontend

A212382 Number A(n,k) of Dyck n-paths all of whose ascents have lengths equal to 1+k*m (m>=0); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A365693 G.f. satisfies A(x) = 1 + x*A(x) / (1 - x^2*A(x)^5).

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A113337 Number of noncrossing partitions of [n] with all blocks of odd size and 1 and n in the same block.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

Maxima

PARI

Sage

Formula

A143017 Number of {2-1-3, 2'^e-31}-avoiding permutations of size n (see definition in the Elizalde paper).

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A143950 Triangle read by rows: T(n,k) is the number of Dyck n-paths containing k even-length ascents (0 <= k <= floor(n/2)).

Views

Author

Keywords

Comments

A365243 G.f. satisfies A(x) = 1 + xA(x)/(1 - x^3A(x)^2).

A365693 G.f. satisfies A(x) = 1 + xA(x) / (1 - x^2A(x)^5).

A365692 G.f. satisfies A(x) = 1 + xA(x) / (1 - x^2A(x)^4).

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

A365250 G.f. satisfies A(x) = 1 + xA(x)^3/(1 - x^2A(x)^6).