22
A set of n
positive numbers has 2^n
subsets. We'll call a set "nice" if none of those subsets have the same sum. {2, 4, 5, 8}
is one such nice set. Since none of the subsets has the same sum, we can sort the subsets by sum:
[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]
If we label the numbers [2, 4, 5, 8]
with the symbols [a, b, c, d]
in increasing order, we get the following abstract ordering:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
Another nice set of positive numbers can have the same abstract ordering, or a different one. For instance, [3, 4, 8, 10]
is a nice set with a different abstract ordering:
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]
In this challenge, you must count the number of distinct abstract orderings of nice sets of n
positive numbers. This sequence is OEIS A009997, and the known values, starting at n=1
, are:
1, 1, 2, 14, 516, 124187, 214580603
For instance, for n=3
, the following are the two possible abstract orderings:
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]
For n=4
, the following are the 14 possible abstract orderings, plus an example nice set with that ordering:
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]
The following is not a valid abstract ordering:
{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}
This ordering implies that:
d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e
Summing these inequalities gives:
2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e
which is a contradiction. Your code must not count this ordering. Such counterexamples first appear at n=5
. Example from this paper, example 2.5 on page 3.
This ordering is invalid despite the fact that A < B
implies that A U C < B U C
, for any C
disjoint from A
and B
.
Your code or program must be fast enough that you can run it to completion on n=4
before submitting it.
Submissions may be programs, functions, etc. as usual.
Standard Loopholes are forbidden, as always. This is code golf, so shortest answer in bytes wins. Feel free to ask clarifying questions in the comments.
Long time no see isaac! – orlp – 2018-07-11T01:36:59.143
When $P, Q$ are two subsets, is there any scenario where $P \leq Q$ can be deduced from any information other than $P \subseteq Q$ or $\forall p \in P, q\in Q (p \leq q)$, not counting the initial $a \leq b \leq c \leq \dots $? – orlp – 2018-07-11T02:14:59.350
Answer: yes. $\forall p \in P, q\in Q (p \leq q)$ is not tight enough, example: ${a, c}, {b, c}$. – orlp – 2018-07-11T02:22:03.233
@orlp Good to be back! I think I'll be doing mostly questions for the foreseeable future – isaacg – 2018-07-11T03:47:11.413
Could you also add the 14 possible orderings for n=4? – Peter Taylor – 2018-07-11T12:35:28.063
@PeterTaylor Added – isaacg – 2018-07-11T15:46:26.057