A091894 -id:A091894 - cp's OEIS frontend

A121448 Triangle read by rows: T(n,k) is the number of binary trees with n edges and having k vertices of outdegree 1 (n>=0, k>=0). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.

1, 0, 2, 1, 0, 4, 0, 6, 0, 8, 2, 0, 24, 0, 16, 0, 20, 0, 80, 0, 32, 5, 0, 120, 0, 240, 0, 64, 0, 70, 0, 560, 0, 672, 0, 128, 14, 0, 560, 0, 2240, 0, 1792, 0, 256, 0, 252, 0, 3360, 0, 8064, 0, 4608, 0, 512, 42, 0, 2520, 0, 16800, 0, 26880, 0, 11520, 0, 1024, 0, 924, 0, 18480, 0

Offset: 0

Emeric Deutsch, Jul 31 2006

T(2n,0) = binomial(2n,n)/(n+1) (the Catalan numbers; A000108); T(2n+1,0)=0. T(n,n)=2^n (A000079). Sum(k*T(n,k),k=0..n)=2*binomial(2n,n-1)=2*A001791(n). After deleting the zeros, reflection of A091894.
From Tom Copeland, Feb 07 2016: (Start)
A shifted o.g.f. is OG(x,t) = [1 - 2tx - sqrt[(1-2tx)^2-4x^2]] / (2x) = x + 2t x^2 + (1+4t^2) x^3 + ... with compositional inverse OGinv(x,t) =  x / (1 + 2tx + x^2), the shifted o.g.f. for A053117 (mod signs).
For x > 0 and choosing the positive square root, OG(x^2,t) = H(x,t) = x^2 + 2t x^4 + (1+4t^2) x^6 + ... has the compositional inverse Hinv(x,t) = sqrt[x / (1 + 2tx + x^2)] , which satisfies Hinv(H(x, t), t) = x, and which is the generating function for the Legendre polynomials (mod signs, cf. A008316) times sqrt(x).
In general, GB(x,t,b) =  [x / (1 - 2tx + x^2)]^b is a generator for the Gegenbauer polynomials times x^b for positive roots with compositional inverse about the origin GBinv(x,t,b) = OG(x^(1/b),-t) for x>0. Cf. A097610.
(End)
From Tom Copeland, Feb 09 2016: (Start)
z1 = OG(x,t) is the zero that vanishes for x=0 for the quadratic polynomial Q(z;z1(x,t),z2(x,t)) =(z-z1)(z-z2) = z^2 - (z1+z2) z + (z1*z2) = z^2 - e1 z + e2 = z^2 - [(1-2tx)/x] z + 1, where e1 and e2 are the elementary symmetric polynomials for two indeterminates.
The other zero is given by z2(x,t) = [1 - 2tx + sqrt[(1-2tx)^2-4x^2]] / (2x) = (1 - 2tx)/x - z1(x,t).
The two are zeros of the elliptic curve in Legendre normal form y^2 = z (z-z1)(z-z2). (Added Feb 13 2016. See Landweber et al., p 14. Cf. A097610.)
(End)

			T(2,2)=4 because, denoting by L (R) an edge going from a vertex to a left (right) child, we have the paths: LL, LR, RL and RR.
Triangle starts:
  1;
  0,2;
  1,0,4;
  0,6,0,8;
  2,0,24,0,16;

Colin Defant, Postorder Preimages, arXiv preprint arXiv:1604.01723 [math.CO], 2016.
FindStat - Combinatorial Statistic Finder, The number of vertices with out-degree 1 in a binary tree.
P. Landweber, D. Ravenel, and R. Stong, Periodic cohomology theories defined by elliptic curves

Cf. A000108, A000079, A001791, A091894.
Cf. A038207, A053117, A097610, A126120, A145271, A180874, A218272.
Cf. A008316.

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

nn=10;Drop[CoefficientList[Series[(1-2x y - ((-4x^2+(1-2x y)^2))^(1/2))/(2 x),{x,0,nn}],{x,y}],1]//Grid  (* Geoffrey Critzer, Feb 20 2013 *)

