A100754 -id:A100754 - cp's OEIS frontend

A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n nodes having root of even degree.

0, 1, 0, 1, 2, 6, 18, 57, 186, 622, 2120, 7338, 25724, 91144, 325878, 1174281, 4260282, 15548694, 57048048, 210295326, 778483932, 2892818244, 10786724388, 40347919626, 151355847012, 569274150156, 2146336125648, 8110508473252, 30711521221376

Offset: 0

N. J. A. Sloane

Row-sum of signed Catalan triangle A009766. - Wouter Meeussen
There are two schools of thought about the best indexing for these numbers. Deutsch and Shapiro have a(4) = 6 whereas here a(5) = 6. The formulas given here use both labelings.
From D. G. Rogers, Oct 18 2005: (Start)
I notice that you have some other zero-one evaluations of binary bracketings (such as A055395). But if you have an operation # with 0#0 = 1#0 = 1, 0#1 = 1#1 = 0, and look at the number of bracketings of a string of n 0's that come out 0, you get another instance of the Fine numbers.
For Z = 1 + x(ZW + WW) = 1 + x CW and W = x(ZZ + ZW) = xZC. Hence Z = 1 + xxCCZ, the functional equational for the g.f. of the Fine numbers. Indeed, C = Z + W = Z + xCZ.
In terms of rooted planar trees with root of even degree, this says that of all rooted planar trees, some have root of even degree (Z) and some have root of odd degree (xCZ). (End)
Hankel transform of a(n+1) = [1,0,1,2,6,18,57,186,...] is A000012 = [1,1,1,1,1,...]. - Philippe Deléham, Oct 24 2007
Starting with offset 3 = iterates of M * [1,0,0,0,...] where M = a tridiagonal matrix with [0,2,2,2,...] as the main diagonal and [1,1,1,...] as the super and subdiagonals. - Gary W. Adamson, Jan 09 2009
Starting with 1 and convolved with A068875 = the Catalan numbers with offset 1. - Gary W. Adamson, May 01 2009
For a relation to non-crossing partitions of the root system A_n, see A100754. - Tom Copeland, Oct 19 2014
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x) = [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)] = (x-2x^2)/(1-x)^2, and Fin(Cinv(x)) = P(x).
Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)] = (x-x^2) / (1 + x - x^2).
Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].
(End)
a(n+1) is the number of Dyck paths of semilength n avoiding UD at Level 0. For n = 3 the a(4) = 2 such Dyck paths are UUUDDD and UUDUDD. - Ran Pan, Sep 23 2015
For n >= 3, a(n) is the number of permutations pi of [n-2] such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - Colin Defant, Sep 16 2018
Named after the American scientist Terrence Leon Fine (1939-2021). - Amiram Eldar, Jun 08 2021

			G.f. = x + x^3 + 2*x^4 + 6*x^5 + 18*x^6 + 57*x^7 + 186*x^8 + 622*x^9 + 2120*x^10 + ...

