cp's OEIS Frontend

A213806 Number of minimal coprime labelings for the complete bipartite graph K_{n,n}.

%I A213806 #40 Feb 16 2025 08:33:17
%S A213806 1,1,7,3,1,3,4,5,1,9,1,1,39,2,46,16,42,68,1,175,1,5,50,1,627,1256,
%T A213806 1177,10,1860,7144,15,170,27156,178,64,2,6335,6334,15592,4522,3230,
%U A213806 113926,99010,72256,114606,199042,1,198518,151036,236203,8557,26542,21388
%N A213806 Number of minimal coprime labelings for the complete bipartite graph K_{n,n}.
%C A213806 A minimal coprime labeling for K_{n,n} uses two disjoint n-subsets of {1,...,m} with minimal m = A213273(n) >= 2*n as labels for the two disjoint vertex sets such that labels of adjacent vertices are relatively prime.  One of the label sets contains m.
%H A213806 Kevin Cuadrado, <a href="/A213806/b213806.txt">Table of n, a(n) for n = 1..105</a>
%H A213806 Adam H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, C. McBee, <a href="https://arxiv.org/abs/1604.07698">Coprime and prime labelings of graphs</a>, arXiv preprint arXiv:1604.07698 [math.CO], 2016.
%H A213806 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>
%F A213806 a(A284875(n)) = 1. - _Jonathan Sondow_, May 21 2017
%e A213806 a(1) = 1: the two label sets are {{1}, {2}} with m=2.
%e A213806 a(2) = 1: {{1,3}, {2,4}} with m=4.
%e A213806 a(3) = 7: {{2,4,5}, {1,3,7}}, {{1,3,5}, {2,4,7}}, {{2,3,4}, {1,5,7}}, {{2,3,6}, {1,5,7}}, {{2,4,6}, {1,5,7}}, {{3,4,6}, {1,5,7}}, {{1,2,4}, {3,5,7}}.
%e A213806 a(4) = 3: {{2,4,7,8}, {1,3,5,9}}, {{2,4,5,8}, {1,3,7,9}}, {{1,2,4,8}, {3,5,7,9}}.
%e A213806 a(5) = 1: {{2,4,5,8,10}, {1,3,7,9,11}}.
%e A213806 a(21) = 1: {{2,4,5,8,10,11,16,20,22,23,25,29,31,32,40,44,46,50,55,58,62}, {1,3,7,9,13,17,19,21,27,37,39,41,43,47,49,51,53,57,59,61,63}}.
%p A213806 b:= proc(n, k, t, s) option remember;
%p A213806       `if`(nops(s)>=t and k>=t, binomial(nops(s), t),
%p A213806       `if`(n<1, 0, b(n-1, k, t, s)+ b(n-1, k+1, t,
%p A213806       select(x-> x<>n and igcd(n, x)=1, s))))
%p A213806     end:
%p A213806 g:= proc(n) option remember; local m, r;
%p A213806       for m from `if`(n=1, 2, g(n-1)[1]) do
%p A213806         r:= b(m-1, 1, n, select(x-> igcd(m, x)=1, {$1..m-1}));
%p A213806         if r>0 then break fi
%p A213806       od; [m, r]
%p A213806     end:
%p A213806 a:= n-> g(n)[2]:
%p A213806 seq(a(n), n=1..11);
%t A213806 b[n_, k_, t_, s_] := b[n, k, t, s] = If[Length[s] >= t && k >= t, Binomial[Length[s], t], If[n < 1, 0, b[n - 1, k, t, s] + b[n - 1, k + 1, t, Select[s, # != n && GCD[n, #] == 1 &]]]];
%t A213806 g[n_] := g[n] = Module[{m, r}, For[ m = If[n == 1, 2, g[n - 1][[1]] ], True, m++, r = b[m - 1, 1, n, Select[Range[1, m - 1], GCD[m, #] == 1 &]]; If [r > 0,  Break[]]]; {m, r}];
%t A213806 a[n_] := a[n] = g[n][[2]];
%t A213806 Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 18}] (* _Jean-François Alcover_, Nov 08 2017, after _Alois P. Heinz_ *)
%Y A213806 Cf. A213273, A284875, A291465.
%K A213806 nonn
%O A213806 1,3
%A A213806 _Alois P. Heinz_, Jun 20 2012
%E A213806 Terms a(24) and beyond from _Kevin Cuadrado_, Dec 01 2020