|
Search: id:A007600
|
|
|
| A007600 |
|
Minimal number of subsets in a separating family for a set of n elements.
(Formerly M0456)
|
|
+0
3
|
|
| 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Let j = ceil(log3(n))-1. Then a(n) = 3j+1 if 3^j < n <= 4*3^(j-1); 3j+2 if 4*3^(j-1) < n <= 2*3^j; 3j+3 if 2*3^j < n <= 3^(j+1). - Ralf Stephan, Apr 28 2003
"In 1973, The Hungarian mathematician G. O. H. Katona posed the general problem of determining, for a set of n elements, the minimum number f(n) of subsets in a separating family. This problem was solved in early February, 1982, by the gifted Chinese mathematician Cai Mao-Cheng (Academia Sinica, Peking), during an extended visit to the University of Waterloo." [Honsberger]
Honsberger gives a misattribution: the problem was first solved by Andrew Chi-Chih Yao. - Vince Vatter (vince(AT)mcs.st-and.ac.uk), Apr 24 2006
A007600(A000792(n)) = n; Andrew Chi-Chih Yao attributes this observation to D. E. Muller. - Vince Vatter (vince(AT)mcs.st-and.ac.uk), Apr 24 2006
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, II, Theoret. Computer Sci., 307 (2003), 3-29.
Ross Honsberger, Mathematical Gems III, Dolciani Mathematical Expositions No. 9, Mathematical Association of America, 1985, Cai Mao-Cheng's Solution to Katona's Problem on Families of Separating Subsets, Chapter 18, pages 224 - 239.
M-C. Cai, Solutions to Edmonds' and Katona's problems on families of separating sets, Discrete Math., 47 (1983) 13-21.
A. C.-C. Yao, On a problem of Katona on minimal separating systems, Discrete Math., 15 (1976), 193-199.
|
|
LINKS
|
J.-P. Allouche and J. Shallit, The Ring of k-regular Sequences, II
J. Shallit, k-regular Sequences
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
Gyula O. H. Katona, Home page.
|
|
FORMULA
|
a(n) = min{2p + 3 ceiling(log_3(n/2^p)) | p=0, 1, 2 }.
|
|
MATHEMATICA
|
f[n_] := Min[ Table[2p + 3Ceiling[Log[3, n/2^p]], {p, 0, 2}]]; Table[ f[n], {n, 80}] (from Robert G. Wilson v Jan 15 2005)
|
|
CROSSREFS
|
Positions of increases are in A007601.
Adjacent sequences: A007597 A007598 A007599 this_sequence A007601 A007602 A007603
Sequence in context: A091334 A025280 A096365 this_sequence A091333 A005245 A061373
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
njas, Robert G. Wilson v (rgwv(AT)rgwv.com), Mira Bernstein (mira(AT)math.berkeley.edu)
|
|
|
Search completed in 0.002 seconds
|
