|

Algebra

Hot goIITian

 Joined: 31 Aug 2007 Post: 117
20 Sep 2007 20:03:20 IST
0 People liked this
1
403
group formation in pnc
Engineering Entrance , JEE Main , JEE Advanced , Mathematics , Algebra

In how many ways can we distribute  on n things in 3 groups such that one gets p obj, one gets q & other also gets q obj
given that p + 2q=n.please explain this concept clearly

Forum Expert
Joined: 9 Mar 2007
Posts: 259
4 Nov 2007 16:36:20 IST
0 people liked this

The number of ways to divide n things as p + q +q = n is same as ?Total number of solutions of the linear equation p + 2q = n?. Where p and q are non-negative integers.

For example let?s take a simple situation. Divide 5 in two groups that one get x and second get y elements. Then we have x+y=5.
(i) Solution from the set of non-negative integers.

 Var 1 2 3 4 5 6 X 0 1 2 3 4 5 Y 5 4 3 2 1 0

Hence we have total 6 ways to divide 5 in two groups. Which is equal to dividing n (here 5) items in r (here 2) groups:
n+r-1Cr-1 =5+2-1C2-1 = 6C1 = 6
[n+r-1Cr-1  is equal to Coefficient of xn in (1-x)-r
Proof :   Any group can get (x0+x1+x2+x3+??..+xn) items, but we have r groups so the required number of ways is the coefficient of xn in the product of (x0+x1+x2+x3+??..+xn). (x0+x1+x2+x3+??..+xn)??.. (x0+x1+x2+x3+??..+xn)r times
= Coefficient of xn in (x0+x1+x2+x3+??..+xn)r
= Coefficient of xn in {(1-xn+1)/(1-x)}r
= Coefficient of xn in (1-xn+1)r(1-x)-r
= Coefficient of xn in (1-x)-r
= n+r-1Cr-1  ]
(ii) If we are restricted to take only natural numbers (zero is not acceptable) as solution set then the solutions are

 Var 1 2 3 4 X 1 2 3 4 Y 4 3 2 1

Hence we have total 4 ways to divide 5 in two groups. Which is equal to dividing n (here 5) items in r (here 2) groups:
n-1Cr-1 =5-1C2-1 = 4C1 = 4
[n-1Cr-1  is equal to Coefficient of xn-r in (1-x)-r
Proof: Same as above except that any group can get (x1+x2+x3+??..+xn) items now take x as common so
so the required number of ways is the coefficient of xn in the product of x.(1+x1+x2+x3+??..+xn). x.(1+x1+x2+x3+??..+xn)??.. x.(1+x1+x2+x3+??..+xn) r times
= Coefficient of xn in xr. (1+x1+x2+x3+??..+xn)r
= Coefficient of xn-r in {(1-xn)/(1-x)}r
= Coefficient of xn-r in (1-xn)r(1-x)-r
= Coefficient of xn-r in (1-x)-r = n-r+r-1Cr-1
= n-1Cr-1  ]

Same way we can deduct the most general solution for the linear equation like
px1+qx2+rx3+???=n with a restriction that ai<= xi <= bi; i=1,2,3?..r

= Coefficient of xn in [ {(xp)a1+(xp)a1+1+(xp)a1+2????+(xp)b1} . {(xq)a2+(xq)a2+1+(xq)a2+2????+(xq)b2} . {(xr)a3+(xr)a3+1+(xr)a3+2????+(xr)b3}???]

Now according to it the solution of the given equation p + 2q=n is
= Coefficient of xn in [(x0+x1+x2+x3+??..).( x0+x2+x4+x6+???)]
= Coefficient of xn in [(1-x)-1. ( 1+x2+x4+x6+???)]
= Coefficient of xn in [(1-x)-1+ x2. (1-x)-1+ x4. (1-x)-1???.]
= Coefficient of xn in (1-x)-1+ Coefficient of xn-2 in (1-x)-1+ Coefficient of xn-4 in (1-x)-1+ Coefficient of xn-6 in (1-x)-1+?????+ Coefficient of x0 in (1-x)-1
= n+1-1C1-1 + n-2+1-1C1-1 + n-4+1-1C1-1 + n-6+1-1C1-1 +???.+1
= nC0 + n-2C0+ n-4C0+ n-6C0+???..+1

For example let?s take a simple situation. Divide 6 in two groups that one get x and second get y elements such as x+2y=6.

 Var 1 2 3 4 X 0 2 4 6 Y 3 2 1 0

= 6C0 + 4C0+ 2C0+ 1
=1+1+1+1 = 4 ways

 Some HTML allowed. Keep your comments above the belt or risk having them deleted. Signup for a avatar to have your pictures show up by your comment If Members see a thread that violates the Posting Rules, bring it to the attention of the Moderator Team

For Quick Info

Name

Mobile

E-mail

City

Class

Vertical Limit

Top Contributors
All Time This Month Last Week
1. Bipin Dubey
 Altitude - 16545 m Post - 7958
2. Himanshu
 Altitude - 10925 m Post - 3836
3. Hari Shankar
 Altitude - 9960 m Post - 2185
4. edison
 Altitude - 10815 m Post - 7797
5. Sagar Saxena
 Altitude - 8625 m Post - 8064
 Altitude - 6330 m Post - 1979

Physics

Topics

Mathematics

Chemistry

Biology

Institutes

Parents Corner

Board

Fun Zone