• Support PF! Buy your school textbooks, materials and every day products Here!

Is there an efficient way to think of this combinatorial problem?

  • Thread starter jdinatale
  • Start date
  • #1
155
0

Homework Statement


prob-1.png


Part (a). If the cards are distinct, I see an astronomical number of cases possible.

Case 1. All 28 cards in one envelope. There are 9 envelopes. So 9 ways.

Case 2. 27 of the 28 cards in one envelope. There are (28 choose 27) ways of selecting the 27 cards for one envelope. There are 9 envelopes possible. So (28 choose 27)*9. But then there's the one extra card to place in one of the eight other envelopes. There are 8 remaining envelopes. So in case 2, we have (28 choose 27)*9*8 ways.

Case 3 gets REALLY complicated because you can have 26 cards in one envelope and 2 in a second envelope or 26 cards in one envelope, 1 in a second envelope, and 1 in a third envelope.

So...(28 choose 26)*8 + (28 choose 26)*(2 choose 1)*(1 choose 1)*8*7


See why I'm wondering if there's a more efficient way to do this?
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,535
751
Pick card 1. How many ways can you choose an envelope for it?
After that is done, how many ways can you choose an envelope for card 2?
etc...
 
  • #3
Bacle2
Science Advisor
1,089
10
For the case (a) , I think this is your standard balls-in-boxes type of problem:

The number of solutions to x1+x2+...+xn=k is :

(n+k-1)C(k-1) if you allow for empty enveloppes (" n-1 choose k-1 ")

or (n-1)C(k-1).
 
  • #4
296
0
You are right about the astronomical number of cases possible. However, just because it is astronomical doesn't mean you can't evaluate it.

There is no limit on how many cards you can put in an envelope, so think this way: How many envelopes can you put the first card in? The second? The third? Then, you can use the general multiplication rule to multiply all those numbers to end up with the solution.
 
  • #5
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728

Homework Statement


prob-1.png


Part (a). If the cards are distinct, I see an astronomical number of cases possible.

Case 1. All 28 cards in one envelope. There are 9 envelopes. So 9 ways.

Case 2. 27 of the 28 cards in one envelope. There are (28 choose 27) ways of selecting the 27 cards for one envelope. There are 9 envelopes possible. So (28 choose 27)*9. But then there's the one extra card to place in one of the eight other envelopes. There are 8 remaining envelopes. So in case 2, we have (28 choose 27)*9*8 ways.

Case 3 gets REALLY complicated because you can have 26 cards in one envelope and 2 in a second envelope or 26 cards in one envelope, 1 in a second envelope, and 1 in a third envelope.

So...(28 choose 26)*8 + (28 choose 26)*(2 choose 1)*(1 choose 1)*8*7


See why I'm wondering if there's a more efficient way to do this?
In part (a) you need to clarify what constitutes "different ways". For example, if envelope 1 contains cards 1, 2 and 3, do you count 123 (in that order) as different from 321, etc? (Perhaps you look at the cards from front to back or something similar, so you can tell the difference between 123 and 321.) If you do count them as different, then: the first card to be placed can be any of the 28, and it can go into any of the 9 envelopes. Then the second card to be placed can be any of the remaining 27, and it can go into any of the 9 envelopes, etc. On the other hand, if the order within an envelope does not matter, the number of ways is the same whether or not the cards are distinct or identical. (If you don't believe this, compute both answers.)

RGV
 

Related Threads on Is there an efficient way to think of this combinatorial problem?

Replies
2
Views
512
Replies
30
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
995
  • Last Post
Replies
4
Views
1K
Replies
5
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
Top