|
| |
|
|
A050295
|
|
Number of strongly triple-free subsets of {1, 2, ..., n}.
|
|
4
|
|
|
|
1, 2, 3, 5, 8, 16, 24, 48, 76, 132, 198, 396, 588, 1176, 1764, 2940, 4680, 9360, 13680, 27360, 43776, 72960, 109440, 218880, 330240, 660480, 990720, 1693440, 2709504, 5419008, 8128512, 16257024, 25823232, 43038720, 64558080, 129116160, 194365440, 388730880
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
A set S is strongly triple-free if x in S implies 2x not in S and 3x not in S.
Conjecture: for k=1,2,3,..., a(6k+1)=2a(6k) and a(6k+5)=2a(6k+4) (these relations hold through a(35)). - John W. Layman, Jun 22 2002
From Pradhan Prashanth Kumar (pradhan.ptr(AT)gmail.com), Feb 03 2008:
The conjecture is true. Proof:
Let b(6k+1) = Number of strongly triple-free subsets of {1,2,...,6k+1} which do not contain 6k+1 and c(6k+1) = Number of strongly triple-free subsets of {1,2,...,6k+1} which contain 6k+1. Now a(6k+1) = b(6k+1) + c(6k+1) and b(6k+1) = a(6k).
1) c(6k+1)<=a(6k) : Take any strongly triple-free subset of {1,2,..,6k+1}, which contains 6k+1 and delete 6k+1. The new set is a subset of {1,2,...,6k} and is trongly triple-free. Hence c(6k+1)<=a(6k).
2) c(6k+1)>=a(6k) : Take any strongly triple-free subset of {1,2,...,6k}. Add 6k+1 to it. Since 6k+1 is not divisible by 2 or 3, this new set is still strongly triple-free. Hence c(6k+1)>=a(6k).
This shows that c(6k+1) = a(6k) and therefore a(6k+1) = b(6k+1)+c(6k+1) = 2a(6k). QED
Another proof for the conjecture: a(6k+r) = 2a(6k+r-1) when r={1,5} (with a(0)=1) would be: Any positive integer of form (6k+1) or (6k+5) is neither divisible by 2 nor by 3. Hence adding the number (6k+1) or (6k+5) to the each strongly triple-free subset of {1, ..., 6k} or {1, ..., 6k+4} does not violate the property and hence we would have 2a(6k) or 2a(6k+4) such subsets for a(6k+1) or a(6k+5). - Ramasamy Chandramouli, Aug 30 2008
|
|
|
LINKS
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
