Combinatorics problem

[Practicalpart]

We have 5 friends that came to visit us and 4 different types of juice in our home. In how many ways can we serve the juice to our friends if each friend gets one type of juice and each type of juice is used least once?

 

[Dr.Peterson]

What have you tried? Do you have any thoughts?

Suppose we call the types of juice A, B, C, and D. Then an example way to serve the juice might be ABCDD; a different way (assuming the friends are considered distinguishable) would be CDABD. Can you see a first step to count such ways? (Hint: first pick which kinds, then to whom.)

 

[pka]

We have 5 friends that came to visit us and 4 different types of juice in our home. In how many ways can we serve the juice to our friends if each friend gets one type of juice and each type of juice is used least once?

This may well be a pointless reply. But here goes: the answer to the question as posted is to count the number of surjections (onto functions) from a set of five to a set of four. That is \(\displaystyle \text{SURJ}(m,n)=\sum\limits_{k = 0}^m {{{( - 1)}^k} \dbinom{m}{k}{{(m - k)}^n}}\) [from a set of m to a set of n] Clearly \(\displaystyle m\ge n\). Here is the calculation in this question.

 

[Dr.Peterson]

My suggestion is a little simpler than that. Since exactly one type has to be repeated, the answer is just the number of ways to choose that one, times the number of ways to arrange ABCDD. (We have no idea yet what the OP knows, so either of these, or something else entirely, may be what is expected.)

 

[pka]

My suggestion is a little simpler than that. Since exactly one type has to be repeated, the answer is just the number of ways to choose that one, times the number of ways to arrange ABCDD. (We have no idea yet what the OP knows, so either of these, or something else entirely, may be what is expected.)

Simplicity has never been my game. If we had twenty-five guests and fifteen different types of beverages. We want to know how many ways can we give each guest exactly one type of drink and each type of beverage is given at least once.

 

[Practicalpart]

Well I thought of a serving as setting all the prepared glasses on the table and for it to not matter which friend we serve first. So I considered it like: 4*3*2*1*4 since the last glass can be whatever(or whichever glass doesnt really matter) and we have to use all the drinks, but this was wrong, so I considered also multiplying that with 5!(factorial) to consider the different serving orders to people, though I dont know if that is the correct way to do it and I don't know the correct answer since this was on an exam and all I know is that first attempt was wrong.
Thank you for your replies.

 

[Dr.Peterson]

As I interpret it, it doesn't matter whom we serve first, but it does matter who gets what.

Your approach appears to be choosing a juice for the first person, then a different juice for the second, and so on; but that assumes that the first four people have to get different juices, which is not required; you undercount. If you then multiply by 5! to rearrange them, you will be overcounting, as a rearrangement of one way may be obtainable starting with a different way already counted.

My suggestion was to first choose which one juice will be given to more than one person, and then to use the well-known way to count arrangements of letters with repetition, like ABCDD. Are you familiar with the latter problem?

Another approach would be to start with the juices rather than with the people as you did. Choose a person to get juice A, then a different person to get juice B, and so on until each juice has been served to someone; then choose which juice the leftover person gets. But then you will have double-counted, because that last person served might instead have been given that juice on the first pass. So you'd divide by 2. This kind of thinking is part of the derivation of the formula for words made from ABCDD.

Give it another try, and then I'll either approve, or correct, or show you on of my methods done fully.

Now, I'm guessing that pka's method is more advanced than what you have learned; can you tell us a little about where you are in learning combinatorics? We ask you to do that here, and it really helps these interactions to work better.

 

[Practicalpart]

I've now considered that the correct way to calculate the drink thing would be to use the inclusion and exclusion principle. So 4^5 -(4*3^5 - 6*2^5 + 4)

 

[Practicalpart]

I posted that previous post before seeing yours(page hasnt refreshed or something). I missed that part and I'm in 1st year of a math university but I'm really out of practice when it comes to combinatorics and it was never my strong side. We've done things like that. But it appears that what he posted gives the same result as the thing i posted last. Thank you all for your time.
Edit 1: the formula SURJ(m,n) that he wrote was processing in my head while i was listening to music and it occurred to me that its basically the inclusion/exclusion thing

 

[Dr.Peterson]

Great! So you do have a variety of tools at your disposal, if somewhat rusty.

Just to finish my approach, there are 4 ways to choose which juice is repeated, and then 5!/2! = 60 ways to arrange 5 items with 2 the same, for a total of 4*60 = 240. Which is, indeed, the same as you get by inclusion-exclusion. Good work.

One of the best things about combinatorics is that you can often do the same thing several very different ways, which helps confirm an answer.