login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060350 The sum over all subsets S of [n] of the squares of the number of permutations with descent set = S. 14
1, 1, 2, 10, 88, 1216, 24176, 654424, 23136128, 1035227008, 57186502912, 3822411268864, 304059285928960, 28385946491599360, 3073391215118186496, 381995951933025287680, 54020316243835807039488, 8624091617045072628121600, 1543536018434416280510332928 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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

LINKS

Vaclav Kotesovec, Table of n, a(n) for n = 0..250 (terms 0..150 from 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

EXAMPLE

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.

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

CROSSREFS

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

Row sums of A259465.

Column k=2 of A334622.

Sequence in context: A186448 A144002 A209884 * A270923 A096658 A346371

Adjacent sequences:  A060347 A060348 A060349 * A060351 A060352 A060353

KEYWORD

nonn

AUTHOR

Mike Zabrocki, Mar 31 2001

EXTENSIONS

Two more terms from Max Alekseyev, May 06 2009

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 21:14 EDT 2022. Contains 354110 sequences. (Running on oeis4.)