A000341 Number of ways to pair up {1..2n} so sum of each pair is prime.

1, 2, 3, 6, 26, 96, 210, 1106, 3759, 12577, 74072, 423884, 2333828, 16736611, 99838851, 630091746, 4525325020, 38848875650, 342245714017, 3335164762941, 31315463942337, 241353231085002, 2350106537365732, 17903852593938447, 158065352670318614, 1815064841856534244, 20577063085601738871, 276081763499377227299

Offset: 1

Author

S. J. Greenfield (greenfie(AT)math.rutgers.edu)

Keywords

• nonn
• nice

Examples

			For n=4, there are 6 ways to pair up {1, 2, 3, 4, 5, 6, 7, 8} so that each pair sums to a prime:
1+2, 3+4, 5+8, 6+7
1+2, 3+8, 4+7, 5+6
1+4, 2+3, 5+8, 6+7
1+4, 2+5, 3+8, 6+7
1+6, 2+3, 4+7, 5+8
1+6, 2+5, 3+8, 4+7
Therefore a(4) = 6. - _Michael B. Porter_, Jul 19 2016
		

Links

• Martin Fuller, Table of n, a(n) for n = 1..36
• L. E. Greenfield and S. J. Greenfield, Some Problems of Combinatorial Number Theory Related to Bertrand's Postulate, J. Integer Sequences, 1998, #98.1.2.

Crossrefs

Cf. A005326, A009692.

Programs

Maple

f:= proc(n) local M;
  M:= Matrix(n,n,(i,j) -> `if`(isprime(2*i+2*j-1),1,0));
  LinearAlgebra:-Permanent(M)
end proc:
map(f, [$1..20]); # Robert Israel, Jul 19 2016

Mathematica

a[n_] := Permanent[ Array[ Boole[ PrimeQ[2*#1 + 2*#2 - 1]] & , {n, n}]]; Table[an = a[n]; Print[an]; an, {n, 1, 20}] (* Jean-François Alcover, Oct 21 2011, after T. D. Noe, updated Feb 07 2016 *)

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,24,a=matrix(n,n,i,j,isprime(2*(i+j)-1));print1(permRWNb(a)", ")) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

PARI

a(n)=matpermanent(matrix(n,n,i,j,isprime(2*(i+j)-1))); \\ Martin Fuller, Sep 22 2023

Formula

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

Extensions

More terms from David W. Wilson

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

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

More terms from Sean A. Irvine, Nov 14 2010