A005326 -id:A005326 - cp's OEIS frontend

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

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

			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

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.

Cf. A005326, A009692.

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

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 *)

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

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

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

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

A320843 Number of permutations sigma of {1,2,...,n} such that sigma(i) divides i or i divides sigma(i) for 1 <= i <= n.

Original entry on oeis.org

1, 1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679, 87328, 90478, 435812, 449586, 1939684, 3853278, 8650900, 8840110, 60035322, 80605209, 177211024, 368759752, 1380348224, 1401414640, 8892787136, 9014369784, 33923638848, 59455553072, 126536289568, 207587882368

Offset: 0

Seiichi Manyama, Dec 18 2018

nonn

			In case n = 4:
permutation
------------
[1, 2, 3, 4]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 4, 3, 1]
[3, 2, 1, 4]
[3, 4, 1, 2]
[4, 1, 3, 2]
[4, 2, 3, 1]

Carl Pomerance, Coprime permutations, arXiv:2203.03085 [math.NT], 2022.
Carl Pomerance, Permutations with arithmetic constraints, arXiv:2206.01699 [math.NT], 2022.

Cf. A005326, A263987.

a[n_] := a[n] = If[n == 0, 1,Permanent[Table[If[Divisible[i, j] || Divisible[j, i], 1, 0], {i, n}, {j, n}]]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 22}] (* Jean-François Alcover, Jun 25 2022 *)

a(n) = matpermanent(matrix(n, n, i, j, if (!(i%j) || !(j%i), 1, 0))); \\ Michel Marcus, Dec 30 2018

a(n) = Permanent((x_{ij})) with x_{ij} = 1 if i divides j or j divides i and x_{ij} = 0 otherwise for i,j = 1,...,n. - M. Farrokhi D. G., Dec 30 2018

a(0), a(24)-a(30) from Alois P. Heinz, Dec 19 2018

a(31)-a(35) from M. Farrokhi D. G., Dec 30 2018

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

Original entry on oeis.org

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

Offset: 1

David W. Wilson

nonn

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.

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

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

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

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

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

A085244 Permanent of the symmetric n X n matrix M defined by M(i,j) = gcd(i,j) for 1 <= i,j <= n.

Original entry on oeis.org

1, 3, 14, 112, 872, 14372, 154480, 3098480, 59710816, 1688186176, 27925409152, 1327833590272, 25675495200768, 1017195720916224, 47444016840290304, 2267031138313024512, 56480432945454004224, 4051971981329937580032

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Aug 11 2003

nonn

Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007, Table of n, a(n) for n = 1..23

Cf. A001088, A005326.

permRWNb(a)=n=matsize(a)[1];if(n==1,return(a[1,1]));sg=1;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;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(i,j));print1(permRWNb(a)",")) - Herman Jamke (hermanjamke(AT)fastmail.fm), May 13 2007

More terms from Vladeta Jovovic, Aug 13 2003

A351722 a(n) is the number of permutations p of {1, 2, ..., 2n} such that for any k in 1..2n, k and p(k) do not share a common 1-bit.

Original entry on oeis.org

1, 1, 1, 1, 1, 9, 9, 1, 1, 121, 1089, 729, 729, 1521, 169, 1, 1, 2601, 314721, 1771561, 15944049

Offset: 0

Rémy Sigrist, Apr 06 2022

By the pigeonhole principle, and simply considering parities of k and p(k), there are no such permutation of {1, 2, ..., 2*n+1}.

			For n = 5:
- we have the following 9 permutations (shown in decimal and in binary):
  p\k  1 2 3 4  5 6 7 8 9 10 |    1   10  11 100  101  110  111 1000 1001 1010
  --- -----------------------+------------------------------------------------
  p1   6 5 4 3 10 9 8 7 2  1 |  110  101 100  11 1010 1001 1000  111   10    1
  p2  10 5 4 3  2 9 8 7 6  1 | 1010  101 100  11   10 1001 1000  111  110    1
  p3   2 5 4 3 10 9 8 7 6  1 |   10  101 100  11 1010 1001 1000  111  110    1
  p4   6 9 4 3 10 1 8 7 2  5 |  110 1001 100  11 1010    1 1000  111   10  101
  p5   6 1 4 3 10 9 8 7 2  5 |  110    1 100  11 1010 1001 1000  111   10  101
  p6  10 9 4 3  2 1 8 7 6  5 | 1010 1001 100  11   10    1 1000  111  110  101
  p7   2 9 4 3 10 1 8 7 6  5 |   10 1001 100  11 1010    1 1000  111  110  101
  p8  10 1 4 3  2 9 8 7 6  5 | 1010    1 100  11   10 1001 1000  111  110  101
  p9   2 1 4 3 10 9 8 7 6  5 |   10    1 100  11 1010 1001 1000  111  110  101
- so a(5) = 9.

Cf. A000225, A005326, A109468, A253515, A352857.

