(I agree with the points I don't quote here) General reiteration on notation: O-1 is the maximum allowed overlap, overlap of O is already not allowed (it was this way in your first message).
On Wed, Oct 22, 2008 at 3:08 AM, Ed Porter <[EMAIL PROTECTED]> wrote: > > T(N,S,O) = SUM FROM X = 0 TO S-O OF C(S, S-X)*C(N-S, X) > To match with the explanation of the size of the overlap, I intended T(N,S,O)= C(S,S)*C(N-S,S-S)+ C(S,S-1)*C(N-S,S-(S-1))+ ...+C(S,O)*C(N-S,S-O) to be parsed as T(N,S,O) = SUM FROM X =O TO S OF C(S,X)*C(N-S,S-X) > > Comparing this to C(S,X)*C(N-S,S-X) --- it appears that T(N,S,O) is equal to > the number of all combinations calculated by C(S,X)*C(N-S,S-X) where X is > greater than O, Thus it is an attempt to enumerate all such combinations in > which the overlap is more than O and thus which should be excluded from A. > I don't exclude them from A, as I don't know which of them will go to A and which will get banned multiple times. I exclude them from overall pool of C(N,S). > > --First, yes, each new assembly of length S added to the working set lowers > the number of remaining assemblies that we'll be able to add later, but > adding a given new assembly will ban not T(N,S,O) assemblies, but rather > only all those assemblies that overlap with it by more than O nodes. > But T(N,S,O) IS the number of all those assemblies that overlap with a given assembly by O or more nodes (having from X=O to X=S nodes of overlap). > > --Second, what are the cases where assemblies will be banned multiple times > that you mentioned in the above text? > It's one of the reasons it's a lower bound: in reality, some of the assemblies are banned multiple times, which leaves more free assemblies that could be added to the working set later. > > --Third --- as mentioned in my last group of comments --- why doesn't A = > C(N,S) – T(N,S,O), since C(N,S) is the total number of combinations of > length S that can be formed from N nodes, and T(N,S,O) appears to enumerate > all the combinations that occur with each possible overlap value greater O. > It's only overlap with one given assembly, blind to any other interactions, it says nothing about ideal combination of assemblies that manages to keep the overlap between each pair in check. > > --Fifth, is possible that even though T(N,S,O) appears to enumerate all > possible combinations in which all sets overlap by more than O, that it > fails to take into account possible combinations of sets of size S in which > some sets overlap by more than O and others do not? > > --in which case T(N,S,O) would be smaller than the number of all prohibited > combinations of sets of length S. Or would all the possible sets of length > S which overlap be have been properly taken into account in the above > formula for T? > T doesn't reason about combinations of sets, it's a filter on the individual sets from the total of C(N,S). > > --Sixth, if C(S,X)*C(N-S,S-X) enumerates all possible combinations having an > overlap of X, why can't one calculate A as follows? > > A = SUM FROM X = 0 TO O OF C(S,X)*C(N-S,S-X) > Because some of these sets intersect with each other, you can't include them all. -- Vladimir Nesov [EMAIL PROTECTED] http://causalityrelay.wordpress.com/ ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=117534816-b15a34 Powered by Listbox: http://www.listbox.com