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,6

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<i and p_i > p_k > p_{i+1}.

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

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.

Formula

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

Example

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;

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

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.

Sequence in context: A160752 A186024 A080002 * A297672 A256973 A058057

Adjacent sequences: A291719 A291720 A291721 * A291723 A291724 A291725

Keyword

nonn,tabf

Author

Alois P. Heinz, Aug 30 2017

Status

approved