A291722 Number T(n,k) of permutations p of [n] such that in 0p the sum of all jumps equals k + n; triangle T(n,k), n >= 0, 0 <= k <= n*(n-1)/2, read by rows.

1, 1, 1, 1, 1, 3, 1, 1, 1, 6, 6, 5, 4, 1, 1, 1, 10, 20, 20, 26, 15, 15, 6, 5, 1, 1, 1, 15, 50, 70, 105, 106, 104, 90, 65, 51, 27, 21, 7, 6, 1, 1, 1, 21, 105, 210, 350, 497, 554, 644, 567, 574, 420, 386, 238, 203, 105, 85, 35, 28, 8, 7, 1, 1

Offset: 0

Author

Alois P. Heinz, Aug 30 2017

Keywords

• nonn
• tabf

Comments

An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here.

From David B. Wilson, Dec 14 2018: (Start)

T(n,k) equals the number of permutations p of [n] such that twice the sum of the leftward-down-jumps of p plus the number of descents of p equals k.

T(n,k) equals the number of cover-inclusive Dyck tilings whose lower boundary is the zig-zag path of order n (UD)^n, and which have k tiles.

A leftward-down-jump j occurs at position i in p if p_{i} > p_{i+1} and there are j positions k for which k p_k > p_{i+1}.

Cover-inclusive Dyck tilings are defined in the Kenyon and Wilson link below. (End)

Examples

			T(4,0) = 1: 1234.
T(4,1) = 6: 1243, 1324, 1342, 2134, 2314, 2341.
T(4,2) = 6: 1432, 2143, 2431, 3214, 3241, 3421.
T(4,3) = 5: 1423, 2413, 3124, 3412, 4321.
T(4,4) = 4: 3142, 4213, 4231, 4312.
T(4,5) = 1: 4123.
T(4,6) = 1: 4132.
T(5,5) = 15: 15234, 25134, 31542, 35124, 41235, 42153, 42531, 43152, 45123, 53214, 53241, 53421, 54213, 54231, 54312.
Triangle T(n,k) begins:
  1;
  1;
  1,  1;
  1,  3,  1,  1;
  1,  6,  6,  5,   4,   1,   1;
  1, 10, 20, 20,  26,  15,  15,  6,  5,  1,  1;
  1, 15, 50, 70, 105, 106, 104, 90, 65, 51, 27, 21, 7, 6, 1, 1;
		

Links

• Alois P. Heinz, Rows n = 0..50, flattened
• R. W. Kenyon, D. B. Wilson, Double-dimer pairings and skew Young diagrams, The Electronic Journal of Combinatorics 18(1) #P130, 2011.
• J. S. Kim, K. Mészáros, G. Panova, and D. B. Wilson. Dyck tilings, increasing trees, descents, and inversions, Journal of Combinatorial Theory A 122:9-27, 2014.

Crossrefs

Columns k=0-3 give: A000012, A000217(n-1) for n>0, A002415(n-1) for n>0, A291288(n-3) for n>0.

Row sums give A000142.

T(n,n) gives A289489.

Cf. A005990, A008292, A123125, A173018, A258829, A263776, A316292, A316293.

Programs

Maple

b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,
      add(b(u-j, o+j-1)*x^(j-1), j=1..u)+
      add(b(u+j-1, o-j)*x^(j-1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(0, n)):
seq(T(n), n=0..10);

Mathematica

(* Generating function for tiles for Dyck tilings above the zigzag path of order n *)
(* Computed by looking at descents in the insertion sequence for the Dyck-tiling-ribbon bijection, described in the Kim-Meszaros-Panova-Wilson reference *)
(* Since it's above the zigzag, all insertion positions are even *)
(* When the second argument is specified, refines by position of last insertion *)
tilegen[n_, sn_] := tilegen[n, sn] = If[n == 0 || n == 1, 1,
    Sum[tilegen[n - 1, j] If[j >= sn, t^(j - sn + 1), 1] //
      Expand, {j, 0, 2 (n - 2), 2}]
    ];
tilegen[n_] := tilegen[n + 1, 2 n];
T[n_, k_] := Coefficient[tilegen[n], t, k]; (* David B. Wilson, Dec 14 2018 *)

Formula

Sum_{k>=0} k * T(n,k) = A005990(n).