Emeric Deutsch and Louis W. Shapiro, Seventeen Catalan identities, Bull. Instit. Combin. Applic., Vol. 31 (2001), pp. 31-38.
Ki Hang Kim, Douglas G. Rogers and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013). - N. J. A. Sloane, Jun 05 2012
Louis W. Shapiro and Carol J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1670 (first 201 terms from T. D. Noe)
Francesca Aicardi, Fuss-Catalan Triangles, arXiv:2310.07317 [math.CO], 2023.
Martin Aigner, Enumeration via ballot numbers, Discrete Math., 308 (2008), 2544-2563.
M. Albert, R. Aldred, M. Atkinson, C Handley, D. Holton, D. McCaughan and H. van Ditmarsch, Sorting Classes, Elec. J. of Comb., Vol. 12 (2005), R31.
Elena Barcucci, Elisa Pergola, Renzo Pinzani and Simone Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, 46 (2001).
Jean-Luc Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, Vol. 18 (2011), #P178.
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 4.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Paul Barry, Series reversion with Jacobi and Thron continued fractions, arXiv:2107.14278 [math.NT], 2021.
Paul Barry, Moment sequences, transformations, and Spidernet graphs, arXiv:2307.00098 [math.CO], 2023.
Paul Barry, The Triple Riordan Group, arXiv:2412.05461 [math.CO], 2024. See pp. 6, 10.
George Beck and Karl Dilcher, A Matrix Related to Stern Polynomials and the Prouhet-Thue-Morse Sequence, arXiv:2106.10400 [math.CO], 2021.
Rachael Boyd and Richard Hepworth, Combinatorics of injective words for Temperley-Lieb algebras, arXiv:2006.04261 [math.AT], 2020.
Naiomi Tuere Cameron, Random walks, trees and extensions of Riordan group techniques, Dissertation, Howard University, 2002.
Naiomi T. Cameron and Jillian E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19 (2016), #16.6.1.
Peter J. Cameron, Some sequences of integers, Discrete Math., Vol. 75, No. 1-3 (1989), pp. 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., Vol. 43 (1989), pp. 89-102.
Johann Cigler and Christian Krattenthaler, Hankel determinants of linear combinations of moments of orthogonal polynomials, arXiv:2003.01676 [math.CO], 2020.
Ari Cruz, Pamela E. Harris, Kimberly J. Harry, Jan Kretschmann, Matt McClinton, Alex Moon, John O. Museus, and Eric Redmon, On some discrete statistics of parking functions, arXiv:2312.16786 [math.CO], 2023. See p. 13.
Dennis E. Davenport, Lara K. Pudwell, Louis W. Shapiro and Leon C. Woodson, The Boundary of Ordered Trees, Journal of Integer Sequences, Vol. 18 (2015), Article 15.5.8.
Dennis E. Davenport, Louis W. Shapiro and Leon C. Woodson, A bijection between the triangulations of convex polygons and ordered trees, Integers, Vol. 20 (2020), Article #A8.
Colin Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.
Emeric Deutsch and Louis W. Shapiro, A survey of the Fine numbers, Discrete Math., Vol. 241 (2001), pp. 241-265.
Filippo Disanto, Andrea Frosini and Simone Rinaldi and Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics, Vol. 32 (2008), pp. 883-912.
R. R. X. Du, J. He, and X. Yun, Counting vertices in plane and k-ary trees with given outdegree, arXiv preprint arXiv:1501.07468 [math.CO], 2015.
Shalosh B. Ekhad, Mingjia Yang and Doron Zeilberger, Automated proofs of many conjectured recurrences in the OEIS made by R. J. Mathar, arXiv:1707.04654 [math.HO], 2017.
Sergio Falcon, Catalan transform of the K-Fibonacci sequence, Commun. Korean Math. Soc. 28 (2013), No. 4, pp. 827-832; http://dx.doi.org/10.4134/CKMS.2013.28.4.827.
Terrence Fine, Extrapolation when very little is known about the source, Information and Control, Vol. 16 (1970), pp. 331-359.
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
Ignas Gasparavičius, Andrius Grigutis, and Juozas Petkelis, Picturesque convolution-like recurrences and partial sums' generation, arXiv:2507.23619 [math.NT], 2025. See p. 27.
Taras Goy and Mark Shattuck, Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries, arXiv:2303.10223 [math.CO], 2023.
Taras Goy and Mark Shattuck, Hessenberg-Toeplitz Matrix Determinants with Schröder and Fine Number Entries, Carpathian Math. Publ. 15 (2023), No. 2, 420-436.
Candice Jean-Louis and Asamoah Nkwanta, Some algebraic structure of the Riordan group, Linear Algebra and its Applications, Vol. 438, No. 5 (2013), pp. 2018-2035. - _N. J. A. Sloane_, Jan 03 2013
Sergey Kitaev, Anna de Mier, Marc Noy, On the number of self-dual rooted maps, European J. Combin., Vol. 35 (2014), pp. 377-387. MR3090510. See page 827.
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv preprint arXiv:1201.6243 [math.CO], 2012. - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
John W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, Vol. 4 (2001), Article 01.1.5.
Toufik Mansour and Mark Shattuck, Chebyshev Polynomials and Statistics on a New Collection of Words in the Catalan Family, arXiv:1407.3516 [math.CO], 2014.
Peter McCalla and Asamoah Nkwanta, Catalan and Motzkin Integral Representations, arXiv:1901.07092 [math.NT], 2019.
Asamoah Nkwanta and Akalu Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, Vol. 16 (2013), Article 13.9.5.
Paul Peart and Wen-Jin Woan, Generating Functions via Hankel and Stieltjes Matrices, J. Integer Seqs., Vol. 3 (2000), Article 00.2.1.
Paul Peart and Wen-Jin Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, Vol. 4 (2001), Article 01.1.3.
Aaron Robertson, Dan Saracino and Doron Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.
D. G. Rogers, Similarity relations on finite ordered sets, J. Combin. Theory, Series A, Vol. 23, No. 1 (1977), pp. 88-98. Erratum, loc. cit., Vol. 25 (1978), pp. 95-96.
Louis W. Shapiro and Carol J. Wang, A bijection between 3-Motzkin paths and Schroder paths with no peak at odd height, JIS, Vol. 12 (2009), Article 09.3.2.
Volker Strehl, A note on similarity relations, Discr. Math., Vol. 19, No. 1 (1977), pp. 99-102.
Hua Sun and Yi Wang, A Combinatorial Proof of the Log-Convexity of Catalan-Like Numbers, J. Int. Seq., Vol. 17 (2014), Article 14.5.2
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, M.Sc. Thesis, Reykjavik Univ., May 2016.
Index entries for sequences related to rooted trees

A column of A065600.
Sequence with signs: A064310.
Bisections: A138413, A138414.
Logarithmic derivative: A072547.
Cf. A068875, A000108, A000045, A005043, A057078, A007317, A091867, A104597.
Cf. A000012, A009766, A039598, A055395, A064306, A100754, A126093.

a000957 n = a000957_list !! n
a000957_list = 0 : 1 :
   (map (`div` 2) $ tail $ zipWith (-) a000108_list a000957_list)
-- Reinhard Zumkeller, Nov 12 2011

[0,1] cat  [n le 1 select n-1 else (Catalan(n)-Self(n-1))/2: n in [1..30]]; // Vincenzo Librandi, Nov 17 2016

t1 := (1-sqrt(1-4*x))/(3-sqrt(1-4*x)); t2 := series(t1,x,90); A000957 := n- coeff(t2,x,n);
A000957 := proc(n): if n = 0 then 0 else add((-1)^(n+k-1)*binomial(n+k-1, n-1)*(n-k)/n, k=0..n-1) fi: end: seq(A000957(n), n=0..28); # Johannes W. Meijer, Jul 22 2013
# third Maple program:
a:= proc(n) option remember; `if`(n<3, n*(2-n),
      ((7*n-12)*a(n-1)+(4*n-6)*a(n-2))/(2*n))
    end:
seq(a(n), n=0..32);  # Alois P. Heinz, Apr 23 2020