T(n,k) = 2^k*binomial(n+1,k)binomial(n+1-k,(n-k)/2)/(n+1) if n-k is even; otherwise, T(n,k) = 0. G.f. G=G(t,z) satisfies G=1+2tzG+z^2*G^2.
T(n,k) = 2^k*A097610(n,k). - Philippe Deléham, Aug 17 2006
From Tom Copeland, Feb 09 2016: (Start)
The following is from the formalism in A097610 with h1 = 2t, h2 = 1, and MT(n,h1,h2) = MT(n,2t,1) and with OG(x,t) defined above.
E.g.f.: M(x,t) = e^(2tx) AC(x) = exp[x MT(.,2t,1)] = exp[x P(.,t)], where AC(x) = I_1(2x)/x = Sum_{n>=0} x^(2n)/(n!(n+1)!) = exp(c.x) is the e.g.f. of A126120.
P(n,t) = MT(n,2t,1) = (c. + 2t)^n = Sum_{k=0..n} binomial(n,k) c(n-k) (2t)^k with c(k) = A126120(k). P(n,t+s) = (c. + 2t + 2s)^n = (P(.,t) + 2s)^n.
P(n,t) = t^n FC(n,c./t) = t^n (2 + c./t)^n, where FC(n,t) = (2 + t)^n are the face polynomials (vectors) of the hypercubes of A038207, i.e., the row polynomials of this entry can be obtained as the umbral composition of the reverse face polynomials with the aerated Catalan numbers of A000108.
The lowering and raising operators for the row polynomials P(n,t) of this entry are L = (1/2) d/dt = (1/2) D and R = 2t + dlog{AC(L)}/dL = 2t + Sum_{n>=0} b(n) L^(2n+1)/(2n+1)! = 2t + L - L^3/3! + 5 L^5/5! - ...  with b(n) = (-1)^n A180874(n+1).
Let CP(n,t) = P(n+1,t) with CP(0,t) = 0. Then the infinitesimal generator for CP(n,t) is g(x) d/dx with g(x) = 1 /[dOGinv(x,t)/dx] = x^2 / [(OGinv(x,t))^2 (1 - x^2)] = (1 + 2t x + x^2)^2 / (1 - x^2) so that [g(x)d/dx]^n/n! x evaluated at x = 0 gives the row polynomial CP(n,t), i.e., exp[x g(u)d/du] u |_(u=0) = OG(x,t) = 1 /[1 - x P(.,t)]. Cf. A145271.
g(x) = 1 + 4t x + (3+4t) x^2 + 8t x^3 + 4(1+t^2) x^4 + 8t x^5 + 4(1+t^2) x^6 + 8t x^7 + ... has the repeating coefficients of the vector V = (1, 4t, 3+4t, 8t, 4(1+t^2), 8t, 4(1+t^2), 8t, ...). Form the lower triangular matrix U with all ones on the diagonal and below. Multiply the n-th diagonal of U by V(n), giving the matrix VU with VU(n,k) = V(n-k). Then (1,0,0,0,..) [VU * DM]^n/n! (0,1,0,0,..)^T = CP(n,t) = P(n-1,t) for n>0 with DM being the matrix A218272 representing differentiation of a power series.
(End)

A125107 Subtract compositions (A011782) from Catalan numbers (A000108).

Original entry on oeis.org

0, 0, 0, 1, 6, 26, 100, 365, 1302, 4606, 16284, 57762, 205964, 738804, 2666248, 9678461, 35324902, 129579254, 477507628, 1767001046, 6563596132, 24465218444, 91480466488, 343055419346, 1289895758716, 4861929624236, 18367319517720, 69533483807140, 263747817532632

Offset: 0

Alford Arnold, Dec 15 2006

