A137782 -id:A137782 - 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.

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

Offset: 0

Mike Zabrocki, Mar 31 2001

nonn

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

			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.

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

Cf. A060351, A262233, A262234, A262241, A262372.
Row sums of A259465.
Column k=2 of A334622.

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

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 *)

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

Two more terms from Max Alekseyev, May 06 2009

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

A137783 a(n) = the number of permutations (p(1), p(2), ..., p(2n+1)) of (1, 2, ..., 2n+1) where, for each k (2 <= k <= 2n+1), the sign of (p(k) - p(k-1)) equals the sign of (p(2n+2-k) - p(2n+3-k)).

Original entry on oeis.org

1, 4, 44, 1028, 40864, 2484032, 214050784, 24831582176, 3731039384576, 704879630525696, 163539441616948736, 45712130697710081024, 15150993151215400441856, 5875388829103413298173952, 2635427286694074346846232576, 1353918066433734600362650169344

Offset: 0

Leroy Quet, Feb 10 2008, Feb 14 2008

nonn

There are no such permutations of (1,2,...,2n).

			Consider the permutation (for n = 3): 3,4,5,2,7,6,1. The signs of the differences between adjacent terms form the sequence: ++-+--, which is the negative of its reversal. So this permutation, among others, is counted when n = 3.

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

Cf. A060350, A137782.

{ a(n) = my(s,c,r); s=0; forvec(t=vector(n\2,i,[0,2]), c=0; r=[]; for(j=1,#t, if(t[j]==0,c++, if(t[j]==1,r=concat(r,[j]),r=concat(r,[n-j])); ); ); r=vecsort(r); s+=(-2)^c*if(#r,n!/(r[1]!*prod(j=1,#r-1,(r[j+1]-r[j])!)*(n-r[ #r])!),1) ); s } /* Max Alekseyev */

First 4 terms calculated by Olivier Gérard

Edited and extended by Max Alekseyev, May 09 2009

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions