My Math Forum Counting Problem

 Number Theory Number Theory Math Forum

 June 5th, 2012, 06:20 PM #1 Member   Joined: May 2012 Posts: 86 Thanks: 0 Counting Problem Consider the equation x+y+z+w=n, where n is a positive integer greater or equal to 4. A positive and integer solution is a set (x,y,z,w) of positive integers that satisfies the equation for a given n. For example, for n=10 one solution to x+y+z+w=10 would be (1,2,3,4), since 1+2+3+4=10. a) Determine the number of positive and integer solutions for n=10. b) Find a general formula that counts the number of whole and integer solutions for x+y+z+w=n. Note: Solutions (2, 2, 2, 4), (2, 2, 4, 2),(2, 4, 2, 2) and (4, 2, 2, 2) for n=10 are each considered different and separate solutions.
 June 5th, 2012, 07:14 PM #2 Member   Joined: May 2012 From: Chennai,India Posts: 67 Thanks: 0 Re: Counting Problem so. its finding the no of partitions of n as 4 integers.. it can be split like partitions of n as sum of two numbers.. and finding the partitions of those 2 numbers as sum of two numbers...
 June 5th, 2012, 10:47 PM #3 Member   Joined: May 2012 From: Chennai,India Posts: 67 Thanks: 0 Re: Counting Problem this can be proved by multinomial theorem... For a+b+c+d = n, the no. of solutions including 0 is $(n+1)(n+2)(n+3)/6$ need to eliminate those terms in the expansion of $(a+b+c+d)^n$ that have powers of all a,b,c,d
June 6th, 2012, 03:14 AM   #4
Math Team

Joined: Apr 2012

Posts: 1,579
Thanks: 22

Re: Counting Problem

Quote:
 Originally Posted by karthikeyan.jp this can be proved by multinomial theorem... For a+b+c+d = n, the no. of solutions including 0 is $(n+1)(n+2)(n+3)/6$ need to eliminate those terms in the expansion of $(a+b+c+d)^n$ that have powers of all a,b,c,d
What's the reasoning behind that formula?

 June 6th, 2012, 05:10 AM #5 Member   Joined: May 2012 From: Chennai,India Posts: 67 Thanks: 0 Re: Counting Problem The number of co-efficients in the expansion of $(x1+x2+x3...+xm)^n$ is (n+m-1 n). http://en.wikipedia.org/wiki/Multinomial_theorem So for $(a+b+c+d)^n$, it is (n+3 n) ==> $(n+3)!/n! x 3!$
June 6th, 2012, 05:40 AM   #6
Member

Joined: May 2012

Posts: 86
Thanks: 0

Re: Counting Problem

Quote:
 Originally Posted by karthikeyan.jp this can be proved by multinomial theorem... For a+b+c+d = n, the no. of solutions including 0 is $(n+1)(n+2)(n+3)/6$
Well, using this formula, I found through trial and error that the general formula for my problem happens to be:
((n-3)(n-2)(n-1))/6

I'm completely clueless as to the reasoning behind it, though, and politely ask for a baby explanation lol.

June 7th, 2012, 03:32 PM   #7
Math Team

Joined: Dec 2006
From: Lexington, MA

Posts: 3,267
Thanks: 408

Re: Counting Problem

Hello, Jakarta!

Quote:
 Consider the equation $x\,+\,y\,+\,z\,+\,w\:=\:n$, where $n$ is a positive integer $\ge\,4.$ A solution is a set $(x,\,y,\,z,\,w)$ of positive integers that satisfies the equation for a given $n.$ a) Determine the number of solutions for $n=10.$

Place 10 objects in a row, inserting a space between them.
[color=beige]. . [/color]$\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ \,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\, \circ\,\_\,\circ$

Select 3 of the 9 spaces and insert "dividers".

$\text{So that: }\:\circ\,\_\,\circ\,|\,\circ\,|\,\circ \,\_\,\circ\,\_\,\circ\,|\,\circ\,\_\,\circ\,\_\,\ circ\,\_\,\circ\:\text{ represents }\:2\,+\,1\,+\,3\,+\,4$

$\;\;\;\;\text{and: }\:\circ\,\_\,\circ\,\_\,\circ\,|\,\circ \,|\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\ circ\,|\,\circ\:\text{ represents }\:3\,+\,1\,+\,5\,+\,1$

$\text{Therefore, there are: }\:{9\choose3} \:=\:84\text{ solutions.}$

Quote:
 b) Find a general formula that counts the number of solutions for $x\,+\,y\,+\,z\,+\,w\:=\:n$ Note: Solutions (2, 2, 2, 4), (2, 2, 4, 2), (2, 4, 2, 2) and (4, 2, 2, 2) for $n=10$ [color=beige]. . . . . [/color]are each considered different and separate solutions.

Following the solution in part (a), place $n$ objects in a row (with spaces).

Select 3 of the $n-1$ spaces and insert "dividers".

$\text{Therefore, there are: }\:{n-1\choose3}\text{ solutions.}$

June 7th, 2012, 09:05 PM   #8
Member

Joined: May 2012

Posts: 86
Thanks: 0

Re: Counting Problem

Quote:
Originally Posted by soroban
Hello, Jakarta!

Quote:
 Consider the equation $x\,+\,y\,+\,z\,+\,w\:=\:n$, where $n$ is a positive integer $\ge\,4.$ A solution is a set $(x,\,y,\,z,\,w)$ of positive integers that satisfies the equation for a given $n.$ a) Determine the number of solutions for $n=10.$

Place 10 objects in a row, inserting a space between them.
[color=beige]. . [/color]$\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ \,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\, \circ\,\_\,\circ$

Select 3 of the 9 spaces and insert "dividers".

$\text{So that: }\:\circ\,\_\,\circ\,|\,\circ\,|\,\circ \,\_\,\circ\,\_\,\circ\,|\,\circ\,\_\,\circ\,\_\,\ circ\,\_\,\circ\:\text{ represents }\:2\,+\,1\,+\,3\,+\,4$

$\;\;\;\;\text{and: }\:\circ\,\_\,\circ\,\_\,\circ\,|\,\circ \,|\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\circ\,\_\,\ circ\,|\,\circ\:\text{ represents }\:3\,+\,1\,+\,5\,+\,1$

$\text{Therefore, there are: }\:{9\choose3} \:=\:84\text{ solutions.}$

[quote:3oncju6n]b) Find a general formula that counts the number of solutions for $x\,+\,y\,+\,z\,+\,w\:=\:n$

Note: Solutions (2, 2, 2, 4), (2, 2, 4, 2), (2, 4, 2, 2) and (4, 2, 2, 2) for $n=10$
[color=beige]. . . . . [/color]are each considered different and separate solutions.

Following the solution in part (a), place $n$ objects in a row (with spaces).

Select 3 of the $n-1$ spaces and insert "dividers".

$\text{Therefore, there are: }\:{n-1\choose3}\text{ solutions.}$

[/quote:3oncju6n]
Wow, that is extremely smart and clear. Thanks!

 Tags counting, problem

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post superconduct Algebra 2 January 7th, 2014 10:01 AM zelmac Algebra 0 February 14th, 2013 05:29 AM scream Applied Math 2 February 21st, 2012 11:50 AM kec11494 Applied Math 1 December 20th, 2010 08:44 PM julian21 Applied Math 0 April 27th, 2010 09:48 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top