Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If we order all the partitions of a integer in a lexicographic order, how can we compute the position of each partition in this order without having to explicitly list all other partitions that precedes it. How is the modification done when we restrict the maximum part and the number of partitions? I would like to use these indices in database search. It would be helpful even if we get a closed form formula when the number of parts is restricted to small number, for example $<15$ and the integer is $< 100$ with each part $<5$.

share|improve this question
    
Knuth's The Art of Computer Programming volume 4A $\S$7.2.1.4 could be helpful. I would think any answer would have to involve the complexity of the partition function. –  Brian Hopkins Oct 15 '13 at 13:48
    
Look up "ranking and unranking of partitions" - it seems like there are ranking/unranking algorithms for the partitions in reverse-lex order but I'm not sure about lex order. –  Gordon Royle Oct 15 '13 at 13:50
add comment

2 Answers 2

Lexicographic order seems more complex than reverse lexicographic order.
In reverse lex order, it becomes straightforward: define p(n,k) as the number of partitions of n with largest part k (alternatively with no more than k parts). It has the well known recursion p(n,k)=p(n,k-1)+p(n-k,k). Then, for any partition, say 5311, here with sum n=10, do
p(5+3+1+1,5 -1) = 23
p(3+1+1,3 -1) = 3
p(1+1,1 -1) = 0
p(1,1 -1) = 0
add them to get 26, and subtract that from p(5+3+1+1)= 42 to get the rank = 16. To see why this works, look at the transpose partitions counted by p(10,4), p(5,2) etc that are clipped of.

share|improve this answer
add comment

Maybe one possibility is to multiply each partition in lexicographic order by the number that represents its position in the sequence. Storing the partitions this way you retrieve the order by dividing the partition stored value by the original integer to partition. And you retrieve the correct partition terms by dividing them by the order. I dont know what the data model is, but of course somehow, together with the series of each "new transformed partition" you would also have to store the original value of the integer to partition, to compare with.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.