A073090 Number of permutations p from (1,2,3,...,n) to (1,2,3...,n) such that 1/p(1)+2/p(2)+...+n/p(n) is an integer.

1, 1, 1, 1, 2, 2, 8, 8, 22, 104, 1128, 1128, 14520, 14520, 229734, 3217088, 21157428, 21157428

Offset: 0

Author

Benoit Cloitre, Aug 18 2002

Keywords

• nonn
• more

Examples

			p(1,2)=(1,2) is the only permutation such that 1/p(1)+2/p(2) is an integer hence a(2)=1.
a(4) = 2: 1234, 2431.
a(5) = 2: 12345, 24315.
a(6) = 8: 123456, 146253, 216453, 243156, 312654, 342651, 621354, 641352.
a(7) = 8: 1234567, 1462537, 2164537, 2431567, 3126547, 3426517, 6213547, 6413527.
		

Crossrefs

Cf. A000040, A349257.

Programs

PARI

a(n)=if(n<0,0,sum(k=1,n!,if(frac(sum(i=1,n,i/component(numtoperm(n,k),i))),0,1)))

Formula

For each prime p: a(p) = a(p-1). - Alois P. Heinz, Nov 08 2021

Extensions

More terms from John W. Layman, Feb 06 2004

Corrected by Benoit Cloitre, Feb 21 2004

a(14)-a(15) from Matthijs Coster, Mar 22 2017

a(0)=1 prepended by Alois P. Heinz, Nov 08 2021

a(16)-a(17) from Jinyuan Wang, Mar 05 2025