Combination/Permutation Problem

  • Thread starter Seda
  • Start date
  • #1
Seda
71
0

Homework Statement



What is the number of distinguishable fruit baskets, each with seven fruit, can you make with apples, oranges, and bananas.

Homework Equations



Knowledge of Combinations/Permutations

The Attempt at a Solution



Well, to me, this is weird because this is essentially a problem where there is replacement. And obviously, I need to look at combinations, not permutations, because I need distinct baskets.

However, I know the general formula for combination when it's read "n choose k"
, but the way this question is worded, it seems k is bigger than n.

Can I just get some help on how to think about this in terms of combination with replacement or something? Help is appreciated.
 

Answers and Replies

  • #2
Seda
71
0
Okay, I've learned that this is a combination with repetition, which the formula is C (n+k-1; k)



but can anyone here tell me how that formula is derived? I've look at it for 30 minutes and I am clueless.
 
  • #3
Dick
Science Advisor
Homework Helper
26,263
621
Uh, don't double post, ok?
 
  • #4
montoyas7940
363
21
:uhh:
 
Last edited:
  • #5
HallsofIvy
Science Advisor
Homework Helper
43,021
970
You are to make a basket containing 7 fruit from apples, oranges, and bananas.

You can choose to put in a basket, 0, 1, 2, 3, 4, 5, 6, or 7 apples: 8 choices.

If you chose to put 0 apples in you could choose
0, 1, 2, 3, 4, 5, 6, or 7 oranges. For each of those, the number of bananas is now fixed.

If you chose to put 1 apple in you could choose
0, 1, 2, 3, 4, 5, or 6 oranges. And now the number of bananas is fixed.

If you chose to put in 2 apples you could choose
0, 1, 2, 3, 4, or 5 oranges. And now the number of bananas is fixed.

Do you see the pattern? How many total choices do you have?
 
  • #6
Tedjn
737
0
In any case, I don't think the formula is C(n+k-1, k). Perhaps it is C(n+k-1, k-1)? The general idea behind this is an alternative way of looking at the problem. Suppose apples are represented by A, bananas by B, oranges by O. Then, let apples always come before bananas always come before oranges, so a basket of 3 apples, 1 banana, and 3 oranges would be the string AAABOOO. Now, an empty basket would be just seven blank spaces waiting for letters to be put in, so: _ _ _ _ _ _ _

To this string of seven letters, we add two separators. Thus, we have _ _ _ _ _ _ _ | |

If we put these nine symbols in any distinguishable order, we will have a distinct fruit basket, if we keep in mind that anything to the left of the first separator is an apple, anything in between the two is a banana, and anything after the second separator is an orange.

For example, the arrangement for 3 apples, 1 banana, and 3 oranges is now: _ _ _ | _ | _ _ _

Basically, we have 9 places (this is n+(k-1)) where k-1 is the number of separators. From that, we choose 2 places (this is k-1) for the separators, and order doesn't matter. Thus, there should be C(n+k-1, k-1) arrangements.

Hopefully, that's right.
 

Suggested for: Combination/Permutation Problem

  • Last Post
Replies
1
Views
166
Replies
1
Views
210
Replies
7
Views
442
Replies
1
Views
218
Replies
20
Views
2K
  • Last Post
Replies
22
Views
1K
Replies
20
Views
750
  • Last Post
Replies
5
Views
435
Replies
8
Views
926
Replies
14
Views
773
Top