login
The OEIS is supported by the many generous donors 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 from (0,0) to (2n,0) having k peaks. 25

%I #128 Jun 07 2023 09:46:05

%S 1,1,1,2,3,1,5,10,6,1,14,35,30,10,1,42,126,140,70,15,1,132,462,630,

%T 420,140,21,1,429,1716,2772,2310,1050,252,28,1,1430,6435,12012,12012,

%U 6930,2310,420,36,1,4862,24310,51480,60060,42042,18018,4620,660,45,1,16796

%N Triangle (0 <= k <= n) read by rows: T(n, k) is the number of Schröder paths from (0,0) to (2n,0) having k peaks.

%C 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.

%C 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

%C A090181*A007318 as infinite lower triangular matrices. - _Philippe Deléham_, Oct 14 2008

%C 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

%H Vincenzo Librandi, <a href="/A060693/b060693.txt">Rows n = 0..100, flattened</a>

%H J. Agapito, A. Mestre, P. Petrullo, and M. Torres, <a href="https://m.math.tecnico.ulisboa.pt/seminars/ceafel/index.php.en?action=show&amp;id=4075">Counting noncrossing partitions via Catalan triangles</a>, CEAFEL Seminar, June 30, 2015

%H Jean-Christophe Aval and François Bergeron, <a href="http://arxiv.org/abs/1603.09487">Rectangular Schröder Parking Functions Combinatorics</a>, arXiv:1603.09487 [math.CO], 2016.

%H Paul Barry, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, J. Integer Sequ., Vol. 9 (2006), Article 06.2.4.

%H Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.

%H Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.

%H Paul Barry, <a href="https://www.emis.de/journals/JIS/VOL22/Barry1/barry411.html">The Central Coefficients of a Family of Pascal-like Triangles and Colored Lattice Paths</a>, J. Int. Seq., Vol. 22 (2019), Article 19.1.3.

%H Paul Barry, <a href="https://www.emis.de/journals/JIS/VOL22/Barry3/barry422.html">Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles</a>, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.

%H Paul Barry, <a href="https://arxiv.org/abs/2101.06713">On the inversion of Riordan arrays</a>, arXiv:2101.06713 [math.CO], 2021.

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Barry/barry601.html">On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.

%H David Callan and Toufik Mansour, <a href="http://arxiv.org/abs/1602.05182">Five subsets of permutations enumerated as weak sorting permutations</a>, arXiv:1602.05182 [math.CO], 2016.

%H G. E. Cossali, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Cossali/cossali.html">A Common Generating Function of Catalan Numbers and Other Integer Sequences</a>, J. Int. Seqs. 6 (2003).

%H D. Drake, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Drake/drake.html">Bijections from Weighted Dyck Paths to Schröder Paths</a, J. Int. Seq. 13 (2010) # 10.9.2

%H Samuele Giraudo, <a href="https://arxiv.org/abs/1903.00677">Tree series and pattern avoidance in syntax trees</a>, arXiv:1903.00677 [math.CO], 2019.

%H Nate Kube and Frank Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Ruskey/ruskey99.html">Sequences That Satisfy a(n-a(n))=0</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.5.

%H Krishna Menon and Anurag Singh, <a href="https://arxiv.org/abs/2212.13794">Grassmannian permutations avoiding identity</a>, arXiv:2212.13794 [math.CO], 2022.

%H Jean-Christophe Novelli and Jean-Yves Thibon, <a href="http://arxiv.org/abs/1209.5959">Duplicial algebras and Lagrange inversion</a>, arXiv preprint arXiv:1209.5959 [math.CO], 2012.

%F 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

%F 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

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

%F T(n, k) = binomial(2n-k, n)*binomial(n, k)/(n-k+1). - _Philippe Deléham_, Dec 07 2003

%F A060693(n, k) = binomial(2*n-k, k)*A000108(n-k); A000108: Catalan numbers. - _Philippe Deléham_, Dec 30 2003

%F 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

%F T(n,k) = Sum_{j>=0} A090181(n,j)*binomial(j,k). - _Philippe Deléham_, May 04 2007

%F 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

%F From _Paul Barry_, Jan 29 2009: (Start)

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

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

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

%F T(n,k) = A104684(n,k)/(n-k+1). - _Peter Luschny_, May 17 2011

%F From _Tom Copeland_, Sep 21 2011: (Start)

%F 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,

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

%F 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/d) u, evaluated at u = 0.

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

%F See my 2008 formulas in A033282 to relate this entry to A088617, A001263, A086810, and other matrices. - _Tom Copeland_, Jan 22 2016

%F 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

%F From _Werner Schulte_, Jan 09 2017: (Start)

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

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

%F (End)

%F Conjecture: Sum_{k=0..n} (-1)^k*T(n,k)*(n+1-k)^2 = 1+n+n^2. - _Werner Schulte_, Jan 11 2017

%e Triangle begins:

%e 00: [ 1]

%e 01: [ 1, 1]

%e 02: [ 2, 3, 1]

%e 03: [ 5, 10, 6, 1]

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

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

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

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

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

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

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

%e ...

%p A060693 := (n,k) -> binomial(n,k)*binomial(2*n-k,n)/(n-k+1); # _Peter Luschny_, May 17 2011

%t 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 *)

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

%o for(n=0, 10, for(k=0, n, print1(T(n, k),", ")); print); \\ _Indranil Ghosh_, Jul 28 2017

%o (Python)

%o from sympy import binomial

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

%o for n in range(11): print([T(n, k) for k in range(n + 1)]) # _Indranil Ghosh_, Jul 28 2017

%Y Cf. A006318, A000108, A001700.

%Y Triangle in A088617 transposed.

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

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

%K nonn,tabl

%O 0,4

%A _F. Chapoton_, Apr 20 2001

%E More terms from _Vladeta Jovovic_, Apr 21 2001

%E New description from _Philippe Deléham_, Aug 12 2003

%E New name using a comment by _Emeric Deutsch_ from _Peter Luschny_, Jul 26 2017

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:48 EDT 2024. Contains 371265 sequences. (Running on oeis4.)