login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
Adam H. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, C. McBee, Coprime and prime labelings of graphs, arXiv preprint arXiv:1604.07698 [math.CO], 2016.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
FORMULA
a(A284875(n)) = 1. - Jonathan Sondow, May 21 2017
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]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 18}] (* Jean-François Alcover, Nov 08 2017, after Alois P. Heinz *)
CROSSREFS
Sequence in context: A067616 A348992 A199377 * A019856 A124603 A199722
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jun 20 2012
EXTENSIONS
Terms a(24) and beyond from Kevin Cuadrado, Dec 01 2020
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 06:53 EDT 2024. Contains 370953 sequences. (Running on oeis4.)