

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*(n1)/2, read by rows.


7



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,6


COMMENTS

An upjump j occurs at position i in p if p_{i} > p_{i1} 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_{i1}. A downjump j occurs at position i in p if p_{i} < p_{i1} 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_{i1}. 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 leftwarddownjumps of p plus the number of descents of p equals k.
T(n,k) equals the number of coverinclusive Dyck tilings whose lower boundary is the zigzag path of order n (UD)^n, and which have k tiles.
A leftwarddownjump 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}.
Coverinclusive 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, Doubledimer 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:927, 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(uj, o+j1)*x^(j1), j=1..u)+
add(b(u+j1, oj)*x^(j1), 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 Dycktilingribbon bijection, described in the KimMeszarosPanovaWilson 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=03 give: A000012, A000217(n1) for n>0, A002415(n1) for n>0, A291288(n3) 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



