Results 1 to 5 of 5

Math Help - Clarification of counting problem

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    15

    Clarification of counting problem

    Number of ways to write 10 as a sum of 4 non negative numbers.

    I get why this is 13 choose 3. But then the question also asks what happens when every number has to be atleast one, the answer is 9 choose 3. Do you just subtract the 4 zeros that are not going to be used or what?

    Thanks for the help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,963
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by smellatron View Post
    Number of ways to write 10 as a sum of 4 non negative numbers. I get why this is 13 choose 3. But then the question also asks what happens when every number has to be atleast one, the answer is 9 choose 3. Do you just subtract the 4 zeros that are not going to be used or what?
    The first question is \binom{10+4-1}{10}, the number of ways putting ten identical objects (in this case 1’s) into four different cells (in this case variables).
    \binom{N+k-1}{N} is the number of ways putting N identical objects into k different cells.

    But in both of these cases some cells could be empty.
    If we want no cell to be empty, we play a mind game.
    Go ahead and put a 1 into each variable leaving 6 to distribute into the 4 variables.
    This gives \binom{6+4-1}{6}.

    For the general case:
    \binom{N-1}{N-k} is the number of ways putting N identical objects into k different cells with no cell empty.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Placing objects into cells

    Hello smellatron
    Quote Originally Posted by smellatron View Post
    Number of ways to write 10 as a sum of 4 non negative numbers.

    I get why this is 13 choose 3. But then the question also asks what happens when every number has to be atleast one, the answer is 9 choose 3. Do you just subtract the 4 zeros that are not going to be used or what?

    Thanks for the help.
    Sorry to be fussy, but I'm not sure about this. I think you and Plato are answering a slightly different question, which is: How many solutions are there to the equation a_1+a_2+a_3+a_4 = 10, where the a_i \in \mathbb{N}_0 (including zero)? And, secondly, where the a_i \in \mathbb{N} (excluding zero).

    If this is what you meant, then that's fine. But the difficulty with the problem as you stated it is, of course, is that there is only one solution that uses, for example, the numbers 10,0,0,0. However, the question as I have stated it above (and which, I believe, you have both answered) has four distinct solutions; (10,0,0,0),(0,10,0,0), (0,0,10,0),(0,0,0,10).

    Indeed, in Plato's solution, he mentions 'different cells', whereas in the question as you stated it the 'cells' are, I think, all identical, as well as the objects that are to be placed in them.

    As far as your saying that you understand where \binom{13}{3} comes from, I can't say that I think it's at all obvious, and would be interested to hear why you think it is. I think it's probably easier to understand the second case where the numbers have to be non-zero.

    My reasoning for this is as follows:

    If each number has to be non-zero, imagine 10 1's in a line. There are therefore 9 gaps separating each number 1 from its neighbour. Then we have to choose 3 of these gaps into which to place a barrier, thus dividing the 1's into 4 groups. This can be done in \binom{9}{3} ways.

    To answer the first question (where zeros are allowed), the only method that I know is to imagine 14 1's with, therefore, 13 gaps from which 3 must again be chosen. This can be done in \binom{13}{3} ways. In each group thus formed, there is a non-zero number of 1's. We then simply discard one 1 from each of the four groups, leaving 10 1's as required.

    Is there an easier way of looking at this that I am overlooking?

    Grandad
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2009
    Posts
    15
    That description does make alot of sense. The 14 dots was how the teacher showed it to us. Thanks again for the help.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,963
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by Grandad View Post
    I think you and Plato are answering a slightly different question, which is: How many solutions are there to the equation a_1+a_2+a_3+a_4 = 10, where the a_i \in \mathbb{N}_0 (including zero)? And, secondly, where the a_i \in \mathbb{N} (excluding zero).
    I believe, you have both answered has four distinct solutions; (10,0,0,0),(0,10,0,0), (0,0,10,0),(0,0,0,10).
    Grandad, when I first read this question, the interpretation I made was exactly what you wrote.
    However, the numbers in OP made no sense under that meaning.
    Your reading involves the partition of an integer. How many ways can 10 be represented in by four or fewer summands (the ‘fewer’ is the zero case): P(10;4)=23.
    Here are some of those 23: 10=10, 10=9+1, 10=1+2+3+4.
    But the number 23 makes no sense of the proposed \binom{13}{3}.
    Whereas, the other reading is exactly that.

    The nonzero case is “How many ways can 10 be represented in by exactly four summands?”: P(10;4)-P(10;3)=9.

    There reason that I doubt that the question refers to partitions of an integer is due to the difficulty in calculating P(N;k).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need clarification on this problem
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 28th 2012, 08:45 PM
  2. Clarification on a problem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 12th 2010, 09:13 PM
  3. Clarification for a' counting' problem.
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 5th 2010, 04:24 PM
  4. Word problem clarification
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 10th 2009, 10:14 AM
  5. Replies: 3
    Last Post: April 13th 2009, 06:42 PM

Search Tags


/mathhelpforum @mathhelpforum