|
|
A213806
|
|
Number of minimal coprime labelings for the complete bipartite graph K_{n,n}.
|
|
4
|
|
|
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, 1177, 10, 1860, 7144, 15, 170, 27156, 178, 64, 2, 6335, 6334, 15592, 4522, 3230, 113926, 99010, 72256, 114606, 199042, 1, 198518, 151036, 236203, 8557, 26542, 21388
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
a(1) = 1: the two label sets are {{1}, {2}} with m=2.
a(2) = 1: {{1,3}, {2,4}} with m=4.
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}}.
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}}.
a(5) = 1: {{2,4,5,8,10}, {1,3,7,9,11}}.
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}}.
|
|
MAPLE
|
b:= proc(n, k, t, s) option remember;
`if`(nops(s)>=t and k>=t, binomial(nops(s), t),
`if`(n<1, 0, b(n-1, k, t, s)+ b(n-1, k+1, t,
select(x-> x<>n and igcd(n, x)=1, s))))
end:
g:= proc(n) option remember; local m, r;
for m from `if`(n=1, 2, g(n-1)[1]) do
r:= b(m-1, 1, n, select(x-> igcd(m, x)=1, {$1..m-1}));
if r>0 then break fi
od; [m, r]
end:
a:= n-> g(n)[2]:
seq(a(n), n=1..11);
|
|
MATHEMATICA
|
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 &]]]];
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}];
a[n_] := a[n] = g[n][[2]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|