login
Number of Sós permutations of {0,1,...,n}.
1

%I #22 Mar 30 2021 01:42:32

%S 2,6,16,30,60,84,144,198,280,352,504,598,812,960,1152,1360,1728,1938,

%T 2400,2688,3080,3450,4128,4500,5200,5724,6440,7018,8100,8618,9856,

%U 10692,11696,12600,13824,14652,16416,17550,18960,20090,22260,23306,25696,27180,28888

%N Number of Sós permutations of {0,1,...,n}.

%H S. Bockting-Conrad, Y. Kashina, T. K. Petersen, and B. E. Tenner, <a href="https://arxiv.org/abs/2007.01132">Sós permutations</a>, arXiv:2007.01132 [math.CO], 2020.

%F a(n) = (n+1) * Sum_{k=1..n} phi(k), where phi(k) is Euler's totient function.

%F a(n) = (n+1) * A002088(n).

%e For n = 3, the a(3) = 16 Farey functions of {0,1,2,3} are {0123, 3012, 2301, 1230, 0312, 2031, 1203, 3120, 0213, 3021, 1302, 2130, 0321, 1032, 2103, 3210}.

%t MapIndexed[(First[#2] + 1) #1 &, Accumulate@ Array[EulerPhi, 45]] (* _Michael De Vlieger_, Dec 16 2019 *)

%o (PARI) a(n)={(n+1)*sum(k=1, n, eulerphi(k))} \\ _Andrew Howroyd_, Dec 20 2019

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A330503(n):

%o if n == 0:

%o return 0

%o c, j = 0, 2

%o k1 = n//j

%o while k1 > 1:

%o j2 = n//k1 + 1

%o c += (j2-j)*(2*A330503(k1)//(k1+1)-1)

%o j, k1 = j2, n//j2

%o return (n+1)*(n*(n-1)-c+j)//2 # _Chai Wah Wu_, Mar 29 2021

%Y Cf. A002088.

%K easy,nonn

%O 1,1

%A _Bridget Tenner_, Dec 16 2019

%E More terms from _Michael De Vlieger_, Dec 16 2019