Home » Ask & Discuss » Mathematics
« Back to Discussion

Algebra

Hot goIITian

Joined:	31 Aug 2007
Post:	117

20 Sep 2007 20:03:20 IST

0 People liked this

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

Comments (1)

Avinash Sharma

Forum Expert

Joined: 9 Mar 2007

Posts: 259

4 Nov 2007 16:36:20 IST

Like 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-1C_r-1 =^5+2-1C_2-1 = ⁶C₁ = 6

[^n+r-1C_r-1 is equal to Coefficient of xⁿ in (1-x)^-r

Proof : Any group can get (x⁰+x¹+x²+x³+??..+xⁿ) items, but we have r groups so the required number of ways is the coefficient of xⁿ in the product of (x⁰+x¹+x²+x³+??..+xⁿ). (x⁰+x¹+x²+x³+??..+xⁿ)??.. (x⁰+x¹+x²+x³+??..+xⁿ)r times

= Coefficient of xⁿ in (x⁰+x¹+x²+x³+??..+xⁿ)^r

= Coefficient of xⁿ in {(1-xⁿ⁺¹)/(1-x)}^r

= Coefficient of xⁿ in (1-xⁿ⁺¹)^r(1-x)^-r

= Coefficient of xⁿ in (1-x)^-r

=^n+r-1C_r-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-1C_r-1 =^5-1C_2-1 = ⁴C₁ = 4

[^n-1C_r-1 is equal to Coefficient of x^n-r in (1-x)^-r

Proof: Same as above except that any group can get (x¹+x²+x³+??..+xⁿ) items now take x as common so

so the required number of ways is the coefficient of xⁿ in the product of x.(1+x¹+x²+x³+??..+xⁿ). x.(1+x¹+x²+x³+??..+xⁿ)??.. x.(1+x¹+x²+x³+??..+xⁿ) r times

= Coefficient of xⁿ in x^r. (1+x¹+x²+x³+??..+xⁿ)^r

= Coefficient of x^n-r in {(1-xⁿ)/(1-x)}^r

= Coefficient of x^n-r in (1-xⁿ)^r(1-x)^-r

= Coefficient of x^n-r in (1-x)^-r = ^n-r+r-1C_r-1

=^n-1C_r-1 ]

Same way we can deduct the most general solution for the linear equation like

px₁+qx₂+rx₃+???=n with a restriction that a_i<= x_i <= b_i; i=1,2,3?..r

= Coefficient of xⁿ in [ {(x^p)^a₁+(x^p)^a₁⁺¹₊(x^p)^a₁⁺²????+(x^p)^b₁} . {(x^q)^a₂+(x^q)^a₂⁺¹₊(x^q)^a₂⁺²????+(x^q)^b₂} . {(x^r)^a₃+(x^r)^a₃⁺¹₊(x^r)^a₃⁺²????+(x^r)^b₃}???]

Now according to it the solution of the given equation p + 2q=n is

= Coefficient of xⁿ in [(x⁰+x¹+x²+x³+??..).( x⁰+x²+x⁴+x⁶+???)]

= Coefficient of xⁿ in [(1-x)^-1. ( 1+x²+x⁴+x⁶+???)]

= Coefficient of xⁿ in [(1-x)^-1+ x². (1-x)^-1+ x⁴. (1-x)^-1???.]

= Coefficient of xⁿ in (1-x)^-1+ Coefficient of x^n-2 in (1-x)^-1+ Coefficient of x^n-4 in (1-x)^-1+ Coefficient of x^n-6 in (1-x)^-1+?????+ Coefficient of x⁰ in (1-x)^-1

= ^n+1-1C_1-1 + ^n-2+1-1C_1-1 +^n-4+1-1C_1-1 +^n-6+1-1C_1-1 +???.+1

= ⁿC₀^{+ n-2}C₀+^n-4C₀+^n-6C₀+???..+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

= ⁶C₀^{+ 4}C₀+²C₀+1

=1+1+1+1 = 4 ways

Quick Reply

Reply

	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