Apparently the number of Dyck n-paths with more than half of the path lying between the first and last peaks. - David Scambler, Sep 14 2012
From Peter Luschny, Nov 28 2024: (Start)
A Touchard walk T(n) of length n is, as defined by Dershowitz, "a sequence of n steps, each of which is one of N/S/E/W, such that at each point along the way the number of N-steps that have been taken is never less than the number of S-steps, and are in the end equal."
There are Sum_{k=0..n} binomial(n, k) Touchard walks that have no N/S-steps at all and since by Touchard's identity T(n) = Catalan(n+1), it follows that a(n) = T(n-1) - Sum_{k=0..n-1} binomial(n-1, k) = Catalan(n) - 2^(n-1) for n >= 1. Thus a(n+1) is the number of Touchard walks of length n that have at least one N-step. (End)

			A000108 begins 1 1 2 5 14 42 132 429 ...
A011782 begins 1 1 2 4  8 16  32  64 ...
so we get .... 0 0 0 1  6 26 100 365 ...
.
The 26 Touchard walks of length 4 that have at least one N-step are:
   NNSS, NSNS, NSEE, NSEW, NSWE, NSWW, NESE, NESW, NWSE,
   NWSW, NEES, NEWS, NWES, NWWS, ENSE, ENSW, WNSE, WNSW,
   ENES, ENWS, WNES, WNWS, EENS, EWNS, WENS, WWNS.

Nachum Dershowitz, Touchard's Drunkard, Journal of Integer Sequences, Vol. 20 (2017), #17.1.5.

Cf. A000079, A000108, A000110, A011782, A016098, A097805, A091894 (Touchard distribution), A377659 (similar with Motzkin).

# From Peter Luschny, Nov 28 2024: (Start)
a := n -> ifelse(n = 0, 0, binomial(2*n, n)/(n+1) - 2^(n-1)): seq(a(n), n = 0..28);
# Series expansion:
gf := (1 - sqrt(1 - 4*x)) / (2*x) - (1 - x) / (1 - 2*x): ser := series(gf, x, 30): seq(coeff(ser, x, n), n = 0..28);
# Evaluating polynomials:
p := (n, x) -> ifelse(n = 0, 0, 2^(n-1)*(hypergeom([1 - n/2, 1/2 - n/2], [2], x) - 1)): seq(subs(x = 1, expand(simplify(p(n, x)))), n = 0..28);  # (End)

Table[CatalanNumber[n] - If[n==0, 1, 2^(n-1)], {n, 0, 30}] (* David Scambler, Sep 14 2012 *)

# Generates the walks (for illustration only).
C = str.count
def aGen(n: int) -> Generator[str, Any, list[str]]:
    a = [""]
    if n <= 0: return a
    for w in a:
        if len(w) == n - 1:
            if C(w, "N") > 0 and C(w, "N") == C(w, "S"):
                yield w
        else:
            for j in "NSEW":
                U = w + j
                if C(U, "N") >= C(U, "S"):
                    a += [U]
    return a
for n in range(6): print([w for w in aGen(n)])  # Peter Luschny, Dec 03 2024

a(n) = A000108(n) - A011782(n).
(n+1)*a(n) + 2*(1-4*n)*a(n-1) + 4*(5*n-7)*a(n-2) + 8*(5-2*n)*a(n-3) = 0. - R. J. Mathar, Aug 10 2013
From Peter Luschny, Nov 28 2024: (Start)
a(n) = [x^n] (1 - sqrt(1 - 4*x)) / (2*x) - (1 - x) / (1 - 2*x).
a(n) = n! * [x^n] (exp(2*x)*(BesselI_{0}(2*x) - BesselI_{1}(2*x) - 1/2) - 1/2).
a(n) = p(n, 1) for n >= 1, where p(n, x) = 2^(n-1)*(hypergeom([1-n/2, (1-n)/2], [2], x) - 1).
a(n) = Sum_{k=0..n} (A091894(n, k) - A097805(n, n-k)). (End)

More terms from David Scambler, Sep 14 2012

A127529 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and jump-length equal to k (n >= 0, 0 <= k <= n-2).

