A325790 Number of permutations of {1..n} such that every positive integer from 1 to n * (n + 1)/2 is the sum of some circular subsequence.

1, 1, 2, 6, 16, 100, 492, 1764, 8592, 71208, 395520, 1679480, 9313128, 72154030, 420375872, 1625653650

Offset

0,3

Comments

A circular subsequence is a sequence of consecutive non-overlapping terms where the last and first parts are also considered consecutive. The only circular subsequence of maximum length is the sequence itself (not any rotation of it). For example, the circular subsequences of (2,1,3) are: (), (1), (2), (3), (1,3), (2,1), (3,2), (2,1,3).

Links

Table of n, a(n) for n=0..15.

Example

The a(1) = 1 through a(4) = 16 permutations:
  (1)  (1,2)  (1,2,3)  (1,2,3,4)
       (2,1)  (1,3,2)  (1,3,2,4)
              (2,1,3)  (1,4,2,3)
              (2,3,1)  (1,4,3,2)
              (3,1,2)  (2,1,4,3)
              (3,2,1)  (2,3,1,4)
                       (2,3,4,1)
                       (2,4,1,3)
                       (3,1,4,2)
                       (3,2,1,4)
                       (3,2,4,1)
                       (3,4,1,2)
                       (4,1,2,3)
                       (4,1,3,2)
                       (4,2,3,1)
                       (4,3,2,1)

Mathematica

subalt[q_]:=Union[ReplaceList[q, {___, s__, ___}:>{s}], DeleteCases[ReplaceList[q, {t___, __, u___}:>{u, t}], {}]];
Table[Length[Select[Permutations[Range[n]], Range[n*(n+1)/2]==Union[Total/@subalt[#]]&]], {n, 0, 5}]

Prog

(PARI)
weigh(p)={my(b=0); for(i=1, #p, my(s=0, j=i); for(k=1, #p, s+=p[j]; if(!bittest(b, s), b=bitor(b, 1<<s)); j=if(j==#p, 1, j+1))); hammingweight(b)}
a(n)={my(e=n*(n+1)/2, c=0); forperm(n, p, if(weigh(p)==e, c++)); c} \\ Andrew Howroyd, Aug 16 2019

Crossrefs

Cf. A002033, A008965, A032153, A103295, A103300, A126796, A325684, A325781, A325788, A325791.

Sequence in context: A147932 A147923 A341838 * A144690 A317351 A296108

Adjacent sequences: A325787 A325788 A325789 * A325791 A325792 A325793

Keyword

nonn,more

Author

Gus Wiseman, May 23 2019

Extensions

a(10)-a(12) from Andrew Howroyd, Aug 18 2019

a(13)-a(15) from Bert Dobbelaere, Nov 01 2020

Status

approved