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!)
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. 7

%I #48 Jan 07 2019 03:24:16

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

%T 105,106,104,90,65,51,27,21,7,6,1,1,1,21,105,210,350,497,554,644,567,

%U 574,420,386,238,203,105,85,35,28,8,7,1,1

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

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

%C From _David B. Wilson_, Dec 14 2018: (Start)

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

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

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

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

%H Alois P. Heinz, <a href="/A291722/b291722.txt">Rows n = 0..50, flattened</a>

%H R. W. Kenyon, D. B. Wilson, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p130">Double-dimer pairings and skew Young diagrams</a>, The Electronic Journal of Combinatorics 18(1) #P130, 2011.

%H J. S. Kim, K. Mészáros, G. Panova, and D. B. Wilson. <a href="http://dx.doi.org/10.1016/j.jcta.2013.09.008">Dyck tilings, increasing trees, descents, and inversions</a>, Journal of Combinatorial Theory A 122:9-27, 2014.

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

%e T(4,0) = 1: 1234.

%e T(4,1) = 6: 1243, 1324, 1342, 2134, 2314, 2341.

%e T(4,2) = 6: 1432, 2143, 2431, 3214, 3241, 3421.

%e T(4,3) = 5: 1423, 2413, 3124, 3412, 4321.

%e T(4,4) = 4: 3142, 4213, 4231, 4312.

%e T(4,5) = 1: 4123.

%e T(4,6) = 1: 4132.

%e T(5,5) = 15: 15234, 25134, 31542, 35124, 41235, 42153, 42531, 43152, 45123, 53214, 53241, 53421, 54213, 54231, 54312.

%e Triangle T(n,k) begins:

%e 1;

%e 1;

%e 1, 1;

%e 1, 3, 1, 1;

%e 1, 6, 6, 5, 4, 1, 1;

%e 1, 10, 20, 20, 26, 15, 15, 6, 5, 1, 1;

%e 1, 15, 50, 70, 105, 106, 104, 90, 65, 51, 27, 21, 7, 6, 1, 1;

%p b:= proc(u, o) option remember; expand(`if`(u+o=0, 1,

%p add(b(u-j, o+j-1)*x^(j-1), j=1..u)+

%p add(b(u+j-1, o-j)*x^(j-1), j=1..o)))

%p end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(0, n)):

%p seq(T(n), n=0..10);

%t (* Generating function for tiles for Dyck tilings above the zigzag path of order n *)

%t (* Computed by looking at descents in the insertion sequence for the Dyck-tiling-ribbon bijection, described in the Kim-Meszaros-Panova-Wilson reference *)

%t (* Since it's above the zigzag, all insertion positions are even *)

%t (* When the second argument is specified, refines by position of last insertion *)

%t tilegen[n_, sn_] := tilegen[n, sn] = If[n == 0 || n == 1, 1,

%t Sum[tilegen[n - 1, j] If[j >= sn, t^(j - sn + 1), 1] //

%t Expand, {j, 0, 2 (n - 2), 2}]

%t ];

%t tilegen[n_] := tilegen[n + 1, 2 n];

%t T[n_, k_] := Coefficient[tilegen[n], t, k]; (* _David B. Wilson_, Dec 14 2018 *)

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

%Y Row sums give A000142.

%Y T(n,n) gives A289489.

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

%K nonn,tabf

%O 0,6

%A _Alois P. Heinz_, Aug 30 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 28 04:13 EDT 2024. Contains 371235 sequences. (Running on oeis4.)