|
|
A330503
|
|
Number of Sós permutations of {0,1,...,n}.
|
|
1
|
|
|
2, 6, 16, 30, 60, 84, 144, 198, 280, 352, 504, 598, 812, 960, 1152, 1360, 1728, 1938, 2400, 2688, 3080, 3450, 4128, 4500, 5200, 5724, 6440, 7018, 8100, 8618, 9856, 10692, 11696, 12600, 13824, 14652, 16416, 17550, 18960, 20090, 22260, 23306, 25696, 27180, 28888
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
LINKS
|
S. Bockting-Conrad, Y. Kashina, T. K. Petersen, and B. E. Tenner, Sós permutations, arXiv:2007.01132 [math.CO], 2020.
|
|
FORMULA
|
a(n) = (n+1) * Sum_{k=1..n} phi(k), where phi(k) is Euler's totient function.
|
|
EXAMPLE
|
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}.
|
|
MATHEMATICA
|
MapIndexed[(First[#2] + 1) #1 &, Accumulate@ Array[EulerPhi, 45]] (* Michael De Vlieger, Dec 16 2019 *)
|
|
PROG
|
(PARI) a(n)={(n+1)*sum(k=1, n, eulerphi(k))} \\ Andrew Howroyd, Dec 20 2019
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 0, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*(2*A330503(k1)//(k1+1)-1)
j, k1 = j2, n//j2
return (n+1)*(n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 29 2021
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|