Hello, On Sun, Dec 14, 2008 at 4:04 PM, green351 <mmamashra...@gmail.com> wrote: > > Hi, > This is my first time emailing with a question and my first time > trying to use Sage (I'm a complete programming dunce). I'm trying to > do the following: > Given the tuple (p,q) in Z x Z and integer n I need to count the > number of integer-tuple solutions to the following > (p,q)=(a_1,b_1)+...+(a_n,b_n) subject to the following conditions > - (a_i,b_i) \neq (a_j,b_j) for i, j different > - a_i, b_i >= -1 > - a_i+b_i > 0
What you're trying to count is the number of multiset partitions. I haven't written any code to do this in Sage, but I've been meaning too. So now is a good time to start :-) For an interesting reference on this is Knuth's Art of Computer Programming Volume 4, Fascicle 3 (b). Using the formula found in http://www.emis.de/journals/HOA/IJMMS/22/1213.pdf , we get the following bit of Sage code @cached_function def p(*n): r = len(n) s = sum(n) if s == 0: return 1 result = 0 for k in range(1, s+1): for l in IntegerVectors(k, r, outer=n): nml = tuple(a-b for a,b in zip(n,l)) g = gcd(l) result += sigma(g)/g*sum(l)*p(*nml) return result / s You call it just like p(a,b). We can duplicate Table A-1 in the Knuth fascicle: sage: [ [p(i,j) for j in range(7)] for i in range(6)] [[1, 1, 2, 3, 5, 7, 11], [1, 2, 4, 7, 12, 19, 30], [2, 4, 9, 16, 29, 47, 77], [3, 7, 16, 31, 57, 97, 162], [5, 12, 29, 57, 109, 189, 323], [7, 19, 47, 97, 189, 339, 589]] We can also get the specific values cited in the paper with the formula: sage: p(10,5) 3804 sage: p(9,8) 13715 sage: p(10,8) 21893 sage: p(4,1,1) 38 We can also use this to count the number of distinct factorizations of an integer. For example, we can write 12 as 12*1, 6*2, 4*3, or 3*2*2. sage: p(*[exponent for prime,exponent in factor(12)]) 4 I'll try to add native support for multiset partitions here into Sage in the near future. Hope that helps, --Mike --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
