A342136 - OEIS

%I #26 Sep 30 2025 10:41:04

%S 1,0,0,0,1,2,6,10,22,101,66,504,2088,3572,14398,49984,108030,191228,

%T 1087758,5005440,14081453,97492234,160186634,939652634,3926077642,

%U 4273706733,41832174879,214185383046,494248121522,6153003414039,38125026176659,13635112709648,39350572537836,511502485322923,1069875349612147,5075263842958032

%N Number of partitions of [2n] into pairs whose sums and differences are primes.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

%F The graph on vertices [2n] and edges connecting pairs with prime sum and difference is bipartite (with odd numbers in one part and even numbers in the other). Hence, a(n) as the number of perfect matchings in this graph is given by the permanent of its reduced adjacency matrix (see PARI code). - _Max Alekseyev_, Sep 30 2025

%e a(4) = 1: {{1,6}, {2,5}, {3,8}, {4,7}}.

%e a(5) = 2: {{1,6}, {2,9}, {3,10}, {4,7}, {5,8}}, {{1,6}, {2,5}, {3,8}, {4,9}, {7,10}}.

%p b:= proc(s) option remember; `if`(s={}, 1, (j-> add(`if`(i<j and

%p       andmap(isprime, [j+i, j-i]), b(s minus {i, j}), 0), i=s))(max(s)))

%p     end:

%p a:= n-> b({$1..2*n}):

%p seq(a(n), n=0..15);

%t b[s_] := b[s] = If[s == {}, 1, With[{j = Max[s]}, Sum[If[i < j && AllTrue[{j+i, j-i}, PrimeQ], b[s ~Complement~ {i, j}], 0], {i, s}]]];

%t a[n_] := b[Range[2n]];

%t a /@ Range[0, 15] (* _Jean-François Alcover_, Aug 25 2021, after _Alois P. Heinz_ *)

%o (PARI) a342136(n) = matpermanent( matrix(n, n, i, j, isprime(2*i-1+2*j) && isprime(abs(2*i-1-2*j))) ); \\ _Max Alekseyev_, Sep 30 2025

%Y Cf. A000341, A009692, A342139, A342155.

%K nonn

%O 0,6

%A _Alois P. Heinz_, Mar 01 2021

%E a(25)-a(35) from _Bert Dobbelaere_, Mar 06 2021