cp's OEIS Frontend

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

%I A060350 #46 Dec 20 2020 12:38:11
%S A060350 1,1,2,10,88,1216,24176,654424,23136128,1035227008,57186502912,
%T A060350 3822411268864,304059285928960,28385946491599360,3073391215118186496,
%U A060350 381995951933025287680,54020316243835807039488,8624091617045072628121600,1543536018434416280510332928
%N A060350 The sum over all subsets S of [n] of the squares of the number of permutations with descent set = S.
%C A060350 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
%H A060350 Vaclav Kotesovec, <a href="/A060350/b060350.txt">Table of n, a(n) for n = 0..250</a> (terms 0..150 from Alois P. Heinz)
%F A060350 a(n) = A137782(2n) / A000984(n).
%F A060350 a(n) = Sum_{j=0..ceiling(2^(n-1))-1} A060351(n,j)^2. - _Alois P. Heinz_, Sep 15 2020
%F A060350 a(n) ~ c * d^n * n!^2, where d = 0.552406011965766199179395470003589240257321... and c = 1.6412834540969426814342654061364... - _Vaclav Kotesovec_, Sep 18 2020
%e A060350 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.
%p A060350 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);
%p A060350 # second Maple program:
%p A060350 b:= proc(u, o, h) option remember; `if`(u+o=0, 1,
%p A060350       add(add(b(u-j, o+j-1, h+i-1), i=1..u+o-h), j=1..u)+
%p A060350       add(add(b(u+j-1, o-j, h-i), i=1..h), j=1..o))
%p A060350     end:
%p A060350 a:= n-> b(0, n$2):
%p A060350 seq(a(n), n=0..20);  # _Alois P. Heinz_, Jul 02 2015
%t A060350 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_ *)
%Y A060350 Cf. A060351, A262233, A262234, A262241, A262372.
%Y A060350 Row sums of A259465.
%Y A060350 Column k=2 of A334622.
%K A060350 nonn
%O A060350 0,3
%A A060350 _Mike Zabrocki_, Mar 31 2001
%E A060350 Two more terms from _Max Alekseyev_, May 06 2009
%E A060350 a(0) prepended, a(18) from _Alois P. Heinz_, Jul 02 2015