a(n) = matpermanent(matrix(2*n, 2*n, i,j, bitand(i,j)==0))

a(n) = 1 for any n in A000225 (the only solution is k -> 2*n+1-k).

a(2^k) = 1 for any k >= 0 (the only solution is row 2^k in A253515).

A106489 Triangle read by rows: T(n,k) is the number of short bushes with n edges and having the leftmost leaf at height k (a short bush is an ordered tree with no nodes of outdegree 1).

Original entry on oeis.org

1, 1, 2, 1, 4, 2, 9, 5, 1, 21, 12, 3, 51, 30, 9, 1, 127, 76, 25, 4, 323, 196, 69, 14, 1, 835, 512, 189, 44, 5, 2188, 1353, 518, 133, 20, 1, 5798, 3610, 1422, 392, 70, 6, 15511, 9713, 3915, 1140, 230, 27, 1, 41835, 26324, 10813, 3288, 726, 104, 7, 113634, 71799, 29964

Offset: 2

Emeric Deutsch, May 29 2005

Basically, the mirror image of A020474. Row n has floor(n/2) terms (first row is row 2). Row sums yield the Riordan numbers (A005043). Column 1 yields the Motzkin numbers (A001006); column 2 yields A002026; column 3 yields A005322; column 4 yields A005323; column 4 yields A005324; column 5 yields A005325; column 6 yields A005326.

T(n,k) is the number of Riordan paths (Motzkin paths with no flatsteps on the x-axis) with k returns to the x-axis. For example, T(6,2) = 5 counts UDUFFD, UDUUDD, UFDUFD, UFFDUD, UUDDUD where U = (1,1) is an upstep, F = (1,0) is a flatstep, and D = (1,-1) is a downstep. - David Callan, Dec 12 2021

			Column 1 yields the Motzkin numbers: indeed, if from each short bush, having leftmost leaf at height 1, we drop the leftmost edge, then we obtain the so-called bushes, known to be counted by the Motzkin numbers.
Triangle begins:
   1;
   1;
   2,  1;
   4,  2;
   9,  5,  1;
  21, 12,  3;
  51, 30,  9,  1.

F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
Sen-Peng Eu, Shu-Chung Liu, and Yeong-Nan Yeh, Taylor expansions for Catalan and Motzkin numbers, Advances in Applied Mathematics 29, Issue 3 (2002), 345-357 (see p. 352).

Cf. A020474, A005043, A001006, A002026, A005322, A005323, A005324, A005325, A005326, A064189.

S:=1/2/(z+z^2)*(1+z-sqrt(1-2*z-3*z^2)): G:=simplify(t*z^2*S/(1-z*S-t*z^2*S)): Gserz:=simplify(series(G,z=0,19)): for n from 2 to 17 do P[n]:=sort(coeff(Gserz,z^n)) od: for n from 2 to 17 do seq(coeff(P[n],t^k),k=1..floor(n/2)) od; # yields sequence in triangular form

(* To generate the sequence *)
CoefficientList[CoefficientList[Series[(1-t-2xt^2-Sqrt[1-2t-3t^2])/(2t^2(1-x+xt+x^2t^2)), {t,0,10}], t], x] // Flatten
(* To generate the triangle *)
CoefficientList[Series[(1-t-2xt^2-Sqrt[1-2t-3t^2])/(2t^2(1-x+xt+x^2t^2)), {t, 0, 10}], {t, x}] // MatrixForm
Table[If[n < 2 k, 0, GegenbauerC[n-2k,-n+k-1,-1/2](k+1)/(n-k+1)], {n,0,10}, {k,0,5}] // MatrixForm
(* Emanuele Munarini, Feb 10 2018 *)

G.f.: tz^2*S/(1 - zS - tz^2*S), where S = S(z) = (1 + z - sqrt(1 - 2z - 3z^2))/(2z(1+z)) is the g.f. of the short bushes (the Riordan numbers; A005043).
a(n,k) = T(n-k+1, n-2*k)*(k+1)/(n-k+1), for n >= 2k, where T(n,k) = A027907(n,k) are the trinomial coefficients. - Emanuele Munarini, Feb 10 2018
The rows are the antidiagonals of the Motzkin triangle A064189. - Peter Luschny, Feb 01 2025

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A320843 Number of permutations sigma of {1,2,...,n} such that sigma(i) divides i or i divides sigma(i) for 1 <= i <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A085244 Permanent of the symmetric n X n matrix M defined by M(i,j) = gcd(i,j) for 1 <= i,j <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A351722 a(n) is the number of permutations p of {1, 2, ..., 2*n} such that for any k in 1..2*n, k and p(k) do not share a common 1-bit.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A106489 Triangle read by rows: T(n,k) is the number of short bushes with n edges and having the leftmost leaf at height k (a short bush is an ordered tree with no nodes of outdegree 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A351722 a(n) is the number of permutations p of {1, 2, ..., 2n} such that for any k in 1..2n, k and p(k) do not share a common 1-bit.