Table[ Plus@@Table[ (-1)^(m+n) (n+m)!/n!/m! (n-m+1)/(n+1), {m, 0, n} ], {n, 0, 36} ] (* Wouter Meeussen *)
a[0] = 0; a[n_] := (1/2)*(-3*(-1/2)^n + 2^(n+1)*(2n-1)!!* Hypergeometric2F1Regularized[2, 2n+1, n+2, -1]); (* Jean-François Alcover, Feb 22 2012 *)
Table[2^n (n-2) (2n-1)!! (3 (n-1) Hypergeometric2F1[1, 3-n, 3+n, 2] - n - 2)/(n+2)! + KroneckerDelta[n], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 25 2015 *)

C(n):=binomial(2*n,n)/(n+1);
a(n):=if n<=0 then 0 else if n=1 then 1 else  sum(C(n-i-1)*(a(i)+a(i-1)),i,2,n-1);
/* Vladimir Kruchinin, Apr 23 2020 */

{a(n) = if( n<1, 0, polcoeff( 1 / (1 + 2 / (1 - sqrt(1 - 4*x + x*O(x^n)))), n))}; /* Michael Somos, Sep 17 2006 */

{a(n) = if( n<1, 0, polcoeff( 1 / (1 + 1 / serreverse(x - x^2 + x*O(x^n))), n))}; /* Michael Somos, Sep 30 2006 */

