A009679 Number of partitions of {1, ..., 2n} into coprime pairs.

1, 2, 4, 18, 60, 252, 1860, 9552, 59616, 565920, 4051872, 33805440, 465239808, 4294865664, 35413136640, 768372168960, 8757710173440, 79772814777600, 1986906367584000, 22082635812268800, 280886415019776000, 7683780010315046400

Offset: 1

Author

David W. Wilson

Keywords

• nonn

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..30 calculated by Herman Jamke's code.
• Carl Pomerance, Coprime permutations, arXiv:2203.03085 [math.NT], 2022.

Crossrefs

Cf. A001147 for the number of partitions (pairings) in unrestricted pairs.

Programs

PARI

permRWNb(a)=n=matsize(a)[1]; if(n==1,return(a[1,1])); sg=1; nc=0; in=vectorv(n); x=in;x=a[,n]-sum(j=1,n,a[,j])/2; p=prod(i=1,n,x[i]); for(k=1,2^(n-1)-1,sg=-sg; j=valuation(k,2)+1;z=1-2*in[j]; in[j]+=z; nc+=z; x+=z*a[,j]; p+=prod(i=1,n,x[i],sg)); return(2*(2*(n%2)-1)*p)
for(n=1,26,a=matrix(n,n,i,j,gcd(2*i,2*j-1)==1);print1(permRWNb(a)", ")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

Formula

a(n) = sqrt(A005326(2n)). - T. D. Noe, Feb 10 2007

a(n) = permanent(m), where the n X n matrix m is defined by m(i,j) = 1 or 0, depending on whether gcd(2i,2j-1) is 1 or >1, respectively. - T. D. Noe, Feb 11 2007

Extensions

More terms from T. D. Noe, Feb 10 2007

More terms from T. D. Noe, Feb 11 2007