T Nation

Help with Math Problem

The problem is this:

In how many ways can N identical balls be placed in three boxes, so in first there are N1(1 is index), in the second N2 and in the third N3 so that

N1 + N2 + N3 < N

pÉ?Ç?É¥ Ê?ɯ oÊ? Æ?uıuunɹ sı poolq Ê?ɯ É?o llÉ?

If you mean N^1 + N^2 + N^3 < N

I’m pretty sure that’s unpossible (assuming N > 0, as it’s a physical number of balls, and os N^2 + N^3 > 0, so N^1 + (>0) is not < N^1)

If I’m misreading or mis-interpreting, please elaborate.

[quote]danchubb wrote:
If you mean N^1 + N^2 + N^3 < N

I’m pretty sure that’s unpossible (assuming N > 0, as it’s a physical number of balls, and os N^2 + N^3 > 0, so N^1 + (>0) is not < N^1)

If I’m misreading or mis-interpreting, please elaborate.[/quote]

No no, N1, N2 and N3 are just the names of the boxes I think

Wouldn’t it be something like

50! / (50 - 3)! => 50! / 47! ~ 117.5k ways?

You’re talking about permutations right? So you could have 50 balls and you can use 1 ball or 49 balls? So it’s probably not exactly as above and may be 49! / 47!

That’s my best guess anyway.

[quote]matko5 wrote:
The problem is this:

In how many ways can N identical balls be placed in three boxes, so in first there are N1(1 is index), in the second N2 and in the third N3 so that

N1 + N2 + N3 < N[/quote]

Is that a strictly less than or less than or equal to?

I need some clarification, so there’s 3 boxes and you have n balls, and the question is how many different ways are there to put different numbers of balls in each box so that the total number of balls in all boxes = n? So for instance you have x balls in the first box, y balls in the 2nd and z balls in the 3rd such that x+y+z=n?

Stricky less.

[quote]JLu wrote:
I need some clarification, so there’s 3 boxes and you have n balls, and the question is how many different ways are there to put different numbers of balls in each box so that the total number of balls in all boxes = n? So for instance you have x balls in the first box, y balls in the 2nd and z balls in the 3rd such that x+y+z=n?[/quote]

Yes, it should be like that but it says x+y+z < N

9

[quote]B rocK wrote:
9[/quote]

x2

so 18

I’m not sure how to handle the case where it’s strictly less than, but this sounds like a “ball and stick” problem. Picture all the balls lined up side by side, and you have 2 sticks with which to partition the balls into 3 groups. With n balls lined up, there are n+1 slots in total, and you have to think about the number of possible 2 stick combinations there are ie if n=5 you can have OOOOOII or OOIOOIO for instance.

Based on my understanding of the problem, here is how I see it:

For N=1, there is only 1 way to arrange the balls such that N1+N2+N3 < N and that is to put no balls in the boxe.

For N=2, there are 3 ways: one ball has to be left out and the other one can be put in any 3 of the boxes.

For N=3, there are 3 + 33 ways. You can leave two balls out and put the remaining ball in any of the 3 boxes or you can leave one ball out and put the other two in the boxes 33 ways. However, since all of the balls are identical, there are really only 6 ways to order 2 balls in 3 boxes: 2 in any of the three boxes or 1-2, 1-3, or 2-3. I believe this case assumes that ball A in box 1 and ball B in box = ball A in box 2 and ball B in box 1. So for N=3, there are really only 3 + 6 ways.

For N=4, you take the 3 + 6 from above and now consider how many ways that 3 balls can be ordered amongst 3 boxes. 3-0-0 plus 0-3-0 plus 0-0-3 plus 2-1-0 plus 2-0-1 plus 1-2-0 plus 0-2-1 plus 0-1-2 plus 1-0-2 plus 1-1-1. So for N=4, there are 3 + 6 + 10 ways.

For N=5, you take the 3 + 6 + 10 from above and now consider how many ways that 4 balls can be ordered amongst 3 boxes. 4-0-0, 0-4-0, 0-0-4, 3-1-0, 3-0-1, 0-3-1, 1-3-0, 0-1-3, 1-0-3, 2-2-0, 2-0-2, 0-2-2, 2-1-1, 1-2-1, 1-1-2. So for N=5, there are 3 + 6 + 10 + 15 ways.

So now we see a sequence emerging. The (n-1)th term of the sequence is given by: ((3-1) + (N-1)) C (N-1). or simply (N+1)c(N-1) Ex, for N=4, 5c3 = 10. For N=5, 6c4 = 15.

So the answer is sum(n=1:N) of [ (N+1)c(N-1) ]

That covers the more difficult case where you don’t have to use all of the balls. Ie, if N=6, you can put 1 ball in N1 and 1 in N2 and be done with it. If you are required to use N-1 balls, then the answer is just (N+1)c(N-1).

I think. Somebody feel free to double-check as I often make stupid errors in problems like this.

I just don’t know how to solve that. There is also this problem:

How many words can you make from letters in the word “banana”?
That’s puzzling beauce what is considered a word? Do I just permute possible solutions with b, a and n up to 6 letters or what?

I can solve the question how many combinations can there be in the 7/39 lottery? (15 mill +, it’s just combinations without repeating), A team that has 3 wins, 3 loses and 2 draws and how many possible ways to achieve those stats (that’s permutations with repeating, right?) and how many numbers are below 10^8 that have 5 7’ (I’m figuring out how to solve that, but I know the idea)

[quote]matko5 wrote:
I just don’t know how to solve that.[/quote]

Don’t know how to solve what?