A325791 - OEIS

A325791

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

%I #12 Nov 01 2020 03:53:49

%S 1,1,1,2,4,20,82,252,1074,7912,39552,152680,776094,5550310,30026848,

%T 108376910

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

%C A necklace permutation is a permutation that is either empty or whose first part is the minimum. A circular subsequence is a sequence of consecutive 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 (1,3,2) are: (), (1), (2), (3), (1,3), (2,1), (3,2), (1,3,2).

%e The a(1) = 1 through a(5) = 20 permutations:

%e (1) (1,2) (1,2,3) (1,2,3,4) (1,2,3,4,5)

%e (1,3,2) (1,3,2,4) (1,2,3,5,4)

%e (1,4,2,3) (1,2,4,3,5)

%e (1,4,3,2) (1,2,4,5,3)

%e (1,2,5,4,3)

%e (1,3,2,5,4)

%e (1,3,4,2,5)

%e (1,3,4,5,2)

%e (1,3,5,2,4)

%e (1,3,5,4,2)

%e (1,4,2,3,5)

%e (1,4,2,5,3)

%e (1,4,3,2,5)

%e (1,4,5,2,3)

%e (1,4,5,3,2)

%e (1,5,2,3,4)

%e (1,5,2,4,3)

%e (1,5,3,2,4)

%e (1,5,3,4,2)

%e (1,5,4,3,2)

%t subalt[q_]:=Union[ReplaceList[q,{___,s__,___}:>{s}],DeleteCases[ReplaceList[q,{t___,__,u___}:>{u,t}],{}]];

%t Table[Length[Select[Permutations[Range[n]],#=={}||First[#]==1&&Range[n*(n+1)/2]==Union[Total/@subalt[#]]&]],{n,0,5}]

%Y Cf. A002033, A008965, A032153, A103295, A126796, A304793, A325684, A325781, A325786, A325788, A325789, A325790.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, May 23 2019

%E a(11)-a(15) from _Bert Dobbelaere_, Nov 01 2020