#15998: Restore some documentation and doctests and a function removed with
#15466
-------------------------------------+-------------------------------------
Reporter: darij | Owner:
Type: defect | Status: positive_review
Priority: major | Milestone: sage-6.2
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Darij Grinberg | Reviewers: Nathann Cohen, Travis
Report Upstream: N/A | Scrimshaw
Branch: | Work issues:
public/combinat/re-15466 | Commit:
Dependencies: | da4bf10359d8a23746de8647904ba2c389f61d59
| Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
> Oh -- but it's only sufficient, not necessary, so I'd have to check the
multiplicative equation in one branch nevertheless.
Ahahahaahah.
Okay, last attempt to convince you that it is not only a sufficient
condition. Let me rewrite better what I said above. We are looking for the
largest value h sur that all elements to the right of x[h] can be replaced
with things below x[h].
1) If the current partition is not of length k, then you know for sure
that your multiplicative equation is satisfied, so the current value of h
is the value you want.
Proof: x[h] is at least 3, and all elements to the right of x[h] are at
most one. Let us say that you have exactly L ones, and we know that you
have at least one unused cell : thus L+1 <= (L+1)(x[h]-1), which is the
opposite of your multiplicative equation, i.e. your code does not enter
the loop in this situation.
(We can now assume that the current partition has length exactly k)
2) If there IS some 1 to the right of x[h] (note that this can be tested
without multiplicative equation too), then the current value of h is the
value you want
Proof: let us say that you have L ones to the right of x[h]. In this case
those ones are a partition of L into integers <= 1, and it is of course
possible to express a partition of t=L+1 into (less) integers <= 2 <=
x[h]-1
( We can now assume that your current partition has length exactly k, and
there is no 1 to the right of x[h])
In this case, the least admissible value for h is the largest value h'
such that x[h'] is at least x[h]+2
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/15998#comment:35>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
