A262233 Number of ordered pairs (p,q) of permutations of [n] with equal up-down signatures and p(1)=1 if n>0.

1, 1, 1, 3, 20, 220, 3648, 84616, 2617696, 104112576, 5176135040, 314525766016, 22934467613184, 1976385358538240, 198701625441195520, 23050434113386398720, 3055967615464202301440, 459172688072604359835648, 77616824553405653653094400

Offset: 0

Author

Alois P. Heinz, Sep 15 2015

Keywords

• nonn

Examples

			a(1) = 1: (1,1).
a(2) = 1: (12,12).
a(3) = 3: (123,123), (132,132), (132,231).
a(4) = 20: (1234,1234), (1243,1243), (1243,1342), (1243,2341), (1324,1324), (1324,1423), (1324,2314), (1324,2413), (1324,3412), (1342,1243), (1342,1342), (1342,2341), (1423,1324), (1423,1423), (1423,2314), (1423,2413), (1423,3412), (1432,1432), (1432,2431), (1432,3421).
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..250 (terms 0..110 from Alois P. Heinz)

Crossrefs

Cf. A060350, A262234, A262241.

Programs

Maple

b:= proc(u, o, h) option remember; `if`(u+o=0, 1,
      add(add(b(u-j, o+j-1, h+i-1), i=1..u+o-h), j=1..u)+
      add(add(b(u+j-1, o-j, h-i), i=1..h), j=1..o))
    end:
a:= n-> `if`(n=0, 1, add(b(j-1, n-j, n-1), j=1..n)):
seq(a(n), n=0..20);

Mathematica

b[u_, o_, h_] := b[u, o, h] = If[u + o == 0, 1,
   Sum[Sum[b[u - j, o + j - 1, h + i - 1], {i, 1, u + o - h}], {j, 1, u}]+
   Sum[Sum[b[u + j - 1, o - j, h - i], {i, 1, h}], {j, 1, o}]];
a[n_] := If[n == 0, 1, Sum[b[j - 1, n - j, n - 1], {j, 1, n}]];
a /@ Range[0, 20] (* Jean-François Alcover, Jan 02 2021, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n * n!^2 / n, where d = 0.552406011965766199179395470003589240257321... and c = 1.48557711044485933585341072480938... - Vaclav Kotesovec, Sep 18 2020