A289489 Number of permutations p of [n] such that in 0p the sum of all jumps equals 2n.

1, 0, 0, 1, 4, 15, 104, 644, 3696, 23388, 151842, 979110, 6445659, 43148963, 290832906, 1977914328, 13574296048, 93787977144, 651970844448, 4558718881927, 32038664402074, 226200869873851, 1603811085640698, 11415385190127413, 81538284501095235

Offset: 0

Author

Alois P. Heinz, Sep 02 2017

Keywords

• nonn

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.

Examples

			a(3) = 1: 312.
a(4) = 4: 3142, 4213, 4231, 4312.
a(5) = 15: 15234, 25134, 31542, 35124, 41235, 42153, 42531, 43152, 45123, 53214, 53241, 53421, 54213, 54231, 54312.
a(6) = 104: 126354, 136254, 142635, 146253, ..., 653421, 654213, 654231, 654312.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..300

Crossrefs

Cf. A291722.

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:
a:= n-> coeff(b(0, n), x, n):
seq(a(n), n=0..26);

Mathematica

b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1,
   Sum[b[u - j, o + j - 1]*x^(j - 1), {j, 1, u}] +
   Sum[b[u + j - 1, o - j]*x^(j - 1), {j, 1, o}]]];
a[n_] := Coefficient[b[0, n], x, n];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Nov 17 2022, after Alois P. Heinz *)

Formula

a(n) = A291722(n,n).

a(n) ~ c * d^n / n^2, where d = 7.7572369635460295... and c = 0.022080578979754... - Vaclav Kotesovec, Nov 17 2022