login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060693 Triangle (0 <= k <= n) read by rows: T(n, k) is the number of Schröder paths having k peaks. 24
1, 1, 1, 2, 3, 1, 5, 10, 6, 1, 14, 35, 30, 10, 1, 42, 126, 140, 70, 15, 1, 132, 462, 630, 420, 140, 21, 1, 429, 1716, 2772, 2310, 1050, 252, 28, 1, 1430, 6435, 12012, 12012, 6930, 2310, 420, 36, 1, 4862, 24310, 51480, 60060, 42042, 18018, 4620, 660, 45, 1, 16796 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

The rows sum to A006318 (Schroeder numbers), the left column is A000108 (Catalan numbers); the next-to-left column is A001700, the alternating sum in each row but the first is 0.

T(n,k) is the number of Schroeder paths (i.e., consisting of steps U=(1,1), D=(1,-1),H=(2,0) and never going below the x-axis) from (0,0) to (2n,0), having k peaks. Example: T(2,1)=3 because we have UU*DD, U*DH and HU*D, the peaks being shown by *. E.g., T(n,k) = binomial(n,k)*binomial(2n-k,n-1)/n for n>0. - Emeric Deutsch, Dec 06 2003

A090181*A007318 as infinite lower triangular matrices. - Philippe Deléham, Oct 14 2008

T(n,k) is also the number of rooted plane trees with maximal degree 3 and k vertices of degree 2 (a node may have at most 2 children, and there are exactly k nodes with 1 child). Equivalently, T(n,k) is the number of syntactically different expressions that can be formed that use a unary operation k times, a binary operation n-k times, and nothing else (sequence of operands is fixed). - Lars Hellstrom (Lars.Hellstrom(AT)residenset.net), Dec 08 2009

LINKS

Vincenzo Librandi, Rows n = 0..100, flattened

J. Agapito, A. Mestre, P. Petrullo, and M. Torres, Counting noncrossing partitions via Catalan triangles, CEAFEL Seminar, June 30, 2015

Jean-Christophe Aval, François Bergeron, Rectangular Schröder Parking Functions Combinatorics, arXiv:1603.09487 [math.CO], 2016.

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.

Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.

Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.

David Callan, Toufik Mansour, Five subsets of permutations enumerated as weak sorting permutations, arXiv:1602.05182 [math.CO], 2016.

G. E. Cossali, A Common Generating Function of Catalan Numbers and Other Integer Sequences, J. Int. Seqs. 6 (2003).

D. Drake, Bijections from Weighted Dyck Paths to Schröder Paths</a, J. Int. Seq. 13 (2010) # 10.9.2

Nate Kube and Frank Ruskey, Sequences That Satisfy a(n-a(n))=0, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

Jean-Christophe Novelli and Jean-Yves Thibon, Duplicial algebras and Lagrange inversion, arXiv preprint arXiv:1209.5959 [math.CO], 2012.

FORMULA