from itertools import count, islice
def A000957_gen(): # generator of terms
    yield from (0,1,0)
    a, c = 0, 1
    for n in count(1):
        yield (a:=(c:=c*((n<<2)+2)//(n+2))-a>>1)
A000957_list = list(islice(A000957_gen(),20)) # Chai Wah Wu, Apr 26 2023

def Fine():
    f, c, n = 1, 1, 1
    yield 0
    while True:
        yield f
        n += 1
        c = c * (4*n - 6) // n
        f = (c - f) // 2
a = Fine()
print([next(a) for  in range(29)])  # _Peter Luschny, Nov 30 2016

Catalan(n) = 2*a(n+1) + a(n), n >= 1. [Corrected by Pontus von Brömssen, Jul 23 2022]
a(n) = (A064306(n-1) + (-1)^(n-1))/2^n, n >= 1.
G.f.: (1-sqrt(1-4*x))/(3-sqrt(1-4*x)) (compare g.f. for Catalan numbers, A000108). - Emeric Deutsch
a(n) ~ 4^n/(9*n*sqrt(n*Pi)). (Corrected by Peter Luschny, Oct 26 2015.)
a(n) = (2/(n-1))*Sum_{j=0..n-3}(-2)^j*(j+1)*binomial(2n-1, n-3-j), n>=2. - Emeric Deutsch, Dec 26 2003
a(n) = 3*Sum_{j=0..floor((n-1)/2)} binomial(2n-2j-2, n-1) - binomial(2n, n) for n>0. - Emeric Deutsch, Jan 28 2004
Reversion of g.f. (x-2x^2)/(1-x)^2. - Ralf Stephan, Mar 22 2004
a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, C(1/2, k)8^k})+0^n; a(n) = ((-1)^n/2^n)*(-3/4-(1/4)*sum{k=0..n, (-1)^(k-1)*2^k*(2k)!/((k!)^2*(2k-1))})+0^n. - Paul Barry, Jun 10 2005
Hankel determinant transform is 1-n. - Michael Somos, Sep 17 2006
a(n+1) = A126093(n,0). - Philippe Deléham, Mar 05 2007
a(n+1) has g.f. 1/(1-0*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(1-2*x-x^2/(..... (continued fraction). - Paul Barry, Dec 02 2008
From Paul Barry, Jan 17 2009: (Start)
G.f.: x*c(x)/(1+x*c(x)), c(x) the g.f. of A000108;
a(n+1) = Sum_{k=0..n} (-1)^k*C(2n-k,n-k)*(k+1)/(n+1). (End)
a(n) = 3*(-1/2)^(n+1) + Gamma(n+1/2)*4^n*hypergeom([1, n+1/2],[n+2],-8) /(sqrt(Pi)*(n+1)!) (for n>0). - Mark van Hoeij, Nov 11 2009
Let A be the Toeplitz matrix of order n defined by: A[i,i-1] = -1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n>=1, a(n+1) = (-1)^n*charpoly(A,1). - Milan Janjic, Jul 08 2010
a(n) = the upper left term in M^n, n>0; where M = the infinite square production matrix:
0, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011
a(n+1) = Sum_{k=0..n} A039598(n,k)*(-2)^k. - Philippe Deléham, Nov 04 2011
D-finite with recurrence: 2*n*a(n) +(12-7*n)*a(n-1) +2*(3-2*n)*a(n-2)=0. - R. J. Mathar, Nov 15 2011
a(n) = sum(sum(2^(s-2n-2k)*(n/n+2k)binomial(n+2k, k)*binomial(s-n-1, s-2n-2k), (k=0, ..., floor((s-2n)/2)), (n=1, ..., s) with s>=2. - José Luis Ramírez Ramírez, Mar 22 2012
0 = a(n)*(16*a(n+1) + 22*a(n+2) - 20*a(n+3)) + a(n+1)*(34*a(n+1) + 53*a(n+2) - 38*a(n+3)) + a(n+2)*(10*a(n+2) + 4*a(n+3)) for all n in Z if we extend by a(0)=-1, a(-n) = -3/4 * (-2)^n if n>0. - Michael Somos, Jan 31 2014 [Corrected by Pontus von Brömssen, Aug 04 2022]
G.f. A(x) satisfies x*A'(x)/A(x) = x + 2*x^3 + 6*x^4 + 22*x^5 + ..., the o.g.f. for A072547. - Peter Bala, Oct 01 2015
a(n) = 2^n*(n-2)*(2*n-1)!!*(3*(n-1)*hypergeom([1,3-n], [3+n], 2)-n-2)/(n+2)! + 0^n. - Vladimir Reshetnikov, Oct 25 2015
a(n) = binomial(2*n,n)*(hypergeom([1,(1-n)/2,1-n/2],[1-n,3/2-n],1)*3/(4-2/n)-1) for n>=2. - Peter Luschny, Oct 26 2015
O.g.f. A(x) satisfies 1 + A(x) = (1 + 3*Sum_{n >= 1} Catalan(n)*x^n)/(1 + 2*Sum_{n >= 1} Catalan(n)*x^n) = (1 + 2*Sum_{n >= 1} binomial(2*n,n)*x^n )/(1 + 3/2*Sum_{n >= 1} binomial(2*n,n)*x^n). - Peter Bala, Sep 01 2016
a(n) = Sum_{i=2..n-1} C(n-i-1)*(a(i)+a(i-1)), a(0)=0, a(1)=1, where C(n) = A000108(n). - Vladimir Kruchinin, Apr 23 2020

A108263 Triangle read by rows: T(n,k) is the number of short bushes with n edges and k branchnodes (i.e., nodes of outdegree at least two). A short bush is an ordered tree with no nodes of outdegree 1.

Original entry on oeis.org

1, 0, 0, 1, 0, 1, 0, 1, 2, 0, 1, 5, 0, 1, 9, 5, 0, 1, 14, 21, 0, 1, 20, 56, 14, 0, 1, 27, 120, 84, 0, 1, 35, 225, 300, 42, 0, 1, 44, 385, 825, 330, 0, 1, 54, 616, 1925, 1485, 132, 0, 1, 65, 936, 4004, 5005, 1287, 0, 1, 77, 1365, 7644, 14014, 7007, 429, 0, 1, 90, 1925, 13650, 34398

Offset: 0

Emeric Deutsch, May 29 2005

Row n has 1+floor(n/2) terms. Row sums are the Riordan numbers (A005043). Column 3 yields A033275; column 4 yields A033276.

Related to the number of certain non-crossing partitions for the root system A_n. Cf. p. 12, Athanasiadis and Savvidou. Diagonals are A033282/A086810. Also see A132081 and A100754.- Tom Copeland, Oct 19 2014

			T(6,3)=5 because the only short bushes with 6 edges and 3 branchnodes are the five full binary trees with 6 edges.
Triangle begins:
1;
0;
0,1;
0,1;
0,1,2;
0,1,5;
0,1,9,5

Indranil Ghosh, Rows 0..100, flattened
C. Athanasiadis and C. Savvidou, The local h-vector of the cluster subdivision of a simplex, arXiv preprint arXiv:1204.0362, 2012
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999) 73-112.
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 10.

Cf. A005043, A033275, A033276.

Columns: A000007, A000012, A000096, A033275, A033276, A033277, A033278, A033279; A005043 (row sums), A033282, A086810

G:=(1+z-sqrt((1-z)^2-4*t*z^2))/2/z/(1+t*z): Gser:=simplify(series(G,z=0,18)): P[0]:=1: for n from 1 to 16 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 16 do seq(coeff(t*P[n],t^k),k=1..1+floor(n/2)) od; # yields sequence in triangular form
A108263 := (n,k) -> binomial(n-k-1,n-2*k)*binomial(n,k)/(n-k+1);
seq(print(seq(A108263(n,k),k=0..ceil((n-1)/2))),n=0..8); # Peter Luschny, Sep 25 2014

T[n_,k_]:=Binomial[n-k-1,n-2k]*Binomial[n,k]/(n-k+1); Flatten[Table[T[n,k],{n,0,11},{k,0,Ceiling[(n-1)/2]}]] (* Indranil Ghosh, Feb 20 2017 *)

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

T(n, k) = A086810(n-k, k). - Philippe Deléham, May 30 2005

A132081 Triangle (read by rows) with row sums = Motzkin sums (also called Riordan numbers) (A005043): T(n,s) = (1/n)C(n,s)(C(n-s,s+1) - C(n-s-2,s-1)).

Original entry on oeis.org

1, 1, 2, 1, 5, 1, 9, 5, 1, 14, 21, 1, 20, 56, 14, 1, 27, 120, 84, 1, 35, 225, 300, 42, 1, 44, 385, 825, 330, 1, 54, 616, 1925, 1485, 132, 1, 65, 936, 4004, 5005, 1287, 1, 77, 1365, 7644, 14014, 7007, 429

Offset: 3

Frank R. Bernhart (farb45(AT)gmail.com), Oct 30 2007

Whereas A005043 counts certain trees, or noncrossed partitions, this subdivides the counts according to the number of leaves, or the lattice rank. Analogous to the Narayana triangle (A001263), where rows sum to the Catalan numbers.
Diagonals of A132081 are rows of A033282. - Tom Copeland, May 08 2012
Related to the number of certain non-crossing partitions for the root system A_n. Cf. p. 12, Athanasiadis and Savvidou. See also A108263 and A100754. - Tom Copeland, Oct 19 2014

			A005043(6) = 15 = 1+9+5 since NC (noncrossed, planar) partitions of 6-point cycle without singletons have 1,9,5 items with 1,2,3 blocks.
Triangle begins:
  1;
  1,   2;
  1,   5;
  1,   9,   5;
  1,  14,  21;
  1,  20,  56,  14;
  1,  27, 120,  84;
  1,  35, 225, 300,  42;
  1,  44, 385, 825, 330;
  ...

C. Athanasiadis and C. Savvidou, The local h-vector of the cluster subdivision of a simplex, arXiv preprint arXiv:1204.0362 [math.CO], 2012.
F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
F. R. Bernhart & N. J. A. Sloane, Emails, April-May 1994
T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms, 2015.

Row sums are A007404.

Cf. A001263, A005043, A033282, A100754, A108263, A108767, A132081.

/* triangle excluding 0 */ [[Binomial(n,k)*Binomial(n-2-k,k)/(k+1): k in [0..n-3]]: n in [3..15]]; // Vincenzo Librandi, Oct 19 2014

Map[Most, Table[(1/n) Binomial[n, s] (Binomial[n - s, s + 1] - Binomial[n - s - 2, s - 1]), {n, 3, 14}, {s, 0, n}] /. k_ /; k <= 0 -> Nothing] // Flatten (* Michael De Vlieger, Jan 09 2016 *)

a(n,k) = binomial(n,k)*binomial(n-2-k,k)/(k+1). - David Callan, Jul 22 2008
From Peter Bala, Oct 22 2008: (Start)
O.g.f.: (1 + x - sqrt(1 - 2*x + x^2*(1 - 4*a)))/(2*x*(1 + a*x)) = 1 + a*x^2 + a*x^3 + (a + 2*a^2)*x^4 + (a + 5*a^2)*x^5 + (a + 9*a^2 + 5*a^3)*x^6 + ... . [corrected by Jason Yuen, Sep 22 2024]
Define a functional I on formal power series of the form f(x) = 1 + a*x + b*x^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = lim n -> infinity f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).
Let now f(x) = 1 + a*x^2 + a*x^3 + a*x^4 + ... . Then the o.g.f. for this table is I(f(x)) = 1 + a*x^2 + a*x^3 + (a + 2*a^2)*x^4 + (a + 5*a^2)*x^5 + (a + 9*a^2 + 5*a^3)*x^6 + ... . Cf. A001263 and A108767. (End)

Edited by N. J. A. Sloane, Jul 01 2008 at the suggestion of R. J. Mathar

Name corrected by Emeric Deutsch, Dec 20 2014

A166300 Number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having no UUDD's starting at level 0.

Original entry on oeis.org

1, 0, 0, 1, 1, 2, 5, 10, 22, 50, 113, 260, 605, 1418, 3350, 7967, 19055, 45810, 110637, 268301, 653066, 1594980, 3907395, 9599326, 23643751, 58374972, 144442170, 358136905, 889671937, 2214015802, 5518884019, 13778312440, 34448765740

Offset: 0

Emeric Deutsch, Nov 07 2009

nonn

a(n) = A166299(n,0).
a(n) is the number of peakless Motzkin paths of length n with no (1,0)-steps at level 0. Example: a(5)=2 because, denoting  U=(1,1), H=(1,0), and D=(1,-1), we have UHHHD and UUHDD. - Emeric Deutsch, May 03 2011
From Paul Barry, Mar 31 2011: (Start)
The Hankel transform of a(n+3) is A188444(n+1).
a(n+3) gives the diagonal sums of the triangle A100754.
a(n+3) has g.f. 1/(1-x-x^2/(1-2x+3x^2/(1+2x+x^2/(1-2x-(1/3)x^2/(1-x-(2/3)x^2/(1-2x+(5/2)x^2/(1+2x+(3/2)x^2/(1-...)))))))) (continued fraction) where the coefficients of x^2 have denominators A188442 and numerators A188443. (End)
The Ca1 triangle sums of triangle A175136 lead to this sequence (n>=3). For the definitions of the Ca1 and other triangle sums see A180662. - Johannes W. Meijer, May 06 2011
a(n) is the number of closed Deutsch paths of n steps with all peaks at even height.  A Deutsch path is a lattice path of up-steps (1,1) and down-steps (1,-j), j>=1, starting at the origin that never goes below the x-axis, and it is closed if it ends on the x-axis. For example a(5) = 2 counts UUUU4, UU1U2, where  U denotes an up-step and a down-step is denoted by its length, and a(6) = 5 counts UUUU13, UUUU22, UUUU31, UU1U11, UU2UU2. - David Callan, Dec 08 2021

			a(5)=2 because we have UUUDDUUDDD and UUUUUDDDDD.
G.f. = 1 + x^3 + x^4 + 2*x^5 + 5*x^6 + 10*x^7 + 22*x^8 + 50*x^9 + 113*x^10 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 22.

Cf. A166299, A180662, A188442, A188443, A188444.

m:=40; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!(2/(1+x+x^2+Sqrt((1+x+x^2)*(1-3*x+x^2))))); // G. C. Greubel, Sep 22 2018

G := 2/(1+z+z^2+sqrt((1+z+z^2)*(1-3*z+z^2))): Gser := series(G, z = 0, 35): seq(coeff(Gser, z, n), n = 0 .. 32);

CoefficientList[Series[2/(1+x+x^2+Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)

a(n):=sum((j+1)*sum((binomial(j+2*i+1,i)*sum(binomial(k,n-k-j-2*i)*binomial(k+j+2*i,k)*(-1)^(n-k),k,0,n-j-2*i))/(j+2*i+1),i,0,n-j),j,0,n); /*  Vladimir Kruchinin, Mar 07 2016 */

{a(n) = local(A); A = 1 + O(x); for( k=1, ceil(n / 5), A = 1 / (1 - x^3 / (1 - x / (1 - x * A)))); polcoeff( A, n)}; /* Michael Somos, May 12 2012 */

x='x+O('x^40); Vec(2/(1+x+x^2+((1+x+x^2)*(1-3*x+x^2))^(1/2))) \\ Altug Alkan, Sep 23 2018

G.f. = G(z)=2/(1 + z + z^2 + sqrt((1 + z + z^2)*(1 - 3*z + z^2))).
G.f.: 1 / (1 - x^3 / (1 - x / (1 - x / (1 - x^3 / (1 - x / (1 - x / ...)))))). - Michael Somos, May 12 2012
G.f. A(x) satisfies A(x) = 1 / (1 - x^3 / (1 - x / (1 - x *A(x)))). - Michael Somos, May 12 2012
Conjecture: (n+1)*a(n) +2*(-n+1)*a(n-1) +(-n+1)*a(n-2) +2*(-n+1)*a(n-3) +(n-3)*a(n-4)=0. - R. J. Mathar, Nov 24 2012
a(n) ~ (3+sqrt(5))^(n+2) * sqrt(7*sqrt(5)-15) / (2 * sqrt(Pi) * n^(3/2) * 2^(n+9/2)). - Vaclav Kotesovec, Feb 12 2014. Equivalently, a(n) ~  5^(1/4) * phi^(2*n + 2) / (8 * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021
a(n) = Sum_{j=0..n}((j+1)*Sum_{i=0..n-j}((binomial(j+2*i+1,i)*Sum_{k=0..n-j-2*i}(binomial(k,n-k-j-2*i)*binomial(k+j+2*i,k)*(-1)^(n-k)))/(j+2*i+1))). - Vladimir Kruchinin, Mar 07 2016

A372066 Array read by antidiagonals: T(m,n) (m >= 1, n >= 1) = number of reduced connected row convex (RCRC) constraints between an m-element set and an n-element set.

Original entry on oeis.org

1, 1, 1, 1, 7, 1, 1, 17, 17, 1, 1, 31, 90, 31, 1, 1, 49, 284, 284, 49, 1, 1, 71, 687, 1398, 687, 71, 1, 1, 97, 1411, 4861, 4861, 1411, 97, 1, 1, 127, 2592, 13555, 23020, 13555, 2592, 127, 1, 1, 161, 4390, 32436, 83858, 83858, 32436, 4390, 161, 1

Offset: 1

N. J. A. Sloane, May 12 2024, based on emails from Don Knuth, May 06 2024 and May 08 2024

See the Knuth "Notes" link for much more information about these sequences. The present sequence is called "table0" in Part 1 of the Notes.

			The initial antidiagonals are:
   1,
   1, 1,
   1, 7, 1,
   1, 17, 17, 1,
   1, 31, 90, 31, 1,
   1, 49, 284, 284, 49, 1,
   1, 71, 687, 1398, 687, 71, 1,
   1, 97, 1411, 4861, 4861, 1411, 97, 1,
   1, 127, 2592, 13555, 23020, 13555, 2592, 127, 1,
   1, 161, 4390, 32436, 83858, 83858, 32436, 4390, 161, 1,
   ...
The array begins:
   1, 1, 1, 1, 1, 1, 1, 1, 1, ...
   1, 7, 17, 31, 49, 71, 97, 127, 161, ...
   1, 17, 90, 284, 687, 1411, 2592, 4390, 6989, ...
   1, 31, 284, 1398, 4861, 13555, 32436, 69350, 135985, ...
   1, 49, 687, 4861, 23020, 83858, 253876, 669660, 1587491, ...
   1, 71, 1411, 13555, 83858, 386774, 1445748, 4613486, 13010537, ...
   1, 97, 2592, 32436, 253876, 1445748, 6539320, 24831150, 82162821, ...
   1, 127, 4390, 69350, 669660, 4613486, 24831150, 110639796, 424473531, ...
   1, 161, 6989, 135985, 1587491, 13010537, 82162821, 424473531, 1868934548, ...
   ...

Yves Deville, Olivier Barette, Pascal Van Hentenryck, Constraint satisfaction over connected row-convex constraints, Artificial Intelligence 109 (1999), 243-271.
Peter Jeavons, David Cohen, Martin C. Cooper, Constraints, consistency and closure". Artificial Intelligence 101 (1998), 251-265.

D. E. Knuth, Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints, May 06 2024

Cf. A100754, A372067, A372068.

Knuth gives a formula expressing the array A372367 in terms of the current array. He also reports that there is strong experimental evidence that the n-th term of row m in the current array is a polynomial of degree 2*m-2 in n.

A114515 Number of peaks in all hill-free Dyck paths of semilength n (a Dyck path is hill-free if it has no peaks at level 1).

Original entry on oeis.org

0, 0, 1, 3, 12, 45, 171, 651, 2488, 9540, 36690, 141482, 546864, 2118207, 8219967, 31952115, 124389552, 484908408, 1892657934, 7395597354, 28928182440, 113260606074, 443827115886, 1740592240638, 6831289801872, 26829201570600

Offset: 0

Emeric Deutsch, Dec 04 2005

nonn

			a(3)=3 because in the two hill-free Dyck paths of semilength 3, namely U(UD)(UD)D and UU(UD)DD, we have altogether 3 peaks (shown between parentheses).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Sergi Elizalde, Symmetric peaks and symmetric valleys in Dyck paths, arXiv:2008.05669 [math.CO], 2020.

Cf. A000108, A100754.

C:=(1-sqrt(1-4*z))/2/z: G:=1/(1-z*C+z)^2*z^2*C/(1-2*z*C): Gser:=series(G,z=0,32): 0, seq(coeff(Gser,z^n),n=1..28);

CoefficientList[Series[1/(1-x*(1-Sqrt[1-4*x])/2/x+x)^2*x^2*(1-Sqrt[1-4*x])/2/x/(1-2*x*(1-Sqrt[1-4*x])/2/x), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 20 2014 *)
a[n_] := If[n<=1, 0, Binomial[2n-1, n-2] Hypergeometric2F1[2, 2-n, 1-2n, -1]]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Oct 22 2016, after Vladimir Kruchinin *)

a(n):=sum(k*(-1)^(k+1)*binomial(2*n-k,n-k-1),k,1,n); /*  Vladimir Kruchinin, Oct 22 2016 */

my(x='x + O('x^50)); concat([0,0], Vec((2*x*(1-sqrt(1-4*x)))/(sqrt(1-4*x)*(1 + 2*x + sqrt(1-4*x))^2))) \\ G. C. Greubel, Feb 08 2017

a(n) = Sum_{k=0..n-1} k*A100754(n,k).
G.f.: z^2*C/((1-z*C+z)^2*(1-2*z*C)), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function.
a(n) ~ 2^(2*n+1)/(9*sqrt(Pi*n)). - Vaclav Kotesovec, Mar 20 2014
a(n) = Sum_{k=1..n} (k*(-1)^(k+1)*binomial(2*n-k,n-k-1)). - Vladimir Kruchinin, Oct 22 2016
D-finite with recurrence 2*(n+1)*a(n) -9*n*a(n-1) -3*n*a(n-2) +5*(5*n-16)*a(n-3) +6*(2*n-5)*a(n-4)=0. - R. J. Mathar, Jul 22 2022

A114586 Triangle read by rows: T(n,k) is the number of hill-free Dyck paths of semilength n and having k peaks at odd levels (0<=k<=n-2; n>=2). A hill in a Dyck path is a peak at level 1.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 6, 8, 3, 1, 15, 22, 15, 4, 1, 36, 68, 52, 24, 5, 1, 91, 198, 191, 100, 35, 6, 1, 232, 586, 651, 425, 170, 48, 7, 1, 603, 1718, 2203, 1656, 820, 266, 63, 8, 1, 1585, 5047, 7285, 6299, 3591, 1435, 392, 80, 9, 1, 4213, 14808, 23832, 23164, 15155, 6972, 2338

Offset: 2

Emeric Deutsch, Dec 11 2005

Row sums are the Fine numbers (A000957). Column 0 yield the Riordan numbers (A005043). Sum(k*T(n,k),k=0..n-2)=A114587(n).

			T(5,2)=3 because we have UU(UD)DU(UD)DD, UUDU(UD)(UD)DD and UU(UD)(UD)DUDD, where U=(1,1), D=(1,-1) (the peaks at odd levels are shown between parentheses).
Triangle begins:
1;
1,1;
3,2,1;
6,8,3,1;
15,22,15,4,1;

Cf. A000957, A005043, A114587, A114588, A100754.

G:=(t*z+z+1-sqrt(z^2*t^2+2*z^2*t-2*z*t-3*z^2-2*z+1))/2/z/(1+t+z)-1: 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-1) od; # yields sequence in triangular form

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

A372067 Array read by antidiagonals: T(m,n) (m >= 0, n >= 0) = number of connected row convex (CRC) constraints between an m-element set and an n-element set.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 16, 8, 1, 1, 16, 56, 56, 16, 1, 1, 32, 176, 289, 176, 32, 1, 1, 64, 512, 1231, 1231, 512, 64, 1, 1, 128, 1408, 4623, 6655, 4623, 1408, 128, 1, 1, 256, 3712, 15887, 30553, 30553, 15887, 3712, 256, 1, 1, 512, 9472, 51103, 125197, 166186, 125197, 51103, 9472, 512, 1

Offset: 0

N. J. A. Sloane, May 12 2024, based on emails from Don Knuth, May 06 2024 and May 08 2024

See the Knuth "Notes" link for much more information about these sequences. The present sequence is called "table" in Part 1 of the Notes.

			The initial antidiagonals are:
   1,
   1, 1,
   1, 2, 1,
   1, 4, 4, 1,
   1, 8, 16, 8, 1,
   1, 16, 56, 56, 16, 1,
   1, 32, 176, 289, 176, 32, 1,
   1, 64, 512, 1231, 1231, 512, 64, 1,
   1, 128, 1408, 4623, 6655, 4623, 1408, 128, 1,
   1, 256, 3712, 15887, 30553, 30553, 15887, 3712, 256, 1,
   1, 512, 9472, 51103, 125197, 166186, 125197, 51103, 9472, 512, 1,
   ...
The array begins:
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...
   1, 4, 16, 56, 176, 512, 1408, 3712, 9472, 23552, ...
   1, 8, 56, 289, 1231, 4623, 15887, 51103, 156159, 457983, ...
   1, 16, 176, 1231, 6655, 30553, 125197, 471581, 1664061, 5572733, ...
   1, 32, 512, 4623, 30553, 166186, 790250, 3402874, 13570090, 50887322, ...
   1, 64, 1408, 15887, 125197, 790250, 4283086, 20750168, 92177312, 382005370, ...
   1, 128, 3712, 51103, 471581, 3402874, 20750168, 111803585,  547505091, 2483709151, ...
   1, 256, 9472, 156159, 1664061, 13570090, 92177312, 547505091, 2932069965, 14453287777, ...
   1, 512, 23552, 457983, 5572733, 50887322, 382005370, 2483709151, 14453287777, 76964939964, ...
   ...

Yves Deville, Olivier Barette, Pascal Van Hentenryck, Constraint satisfaction over connected row-convex constraints, Artificial Intelligence 109 (1999), 243-271.
Peter Jeavons, David Cohen, Martin C. Cooper, Constraints, consistency and closure". Artificial Intelligence 101 (1998), 251-265.

D. E. Knuth, Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints, May 06 2024

Cf. A100754, A372066, A372068.

Knuth gives a formula expressing the current array in terms of the array A372066.

A372068 Array read by antidiagonals: T(m,n) (m >= 0, n >= 0) = number of max-and-min-closed constraints between an m-element set and an n-element set.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 13, 8, 1, 1, 16, 38, 38, 16, 1, 1, 32, 104, 147, 104, 32, 1, 1, 64, 272, 506, 506, 272, 64, 1, 1, 128, 688, 1612, 2103, 1612, 688, 128, 1, 1, 256, 1696, 4856, 7887, 7887, 4856, 1696, 256, 1, 1, 512, 4096, 14016, 27477, 34088, 27477, 14016, 4096, 512, 1

Offset: 0

N. J. A. Sloane, May 12 2024, based on emails from Don Knuth, May 06 2024 and May 08 2024

See the Knuth "Notes" link for much more information about these sequences. The present sequence is called "tab" in Part 2 of the Notes.

			The initial antidiagonals are:
   1,
   1, 1,
   1, 2, 1,
   1, 4, 4, 1,
   1, 8, 13, 8, 1,
   1, 16, 38, 38, 16, 1,
   1, 32, 104, 147, 104, 32, 1,
   1, 64, 272, 506, 506, 272, 64, 1,
   1, 128, 688, 1612, 2103, 1612, 688, 128, 1,
   1, 256, 1696, 4856, 7887, 7887, 4856, 1696, 256, 1,
   1, 512, 4096, 14016, 27477, 34088, 27477, 14016, 4096, 512, 1,
   ...
The array begins:
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ...
   1, 4, 13, 38, 104, 272, 688, 1696, 4096, 9728, ...
   1, 8, 38, 147, 506, 1612, 4856, 14016, 39104, 106112, ...
   1, 16, 104, 506, 2103, 7887, 27477, 90498, 285072, 865856, ...
   1, 32, 272, 1612, 7887, 34088, 134825, 498465, 1746830, 5859404, ...
   1, 64, 688, 4856, 27477, 134825, 597539, 2451038, 9455182, 34687916, ...
   1, 128, 1696, 14016, 90498, 498465, 2451038, 11055950, 46570858, 185484836, ...
   1, 256, 4096, 39104, 285072, 1746830, 9455182, 46570858, 212833803, 914854829, ...
   1, 512, 9728, 106112, 865856, 5859404, 34687916, 185484836, 914854829, 4223468802, ...
   ...

D. E. Knuth, Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints, May 06 2024

Cf. A099594, A100754, A272644, A372066, A372067.

A188474 A generalized Deutsch triangle.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 10, 10, 1, 1, 16, 40, 16, 1, 1, 23, 102, 102, 23, 1, 1, 31, 209, 393, 209, 31, 1, 1, 40, 376, 1122, 1122, 376, 40, 1, 1, 50, 620, 2656, 4296, 2656, 620, 50, 1, 1, 61, 960, 5536, 13100, 13100, 5536, 960, 61, 1, 1, 73, 1417, 10522, 34036, 50180, 34036, 10522, 1417, 73, 1

Offset: 0

Paul Barry, Apr 01 2011

Member r=2 of the family of "Pascal-like" triangles with T(n,k)=sum{j=0..n-k+1, (j/(n+2-j))*C(n+2-j,n-k+1)*C(n+2-j,k+1)*r^(j-1)}.
The Deutsch triangle A100754 corresponds to r=1.
Row sums are A137398(n+1) (conjecture). Diagonal sums are A188476.

			Triangle begins
1,
1, 1,
1, 5, 1,
1, 10, 10, 1,
1, 16, 40, 16, 1,
1, 23, 102, 102, 23, 1,
1, 31, 209, 393, 209, 31, 1,
1, 40, 376, 1122, 1122, 376, 40, 1,
1, 50, 620, 2656, 4296, 2656, 620, 50, 1,
1, 61, 960, 5536, 13100, 13100, 5536, 960, 61, 1,
1, 73, 1417, 10522, 34036, 50180, 34036, 10522, 1417, 73, 1

T(n,k)=sum{j=0..n-k+1, (j/(n+2-j))*C(n+2-j,n-k+1)*C(n+2-j,k+1)*2^(j-1)}.

cp's OEIS Frontend

A000957 Fine's sequence (or Fine numbers): number of relations of valence >= 1 on an n-set; also number of ordered rooted trees with n nodes having root of even degree.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Sage

Formula

A108263 Triangle read by rows: T(n,k) is the number of short bushes with n edges and k branchnodes (i.e., nodes of outdegree at least two). A short bush is an ordered tree with no nodes of outdegree 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A132081 Triangle (read by rows) with row sums = Motzkin sums (also called Riordan numbers) (A005043): T(n,s) = (1/n)*C(n,s)*(C(n-s,s+1) - C(n-s-2,s-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A166300 Number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having no UUDD's starting at level 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Maxima

PARI

PARI

Formula

A372066 Array read by antidiagonals: T(m,n) (m >= 1, n >= 1) = number of reduced connected row convex (RCRC) constraints between an m-element set and an n-element set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A114515 Number of peaks in all hill-free Dyck paths of semilength n (a Dyck path is hill-free if it has no peaks at level 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

A132081 Triangle (read by rows) with row sums = Motzkin sums (also called Riordan numbers) (A005043): T(n,s) = (1/n)C(n,s)(C(n-s,s+1) - C(n-s-2,s-1)).