Original entry on oeis.org

1, 1, 2, 4, 1, 8, 5, 1, 16, 17, 8, 1, 32, 49, 38, 12, 1, 64, 129, 141, 77, 17, 1, 128, 321, 453, 361, 143, 23, 1, 256, 769, 1326, 1399, 834, 247, 30, 1, 512, 1793, 3640, 4776, 3869, 1765, 402, 38, 1, 1024, 4097, 9539, 14911, 15353, 9722, 3469, 623, 47, 1, 2048, 9217

Offset: 0

Emeric Deutsch, Jan 18 2007

In the preorder traversal of an ordered tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump; the positive difference of the levels is called the jump distance; the sum of the jump distances in a given ordered tree is called the jump-length.
Rows 0 and 1 have one term each; row n (n >= 2) has n-1 terms.
Row sums are the Catalan numbers (A000108).
T(n,0) = A011782(n).
T(n,1) = A000337(n-2).
Sum_{k>=0} k*T(n,k) = binomial(2n-1, n-3) = A003516(n-1) for n >= 3.
The distribution of the statistic "number of jumps" is given in A091894. The average jump distance in all ordered trees with n edges is 2 - 5/(n+2) (i.e., about 2 levels for n large). The Krandick reference considers jump-length for full binary trees.
Also the number of Dyck n-paths with k valleys at height >= 1. - David Scambler, Sep 01 2011
Triangle T(n,k), with zeros omitted, given by (1,1,0,1,0,1,0,1,0,1,0,1,...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,1,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 06 2012

			Triangle starts:
   1;
   1;
   2;
   4,  1;
   8,  5,  1;
  16, 17,  8,  1;
  32, 49, 38, 12, 1;
Triangle (1,1,0,1,0,1,0,1,0,1, ...) DELTA (0,0,1,0,1,0,1,0,1,0,1,0,...) begins:
   1;
   1,   0;
   2,   0,   0;
   4,   1,   0,  0;
   8,   5,   1,  0,  0;
  16,  17,   8,  1,  0, 0;
  32,  49,  38, 12,  1, 0, 0;
  64, 129, 141, 77, 17, 1, 0, 0; ... - _Philippe Deléham_, Feb 06 2012

E. Deutsch, Dyck path enumeration, Discrete Math., 204, 1999, 167-202 (see Table 2).
FindStat - Combinatorial Statistic Finder, The number of valleys not on the x-axis of a Dyck path.
W. Krandick, Trees and jumps and real roots, J. Computational and Applied Math., 162, 2004, 51-55.

Cf. A000108, A000337, A003516, A011782, A091894.

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

n = 12; g[t_, z_] := 1/2/(1 - 2z - t + t*z)*(-2t + 1 + t*z - z + Sqrt[-2t*z + 1 - 2z + t^2*z^2 - 2t*z^2 + z^2]); Flatten[ CoefficientList[#, t]&  /@ CoefficientList[ Simplify[Series[g[t, z], {z, 0, n}]], z]] (* Jean-François Alcover, Jul 22 2011, after g.f. *)

T(n,m):=if n=0 and m=0 then 1 else if n=0 then 0 else sum(k*binomial(n,m+k)*binomial(n-k-1,m),k,0,n-m)/(n); /* Vladimir Kruchinin, Oct 29 2020 */

G.f.: G=G(t,z) satisfies (1 - t - 2*z + t*z)*G^2 - (1 - 2*t - z + t*z)*G - t = 0.

T(n,m) = Sum_{k=0..n-m} k*C(n,m+k)*C(n-k-1,m)/n, n>0, T(0,0)=1. - Vladimir Kruchinin, Oct 29 2020

A152225 Number of Dyck paths of semilength n with no peaks at height 0 (mod 3) and no valleys at height 2 (mod 3).

Original entry on oeis.org

1, 1, 2, 4, 9, 22, 56, 146, 388, 1048, 2869, 7942, 22192, 62510, 177308, 506008, 1451866, 4185788, 12119696, 35227748, 102753800, 300672368, 882373261, 2596389190, 7658677856, 22642421206, 67081765932, 199128719896, 592179010350, 1764044315540, 5263275015120

Offset: 0

Majun (majun(AT)math.sinica.edu.tw), Nov 29 2008

nonn

The antidiagonal sums of A091894 equal this sequence. - Johannes W. Meijer, Sep 13 2012

Robert Israel, Table of n, a(n) for n = 0..2025
Jean-Luc Baril, Sergey Kirgizov, and Armen Petrossian, Forests and pattern-avoiding permutations modulo pure descents, Permutation Patterns 2017, Reykjavik University, Iceland, June 26-30, 2017. See Section 5.
Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
Shu-Chung Liu, Jun Ma, and Yeong-Nan Yeh, Dyck Paths with Peak- and Valley-Avoiding Sets, Stud. Appl Math. 121 (3) (2008) 263-289.

Cf. A091561, A025265, A025247. - R. J. Mathar, Dec 03 2008

f:= gfun:-rectoproc({(n+2)*a(n) - 2*(2*n+1)*a(n-1) + 4*(n-1)*a(n-2) + 2*(5-2*n)*a(n-3)=0,a(0)=1,a(1)=1,a(2)=2,a(3)=4},a(n),remember):
map(f, [$0..40]); # Robert Israel, Jan 09 2018

CoefficientList[Series[(1 - 2 x + 2 x^2 - Sqrt[1 - 4 x + 4 x^2 - 4 x^3])/(2 x^2), {x, 0, 30}], x] (* Michael De Vlieger, Jan 09 2018 *)

G.f.: (1 - 2*x + 2*x^2 - sqrt(1 - 4*x + 4*x^2 - 4*x^3))/(2*x^2).
Conjecture: (n+2)*a(n) - 2*(2*n+1)*a(n-1) + 4*(n-1)*a(n-2) + 2*(5-2*n)*a(n-3)=0. - R. J. Mathar, Aug 14 2012
This conjecture follows from the differential equation (4*x^4-4*x^3+4*x^2-x)*y' + (2*x^3-4*x^2+6*x-2)*y - 2*x^3+2*x^2-3*x+2=0 satisfied by the g.f. - Robert Israel, Jan 09 2018

Edited by Emeric Deutsch, Dec 20 2008

A236406 Triangle read by rows: number of (1-2-3)-avoiding permutations on n letters with k peaks.

Original entry on oeis.org

1, 1, 2, 3, 2, 4, 10, 5, 32, 5, 6, 84, 42, 7, 198, 210, 14, 8, 438, 816, 168, 9, 932, 2727, 1152, 42, 10, 1936, 8250, 5940, 660, 11, 3962, 23276, 25630, 5775, 132, 12, 8034, 62400, 97812, 37180, 2574, 13, 16200, 160953, 341224, 196625, 27456, 429, 14, 32556, 402906, 1111656, 905086, 212212, 10010

Offset: 0

N. J. A. Sloane, Jan 31 2014

This is a convolution of A091156 with itself (see the Pudwell link below).

			Triangle begins:
   1;
   1;
   2;
   3,    2;
   4,   10;
   5,   32,    5;
   6,   84,   42;
   7,  198,  210,   14;
   8,  438,  816,  168;
   9,  932, 2727, 1152,  42;
  10, 1936, 8250, 5940, 660;
  ...

Alois P. Heinz, Rows n = 0..120, flattened
A. M. Baxter, Refining enumeration schemes to count according to permutation statistics, arXiv preprint arXiv:1401.0337 [math.CO], 2014.
M. Bukata, R. Kulwicki, N. Lewandowski, L. Pudwell, J. Roth, and T. Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv preprint arXiv:1812.07112 [math.CO], 2018.
L. Pudwell, On the distribution of peaks (and other statistics), 2018.

Row sums give A000108.

Cf. A091894, A276666.

m = maxExponent = 15;
G = -(-2 z^3 q^2 + 4z^3 q - 2z^3 - 2z^2 q + 2z^2 - 1 + Sqrt[-4z^2 q + 4z^2 - 4z + 1])/(2z (z q - z + 1)^2);
CoefficientList[# + O[q]^m, q]& /@ CoefficientList[G + O[z]^m, z]// Flatten (* Jean-François Alcover, Aug 06 2018 *)

T(2*n+2,n) = A276666(n+2) = (n+1)*A000108(n+2). - Alois P. Heinz, Apr 27 2018

G.f.: G(q,z) = - (-2z^3q^2+4z^3q-2z^3-2z^2q+2z^2-1+sqrt(-4z^2q+4z^2-4z+1))/(2z(zq-z+1)^2). (See the Pudwell link above.)

More terms from Alois P. Heinz, Apr 26 2018

A319252 Triangle read by rows: T(n,k) is the number of permutations pi of [n] with k+1 valleys such that s(pi) avoids the patterns 132, 231, 312, and 321, where s denotes West's stack-sorting map (0 <= k <= floor((n-1)/2)).

Original entry on oeis.org

1, 2, 4, 2, 8, 10, 16, 36, 4, 32, 112, 36, 64, 320, 200, 10, 128, 864, 880, 130, 256, 2240, 3360, 980, 28, 512, 5632, 11648, 5600, 476, 1024, 13824, 37632, 26880, 4536, 84, 2048, 33280, 115200, 114240, 31920, 1764

Offset: 1

Colin Defant, Sep 15 2018

T(n,k) is the number of permutations of [n] that avoid the patterns 1342, 2341, 3142, 3241, 3412, and 3421 and have k+1 valleys.

			Triangle begins:
   1;
   2;
   4,   2;
   8,  10;
  16,  36,  4;
  32, 112, 36;
  ...

C. Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

Row sums give A071721. Cf. A091894, A319251.

Flatten[Table[Table[(2^(n - 2 (m + 1) + 1)) Binomial[n - 1, 2 m] CatalanNumber[m] + Sum[Sum[(2^((n - i - 1) - 2 j + 1)) Binomial[n - i - 2, 2 j - 2] CatalanNumber[j - 1] (2^(i - 2 (m - j + 1) + 1)) Binomial[i - 1, 2 (m - j + 1) - 2] CatalanNumber[m - j], {j, 1, m}], {i, 1, n - 2}], {m, 0, Floor[(n - 1)/2]}], {n, 1, 12}]]

T(n,k) = V(n,k+1) + Sum_{i=1..n-2} Sum_{j=1..m} V(n-i-1,j) * V(i,k-j+1), where V(i,j) = 2^{i-2j+1} * (1/j) * binomial(i-1,2j-2) * binomial(2j-2,j-1) are the numbers given in A091894.

A377443 Triangular array T(n,k) read by rows, satisfies A377441(n, k+2) = Sum_{m=0..k} T(k, m)*n^m.

Original entry on oeis.org

2, 5, 1, 14, 6, 1, 42, 27, 8, 1, 132, 111, 45, 10, 1, 429, 441, 222, 67, 12, 1, 1430, 1728, 1029, 382, 93, 14, 1, 4862, 6733, 4608, 2005, 599, 123, 16, 1, 16796, 26181, 20199, 10018, 3495, 881, 157, 18, 1, 58786, 101763, 87270, 48445, 19188, 5641, 1236, 195, 20, 1

Offset: 0

Thomas Scheuerle, Nov 04 2024

			Triangle T(n, k) starts:
[0]     2
[1]     5,      1
[2]    14,      6,     1
[3]    42,     27,     8,     1
[4]   132,    111,    45,    10,     1
[5]   429,    441,   222,    67,    12,    1
[6]  1430,   1728,  1029,   382,    93,   14,    1
[7]  4862,   6733,  4608,  2005,   599,  123,   16,   1
[8] 16796,  26181, 20199, 10018,  3495,  881,  157,  18,  1
[9] 58786, 101763, 87270, 48445, 19188, 5641, 1236, 195, 20, 1

Cf. A377441, A377442.
Cf. A254316 (row sums).
Cf. A000108, A091894, A175136, A371965.

A377441(n, max_k) = Vec(-2*((n+1)*x-1)/((x-1)*(n*x-1)+((n*x^2-(n+1)*x+1)^2-4*x*(x-1)*((n+1)*x-1)+O(x^max_k))^(1/2)))
T(n, k) = Vec(A377441(y, n+5)[n+3])[n-k+1]

A091894(n, k) = 2^(n-2*k-1)*binomial(n-1, 2*k)*(binomial(2*k, k)/(k + 1))
A175136(n, k) = sum(m=0,(n - k)/2,A091894(n-k, m)*binomial(n-m-1, n-k))
T(n, k) = sum(m=1, n+1-k, A175136(n+2-k, n-m+2-k)*binomial(m+k-1, m-1))+(k==0)

G.f.: (-(y*x^3-(y+1)*x^2+2*x+1) + sqrt((y*x^3-(y+1)*x^2+x)^2 - 4*(x^3-x^2)*((y+1)*x^2-x)))/(2*(x^3-x^2))/x^2.
T(n, 0) = A000108(n+2).
T(n, 1) = A371965(n+2).
T(n, 2) G.f.: x^2*1/( (x - 1)^2*(1 - 4*x)^(3/2) ).
T(n, 3) G.f.: x^3*(3*x - 1)/( (x - 1)^3*(1 - 4*x)^(5/2) ).
T(n, 4) G.f.: x^4*(x^3 + (3*x - 1)^2)/( (x - 1)^4*(1 - 4*x)^(7/2) ).
T(n, 5) G.f.: x^5*(3*x^3*(3*y - 1) + (3*x - 1)^3)/( (x - 1)^5*(1 - 4*x)^(9/2) ).
T(n, 6) G.f.: x^6*(2*x^6 + 6*x^3*(3*x - 1)^2 + (3*x - 1)^4)/( (x - 1)^6*(1 - 4*x)^(11/2) ).
T(n, 7) G.f.: x^7*(10*x^6*(3*x - 1) + 10*x^3*(3*x - 1)^3 + (3*x - 1)^5)/( (x - 1)^7*(1 - 4*x)^(13/2) ).
0 = Sum_{n=0..k} T(n+k, n)*(-1)^n*binomial(k, n).
The diagonal k terms below main diagonal has G.f.: 1 + Sum_{m=1..k+1} A175136(k+2, k-m+2)*(1 - x)^k.
T(n+k, n) = Sum_{m=1..k+1} A175136(k+2, k-m+2)*binomial(m+n-1, m-1), for k > 0.

A319030 Triangle read by rows: T(n,k) is the number of permutations pi of [n] such that pi has k+1 valleys and s(pi) avoids the patterns 132 and 321, where s is West's stack-sorting map (0 <= k <= floor((n-1)/2)).

Original entry on oeis.org

1, 2, 4, 2, 8, 14, 16, 64, 8, 32, 240, 92, 64, 800, 624, 34, 128, 2464, 3248, 534, 256, 7168, 14336, 4736, 144, 512, 19968, 56448, 31200, 2852, 1024, 53760, 204288, 169920, 31120, 604, 2048, 140800, 692736, 808896, 247280, 14412

Offset: 1

Colin Defant, Sep 10 2018

Row sums give A319028.

			Triangle begins:
    1,
    2,
    4,    2,
    8,   14,
   16,   64,    8,
   32,  240,   92,
   64,  800,  624,  34,
  128, 2464, 3248, 534,
  ...

Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

Cf. A319028, A091894.

DeleteCases[Flatten[CoefficientList[Series[(1 - 2 x - Sqrt[(1 - 2 x)^2 - 4 x^2 y])/(2 x*y) + x^3*y (D[(1 - 2 x - Sqrt[(1 - 2 x)^2 - 4 x^2 y])/(2 x*y), x])^2, {x, 0, 10}], {x, y}]], 0]

G.f.: G(x,y) + x^3*y*((d/dx)G(x,y))^2, where G(x,y) = (1 - 2x - sqrt((1-2x)^2 - 4x^2*y))/(2x*y) is the generating function of A091894.

A118929 a(n) = Sum_{k=0..[n/2]} 2^(n-2k-1)C(n-1,2k)C(2k,k)/(k+1)a(k), with a(0)=1.

Original entry on oeis.org

1, 1, 2, 5, 14, 44, 152, 569, 2270, 9524, 41576, 187432, 868144, 4117216, 19945408, 98523013, 495521686, 2534420852, 13167361256, 69417635240, 370991119792, 2008036459744, 10997771773888, 60896581502800, 340633178891872

Offset: 0

Paul D. Hanna, May 06 2006

nonn

Invariant column vector V under matrix product A091894*V = V: a(n) = Sum_{k=0,[n/2]} A091894(n,k)*a(k), where A091894(n,k) = number of Dyck paths of semilength n, having k ddu's [here u=(1,1) and d=(1,-1)].

Cf. A091894.

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

A274883 Triangle read by rows, T(n,k) = 2^kbinomial(n,k)A057977(n-k) for n>=0 and 0<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 4, 4, 3, 6, 12, 8, 2, 24, 24, 32, 16, 10, 20, 120, 80, 80, 32, 5, 120, 120, 480, 240, 192, 64, 35, 70, 840, 560, 1680, 672, 448, 128, 14, 560, 560, 4480, 2240, 5376, 1792, 1024, 256, 126, 252, 5040, 3360, 20160, 8064, 16128, 4608, 2304, 512

Offset: 0

Peter Luschny, Jul 14 2016

			Triangle starts:
                       1;
                      1, 2;
                    1, 4, 4;
                  3, 6, 12, 8;
               2, 24, 24, 32, 16;
            10, 20, 120, 80, 80, 32;
         5, 120, 120, 480, 240, 192, 64;
     35, 70, 840, 560, 1680, 672, 448, 128;
14, 560, 560, 4480, 2240, 5376, 1792, 1024, 256;

Cf. A000079 (T(n,n)), A057977 (T(n,0)), A077587 (row sum).

Cf. A189912. Row reversed A091894 is a subtriangle.

T := (n,k) -> 2^k*binomial(n,k)*((n-k)!/floor((n-k)/2)!^2)/(floor((n-k)/2)+1);
seq(seq(T(n,k), k=0..n), n=0..9);

cp's OEIS Frontend

A121448 Triangle read by rows: T(n,k) is the number of binary trees with n edges and having k vertices of outdegree 1 (n>=0, k>=0). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A125107 Subtract compositions (A011782) from Catalan numbers (A000108).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A127529 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and jump-length equal to k (n >= 0, 0 <= k <= n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

Formula

A152225 Number of Dyck paths of semilength n with no peaks at height 0 (mod 3) and no valleys at height 2 (mod 3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A236406 Triangle read by rows: number of (1-2-3)-avoiding permutations on n letters with k peaks.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A319252 Triangle read by rows: T(n,k) is the number of permutations pi of [n] with k+1 valleys such that s(pi) avoids the patterns 132, 231, 312, and 321, where s denotes West's stack-sorting map (0 <= k <= floor((n-1)/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A377443 Triangular array T(n,k) read by rows, satisfies A377441(n, k+2) = Sum_{m=0..k} T(k, m)*n^m.

Views

Author

Keywords

Examples

A118929 a(n) = Sum_{k=0..[n/2]} 2^(n-2k-1)C(n-1,2k)C(2k,k)/(k+1)a(k), with a(0)=1.

A274883 Triangle read by rows, T(n,k) = 2^kbinomial(n,k)A057977(n-k) for n>=0 and 0<=k<=n.