i'm trying to find the number of non negative integral solutions of the equation a + 2b + 3c + 4d = n ,i find it is equation to the partition of n into at most 4 parts. Wikipedia says this is the definition of partition .
Can some one help me understand why is the number of non integral solutions to the above equation is equal to number of partions atmost 4 of n.
i could write the above equation as
(a+b+c+d) + (b+c+d) + (c+d) + d = n , if we replace a+b+c+d as x1, b+c +d as x2 , c+d as x3 then we have x1 +x2 +x3 + d = n which is number of partitions of n into 4 parts exactly but with below constraints. 0<=d<=n/4 , 0<=c<=n/4 , 0<=b<=n/2 , 0<=a<=n, if there weren't this constraint i could directly substitute x1,x2,x3, x4 and then say it is 4 parts exactly.
now again we can write a+2b +3c=n if d=0, then we have number of solutions of n into 3 parts, if c ,d=0, n into 2 parts, b=c=d=0, then n into 1 part,
I'm stuck here . how do i proceed . This looks easy but i'm unable to find the insight.
> i'm trying to find the number of non negative integral solutions of > the equation a + 2b + 3c + 4d = n ,i find it is equation to the > partition of n into at most 4 parts. Wikipedia says this is the > definition of partition .
> Can some one help me understand why is the number of non integral > solutions to the above equation is equal to number of partions atmost > 4 of n.
> > i'm trying to find the number of non negative integral solutions of > > the equation a + 2b + 3c + 4d = n ,i find it is equation to the > > partition of n into at most 4 parts. Wikipedia says this is the > > definition of partition .
> > Can some one help me understand why is the number of non integral > > solutions to the above equation is equal to number of partions atmost > > 4 of n.
> Conjugation.
To be a little less telegraphic: Victor refers to the fact that counting partitions of n with parts not bigger than 4 is the same thing as counting partitions of n with at most four parts, because each partition in the first set corresponds to one in the second set under the operation of `conjugating' their Ferrer's diagram. See <http://mathworld.wolfram.com/ ConjugatePartition.html>,
> > > i'm trying to find the number of non negative integral solutions of > > > the equation a + 2b + 3c + 4d = n ,i find it is equation to the > > > partition of n into at most 4 parts. Wikipedia says this is the > > > definition of partition .
> > > Can some one help me understand why is the number of non integral > > > solutions to the above equation is equal to number of partions atmost > > > 4 of n.
> > Conjugation.
> To be a little less telegraphic: Victor refers to the > fact that counting partitions of n with parts not > bigger than 4 is the same thing as counting partitions > of n with at most four parts, because each partition > in the first set corresponds to one in the second set > under the operation of `conjugating' their > Ferrer's diagram. See <http://mathworld.wolfram.com/ > ConjugatePartition.html>,
> -- m
I have 2 questions,first is to related to the postings, 2nd is a new one.
For eqn a + 2b + 3c + 4d =n , we are actually dividing into 10 parts ie a,b,b,c,c,c,d,d,d, with some parts being equal and 0<=a<=n , 0<=b<=n/2 , etc
how does the eqn transform into "counting partitions of n with parts not bigger than 4" ? for the equation n=28, i could find a solution (a,b,c,d)=(0,0,0,7) it has part bigger than 4. What is the reasoning behind this transformation ?
We could replace 2b by y2 , 3c by y3 and 4d by y4 but y2 now takes only multiples of 2 , y3 only multiples of 3 and y4 only multiples of 4 to get a + y2+y3+y4=n. This is where i'm little stuck up.
2) For the non negative integral equation , a +b + c+ d=n the number of solutions is C(n+r-1,r), but how do we apply it to a + 2b + 3c + 4d = n, they are having multiples . We can trasform it by a + (y2 -y3) + 3c + 4d = n , where 0<=y2<=n but 0<=y3<=n/2 but again y2-y3 takes odd values but in the oginal equation it takes only even values , similarly for other variables.
> > > > i'm trying to find the number of non negative integral solutions of > > > > the equation a + 2b + 3c + 4d = n ,i find it is equation to the > > > > partition of n into at most 4 parts. Wikipedia says this is the > > > > definition of partition .
> > > > Can some one help me understand why is the number of non integral > > > > solutions to the above equation is equal to number of partions atmost > > > > 4 of n.
> > > Conjugation.
> > To be a little less telegraphic: Victor refers to the > > fact that counting partitions of n with parts not > > bigger than 4 is the same thing as counting partitions > > of n with at most four parts, because each partition > > in the first set corresponds to one in the second set > > under the operation of `conjugating' their > > Ferrer's diagram. See <http://mathworld.wolfram.com/ > > ConjugatePartition.html>,
> > -- m
> I have 2 questions,first is to related to the postings, 2nd is a new > one.
> For eqn a + 2b + 3c + 4d =n , we are actually dividing into 10 parts > ie a,b,b,c,c,c,d,d,d, with some parts being equal and 0<=a<=n , > 0<=b<=n/2 , etc
> how does the eqn transform into "counting partitions of n with parts > not bigger than 4" ? for the equation n=28, i could find a solution > (a,b,c,d)=(0,0,0,7) it has part bigger than 4. What is the reasoning > behind this transformation ?
Ferrer's diagram can be transposed as xxxxxxx xxxxxxx xxxxxxx xxxxxxx into xxxx xxxx xxxx xxxx xxxx xxxx xxxx, and otherwise. kunzmilan
> I have 2 questions,first is to related to the postings, 2nd is a new > one.
> For eqn a + 2b + 3c + 4d =n , we are actually dividing into 10 parts > ie a,b,b,c,c,c,d,d,d, with some parts being equal and 0<=a<=n , > 0<=b<=n/2 , etc
> how does the eqn transform into "counting partitions of n with parts > not bigger than 4" ? for the equation n=28, i could find a solution > (a,b,c,d)=(0,0,0,7) it has part bigger than 4. What is the reasoning > behind this transformation ?
You were not dividing into ten parts.
Let's try an example which may be easier, with n=28 and solution (1,5,3,2), i.e. 28 = 1*1 + 2*5 + 3*3 + 4*2
You can see this a a partition into parts no greater than four, i.e. 28 = 1 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3 + 4 + 4 and draw this as two columns of 4, three columns of 3, five columns of 2, one column of 1
*********** ********** ***** **
Now reflect this in the diagonal to give
**** **** *** *** *** ** ** ** ** ** *
which can be taken to represent 28 = 2 + 5 + 10 + 11.
Note from the original (1,5,3,2) we have 2=2, 3+2=5, 5+3+2=10 and 1+5+3+2=11
The first parition was constrained to have no parts greater than than 4, i.e. no more than four columns, which when reflected became no more than four rows or equivalently no more than 4 parts.
You can do this with any similarly constrained partition and so the number of partitions of n which have no parts greater than than k is equal to the number of partitions of n which have no more than k parts.
> > I have 2 questions,first is to related to the postings, 2nd is a new > > one.
> > For eqn a + 2b + 3c + 4d =n , we are actually dividing into 10 parts > > ie a,b,b,c,c,c,d,d,d, with some parts being equal and 0<=a<=n , > > 0<=b<=n/2 , etc
> > how does the eqn transform into "counting partitions of n with parts > > not bigger than 4" ? for the equation n=28, i could find a solution > > (a,b,c,d)=(0,0,0,7) it has part bigger than 4. What is the reasoning > > behind this transformation ?
> You were not dividing into ten parts.
> Let's try an example which may be easier, with n=28 and solution > (1,5,3,2), > i.e. 28 = 1*1 + 2*5 + 3*3 + 4*2
> You can see this a a partition into parts no greater than four, i.e. > 28 = 1 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3 + 4 + 4 and draw this as two
the above line was what i was looking for . pretty stupid of me.
> which can be taken to represent 28 = 2 + 5 + 10 + 11.
> Note from the original (1,5,3,2) we have 2=2, 3+2=5, 5+3+2=10 and > 1+5+3+2=11
> The first parition was constrained to have no parts greater than than > 4, i.e. no more than four columns, which when reflected became no more > than four rows or equivalently no more than 4 parts.
> You can do this with any similarly constrained partition and so the > number of partitions of n which have no parts greater than than k is > equal to the number of partitions of n which have no more than k > parts.
crystal clear thanks,
Any thoughts on the combinatorial ways for the same question lets take a+2b+3c +4d = n , with a,b,c,d non-negative integers , i have a feeling that it can be done using inclusion exclusion principle. If not for 4 variables how about for 3 , a+2b+3c=n , can we do some transformations so that it ends up like y1 + y2 + y3 = z and the number of solutions of that can be found out using the principles for y1+y2+....yn=r as C(n+r-1,r) .
a + (y2 -y3) + 3c = n , where 0<=y2<=n but 0<=y3<=n/2 but again y2- y3 takes odd values but in the original equation it takes only even values , this is what stops me from proceeding further.
> Any thoughts on the combinatorial ways for the same question > lets take a+2b+3c +4d = n , with a,b,c,d non-negative integers , i > have a feeling that it can be done using inclusion exclusion > principle. If not for 4 variables how about for 3 , a+2b+3c=n , can we > do some transformations so that it ends up like y1 + y2 + y3 = z and > the number of solutions of that can be found out using the principles > for y1+y2+....yn=r as C(n+r-1,r) .
> a + (y2 -y3) + 3c = n , where 0<=y2<=n but 0<=y3<=n/2 but again y2- > y3 takes odd values but in the original equation it takes only even > values , this is what stops me from proceeding further.
