A060350 The sum over all subsets S of [n] of the squares of the number of permutations with descent set = S.

1, 1, 2, 10, 88, 1216, 24176, 654424, 23136128, 1035227008, 57186502912, 3822411268864, 304059285928960, 28385946491599360, 3073391215118186496, 381995951933025287680, 54020316243835807039488, 8624091617045072628121600, 1543536018434416280510332928

Offset: 0

Author

Mike Zabrocki, Mar 31 2001

Keywords

• nonn

Comments

a(n) = number of ordered pairs of permutations of [n] such that the first has an ascent wherever the second has a descent and vice versa. For example, the pair of permutations (1243, 4123) does not qualify because they have a common ascent starting at location 2, and a(2) = 2 counts (12, 21), (21, 12). - David Callan, Sep 15 2013

Examples

			a(1)=1^2; a(2)=1^2+1^2; a(3)=1^2+2^2+2^2+1^2; a(4)=1^2+3^2+5^2+3^2+3^2+5^2+3^2+1^2.
		

Links

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

Crossrefs

Cf. A060351, A262233, A262234, A262241, A262372.

Row sums of A259465.

Column k=2 of A334622.

Programs

Maple

ct := proc(k) option remember; local i,out,n; if k=0 then RETURN(1); fi; n := floor(evalf(log[2](k)))+1; if k=2^n or k=2^(n+1)-1 then RETURN(1); fi; out := 0; for i from 1 to n do if irem(iquo(k, 2^(i-1)), 2) = 1 and irem(iquo(2*k,2^(i-1)),2) =0 then out := out+(n-1)!/(i-1)!/(n-i)!* ct(floor(irem(k,2^(i-1))+2^(i-2)))*ct(iquo(k,2^i)); fi; od; out; end: seq(add(ct(i)^2,i=floor(2^(n-1))..2^n-1), n=0..15);
# second Maple program:
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-> b(0, n$2):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 02 2015

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_] := b[0, n, n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Nov 11 2015, after Alois P. Heinz *)

Formula

a(n) = A137782(2n) / A000984(n).

a(n) = Sum_{j=0..ceiling(2^(n-1))-1} A060351(n,j)^2. - Alois P. Heinz, Sep 15 2020

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

Extensions

Two more terms from Max Alekseyev, May 06 2009

a(0) prepended, a(18) from Alois P. Heinz, Jul 02 2015