|
%I #39 Feb 24 2023 12:01:08
%S 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 1177,10,1860,7144,15,170,27156,178,64,2,6335,6334,15592,4522,3230,
%U 113926,99010,72256,114606,199042,1,198518,151036,236203,8557,26542,21388
%N Number of minimal coprime labelings for the complete bipartite graph K_{n,n}.
%C 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 Kevin Cuadrado, <a href="/A213806/b213806.txt">Table of n, a(n) for n = 1..105</a>
%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>
%F a(A284875(n)) = 1. - _Jonathan Sondow_, May 21 2017
%e a(1) = 1: the two label sets are {{1}, {2}} with m=2.
%e a(2) = 1: {{1,3}, {2,4}} with m=4.
%e 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 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 a(5) = 1: {{2,4,5,8,10}, {1,3,7,9,11}}.
%e 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 b:= proc(n, k, t, s) option remember;
%p `if`(nops(s)>=t and k>=t, binomial(nops(s), t),
%p `if`(n<1, 0, b(n-1, k, t, s)+ b(n-1, k+1, t,
%p select(x-> x<>n and igcd(n, x)=1, s))))
%p end:
%p g:= proc(n) option remember; local m, r;
%p for m from `if`(n=1, 2, g(n-1)[1]) do
%p r:= b(m-1, 1, n, select(x-> igcd(m, x)=1, {$1..m-1}));
%p if r>0 then break fi
%p od; [m, r]
%p end:
%p a:= n-> g(n)[2]:
%p seq(a(n), n=1..11);
%t 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 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 a[n_] := a[n] = g[n][[2]];
%t Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 18}] (* _Jean-François Alcover_, Nov 08 2017, after _Alois P. Heinz_ *)
%Y Cf. A213273, A284875, A291465.
%K nonn
%O 1,3
%A _Alois P. Heinz_, Jun 20 2012
%E Terms a(24) and beyond from _Kevin Cuadrado_, Dec 01 2020
|