Triangle T(n, k) (0 <= k <= n) read by rows; given by [1, 1, 1, 1, 1, ...] DELTA [1, 0, 1, 0, 1, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 12 2003

If C_n(x) is the g.f. of row n of the Narayana numbers (A001263), C_n(x) = Sum_{k=1..n}(binomial(n,k-1)binomial(n-1,k-1)/k * x^k) and T_n(x) is the g.f. of row n of T(n,k), then T_n(x) = C_n(x+1), or T(n,k) = [x^n]Sum_{k=1..n}(A001263(n,k)*(x+1)^k). - Mitch Harris, Jan 16 2007, Jan 31 2007

G.f.: (1 - t*y - sqrt((1-y*t)^2 - 4*y)) / 2.

T(n, k) = binomial(2n-k, n)*binomial(n, k)/(n-k+1). - Philippe Deléham, Dec 07 2003

A060693(n, k) = binomial(2*n-k, k)*A000108(n-k); A000108: Catalan numbers. - Philippe Deléham, Dec 30 2003

Sum_{k=0..n} T(n,k)*x^k = A000007(n), A000108(n), A006318(n), A047891(n+1), A082298(n), A082301(n), A082302(n), A082305(n), A082366(n), A082367(n), for x = -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, respectively. - Philippe Deléham, Apr 01 2007

T(n,k) = Sum_{j>=0} A090181(n,j)*binomial(j,k). - Philippe Deléham, May 04 2007

Sum_{k=0..n} T(n,k)*x^(n-k) = (-1)^n*A107841(n), A080243(n), A000007(n), A000012(n), A006318(n), A103210(n), A103211(n), A133305(n), A133306(n), A133307(n), A133308(n), A133309(n) for x = -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, respectively. - Philippe Deléham, Oct 18 2007

From Paul Barry, Jan 29 2009: (Start)

G.f.: 1/(1-xy-x/(1-xy-x/(1-xy-x/(1-xy-x/(1-xy-x/(1-.... (continued fraction);

G.f.: 1/(1-(x+xy)/(1-x/(1-(x+xy)/(1-x/(1-(x+xy)/(1-.... (continued fraction). (End)

T(n,k) = [k<=n]*(Sum_{j=0..n} binomial(n,j)^2*binomial(j,k))/(n-k+1). - Paul Barry, May 28 2009

T(n,k) = A104684(n,k)/(n-k+1). - Peter Luschny, May 17 2011

From Tom Copeland, Sep 21 2011: (Start)

With F(x,t) = (1-(2+t)*x-sqrt(1-2*(2+t)*x+(t*x)^2))/(2*x) an o.g.f. (nulling the n=0 term) in x for the A060693 polynomials in t,

  G(x,t) = x/(1+t+(2+t)*x+x^2) is the compositional inverse in x.

Consequently, with H(x,t) = 1/(dG(x,t)/dx)=(1+t+(2+t)*x+x^2)^2 /(1+t-x^2), the n-th A060693 polynomial in t is given by (1/n!)*[(H(x,t)*d/dx)^n] x evaluated at x=0, i.e., F(x,t) = exp[x*H(u,t)*d/du] u, evaluated at u = 0.

  Also, dF(x,t)/dx = H(F(x,t),t). (End)

See my 2008 formulas in A033282 to relate this entry to A088617, A001263, A086810, and other matrices. - Tom Copeland, Jan 22 2016

Rows of this entry are non-vanishing antidiagonals of A097610. See p. 14 of Agapito et al. for a bivariate generating function and its inverse. - Tom Copeland, Feb 03 2016

From Werner Schulte, Jan 09 2017: (Start)

T(n,k) = A126216(n,k-1) + A126216(n,k) for 0 < k < n;

Sum_{k=0..n} (-1)^k*(1+x*(n-k))*T(n,k) = x + (1-x)*A000007(n).

(End)

Conjecture: Sum_{k=0..n} (-1)^k*T(n,k)*(n+1-k)^2 = 1+n+n^2. - Werner Schulte, Jan 11 2017

EXAMPLE

Triangle begins:

00: [1]

01: [1, 1]

02: [2, 3, 1]

03: [5, 10, 6, 1]

04: [14, 35, 30, 10, 1]

05: [42, 126, 140, 70, 15, 1]

06: [132, 462, 630, 420, 140, 21, 1]

07: [429, 1716, 2772, 2310, 1050, 252, 28, 1]

08: [1430, 6435, 12012, 12012, 6930, 2310, 420, 36, 1]

09: [4862, 24310, 51480, 60060, 42042, 18018, 4620, 660, 45, 1]

10: [16796, 92378, 218790, 291720, 240240, 126126, 42042, 8580, 990, 55, 1]

...

MAPLE

A060693 := (n, k) -> binomial(n, k)*binomial(2*n-k, n)/(n-k+1); # Peter Luschny, May 17 2011

MATHEMATICA

t[n_, k_] := Binomial[n, k]*Binomial[2 n - k, n]/(n - k + 1); Flatten[Table[t[n, k], {n, 0, 9}, {k, 0, n}]] (* Robert G. Wilson v, May 30 2011 *)

PROG

(PARI) T(n, k) = binomial(n, k)*binomial(2*n - k, n)/(n - k + 1);

for(n=0, 10, for(k=0, n, print1(T(n, k), ", ")); print); \\ Indranil Ghosh, Jul 28 2017

(Python)

from sympy import binomial

def T(n, k): return binomial(n, k)*binomial(2*n - k, n)/(n - k + 1)

for n in xrange(11): print [T(n, k) for k in xrange(n + 1)] # Indranil Ghosh, Jul 28 2017

CROSSREFS

Cf. A006318, A000108, A001700.

Triangle in A088617 transposed.

Diagonals give A000108, A001700, A002457, A002802, A002803; A000012, A000217, A034827, A000910, A088625, A088626.

Cf. A001263, A033282, A086810, A088617, A097610.

Sequence in context: A290053 A105640 A090299 * A172381 A089302 A049020

Adjacent sequences:  A060690 A060691 A060692 * A060694 A060695 A060696

KEYWORD

nonn,tabl,changed

AUTHOR

F. Chapoton, Apr 20 2001

EXTENSIONS

More terms from Vladeta Jovovic, Apr 21 2001

New description from Philippe Deléham, Aug 12 2003

New name using a comment by Emeric Deutsch from Peter Luschny, Jul 26 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 21:14 EDT 2018. Contains 316541 sequences. (Running on oeis4.)