login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A145884 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n such that the difference between the sum of the valley abscissae and number of valleys is k (0 <= k <= (n-1)^2). 2
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 3, 3, 4, 4, 4, 4, 4, 3, 3, 2, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 10, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 2, 3, 4, 6, 7, 9, 11, 13, 15, 18, 19, 21, 23, 24, 24, 25, 24, 24, 23, 21, 19, 18, 15, 13, 11, 9, 7, 6, 4, 3 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,13

COMMENTS

Row n contains 1+(n-1)^2 entries (n >= 1).

Row sums are the Catalan numbers (A000108).

Sum_{k=0..(n-1)^2} k*T(n,k) = A145885(n).

In the R. Stanley reference one has the equivalent statistic (maj(w) - des(w)) on Dyck words w.

REFERENCES

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see p. 236, Exercise 6.34 d.

LINKS

Alois P. Heinz, Rows n = 0..32, flattened

FORMULA

The generating polynomial for row n is P[n](t) = ((1+t)/(1+t^n))*binomial[2n,n]/[n+1], where [n+1]=1+t+t^2+...+t^n and binomial[2n,n] is a Gaussian polynomial.

EXAMPLE

T(4,5)=2 because we have UD.UUD.UDD (2+5-2=5) and UUUDDD.UD (6-1=5); here U=(1,1), D=(1,-1) and each valley is shown by a dot.

Triangle starts:

  1;

  1;

  1,1;

  1,1,1,1,1;

  1,1,1,2,2,2,2,1,1,1;

  1,1,1,2,3,3,4,4,4,4,4,3,3,2,1,1,1;

MAPLE

br:=proc(n) options operator, arrow: sum(q^i, i=0..n-1) end proc: f:=proc(n) options operator, arrow: product(br(j), j=1..n) end proc: cbr:=proc(n, k) options operator, arrow: f(n)/(f(k)*f(n-k)) end proc: P:=proc(n) options operator, arrow: sort(expand(simplify((q+1)*cbr(2*n, n)/(br(n+1)*(1+q^n))))) end proc: 1; for n to 7 do seq(coeff(P(n), q, k), k=0..(n-1)^2) end do; # yields sequence in triangular form

MATHEMATICA

g[k_] := (1 - t^k)/(1 - t);

gpol[n_, k_] := If[0 <= k <= n, Product[g[n - j + 1]/g[j], {j, 1, k}], 0];

P[n_] := ((1 + t)/(1 + t^n)) gpol[2n, n]/Sum[t^k, {k, 0, n}];

T[n_] := CoefficientList[P[n] + O[t]^(n^2), t]; T[0] = {1};

T /@ Range[0, 7] // Flatten (* Jean-Fran├žois Alcover, Feb 16 2021 *)

CROSSREFS

Cf. A000108, A145885.

Sequence in context: A152907 A078786 A102677 * A030368 A258383 A037805

Adjacent sequences:  A145881 A145882 A145883 * A145885 A145886 A145887

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Nov 06 2008

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 5 08:27 EDT 2021. Contains 346464 sequences. (Running on oeis4.)