A375302 a(n) is the rank of row n of A375301 in a lexicographic permutation of [1, ..., n].
0, 0, 5, 14, 5, 119, 5039, 34406, 22589, 10919, 7625519, 83825279, 39916799
Offset: 1
Links
- Blai Bonet, Efficient Algorithms to Rank and Unrank Permutations in Lexicographic Order, Workshop on Search in Artificial Intelligence and Robotics at AAAI, 2008.
- Wendy Myrvold and Frank Ruskey, Ranking and Unranking Permutations in Linear Time.
Programs
-
PARI
\\ Blai Bonet's ranking algorithm rank(P) = {my(n=#P, k=logint(n,2)+1, T=vector(2^(k+1)-1,i,0), r=0); for(i=1, n, my(ctr=P[i], node=2^k+P[i]); for(j=1, k, if(node%2, ctr-=T[(node>>1)<<1]); T[node]++; node=node>>1); T[node]++; r=r*(n+1-i)+ctr); r-sum(k=0, n-1, k!)}; \\ uses function a375301_row from A375301 a(n) = rank(a375301_row(n))
Comments