Combinatorial Problems: Inviting Friends and Seating Arrangements

[twoflower]

Hi all,

I have two problems, probably easy, but I can't get it solved or at least find a solution based on some bulletproof idea :)

Problem 1
A host makes a party for his friends every day. To the party three guests are always invited. How many ways can the host invite his 7 friends, so that all the friends will be invited within a week?

Problem 2
Let's have n = 3k people and k tables, each for three people. How many times is it necessary to seat the people to the tables, so that each one pair will meet at exactly one seating? Can it be done for even number of tables? (Find general expression for tables with s places and t people who should meet exactly once.

To the first problem, I only found out (don't know if correctly), that each one has to be invited twice (to meet each other), but I don't know how to combine it. As a result, I got some this strange one:

$$\left( \begin{array}{c} 7 \\ 3 \end{array} \right)^7$$

And for the second one I got (using experimental method)

$$\frac{n}{3} + 1$$

Could someone explain these problems to me please?

Thank you.

 

[Bartholomew]

Edit: I gave an answer to the first which was an undercount. At the moment I can't think of any way to count it which does not involve fifteen or twenty terms.

The second question is easy. At every step each person must sit with two people whom he has not sat with before.

 

[MathematicalPhysicist]

i got 35 ways
but the way i got it was by counting, and it's not pretty at all, the only analytic way i can think is if you you have the maximum options when there arent restrictions i.e 7^2 and reduce from this 7*2.
you ask why?

well that's a good question, and i think bacuase in my way of counting i decided that there are always two guests that are constant and thus you change the other guests accordingly (and that way in each column i change the two constant guests).

but don't take my post for granted, ok.

 

[Bartholomew]

I think it's going to be a LOT more than 35. C(7, 3)^7 is the number of ways to invite the people without any restrictions, and I think it's safe to say that the number of legal ways to invite them is at least a substantial fraction of that. My original undercount was C(7, 3)^7 - C(6, 3)^7 * 7, which is 1054135040000000 - 8960000000 (if I punched it into the calculator right). And that's an _undercount_.

The way that I came up with that uses a lot of terms is you count the number of ways total, then subtract the number of ways to exclude friend 1, then subtract the number of ways to exclude friend 2 and NOT exclude friend 1, then subtract the number of ways to exclude friend 3 and NOT exclude friends 1 or 2, and subtract the number of ways to exclude friend 4 and NOT exclude friends 1, 2, or 3, and so on...
Representing what I have just said in symbols looks like this:
C(7,3)^7
- C(6,3)^7
- (C(6,3)^7 - C(5,3)^7)
- (C(6,3)^7 - C(5,3)^7 - (C(5,3)^7 - C(4,3)^7))
- (C(6,3)^7 - C(5,3)^7 - (C(5,3)^7 - C(4,3)^7) - (C(5,3)^7 - ... (dang, hard to figure out exactly what goes here)

That's going to have to happen for all 7 people, and each additional term to be subtracted keeps getting bigger, and moreover you have to really think about every term you write down. There must be a simpler way.

 

[Bartholomew]

I think twoflower's problem #1 is a difficult problem which deserves the attention of the math experts on the forum. I'm just learning about Stirling numbers and I think you need to use them in some way to solve the problem concisely, but I'm not yet sure how.

 

[twoflower]

I think twoflower's problem #1 is a difficult problem which deserves the attention of the math experts on the forum. I'm just learning about Stirling numbers and I think you need to use them in some way to solve the problem concisely, but I'm not yet sure how.

Well I think it shouldn't be that difficult (although it IS for me), because I'm in the first semester...

 

[Bartholomew]

Okay, I figured out how to do it simply--not using Stirling numbers but using the concept behind their derivation.

You start out with C(7,3)^7 ways to invite the friends and subtract (C(6,3)^7) * C(7,1) which is the number of ways to exclude each friend. But now you've twice subtracted each way to exclude two people--e.g. you've subtracted the exclusion of friend 1 and friend 2 once when you covered the exclusion of friend 1, and once when you covered the exclusion of friend 2. So you have to add each way to exclude two friends back once, so you add (C(5,3)^7) * C(7,2). Now you have to consider the exclusion of three friends--how many times have you covered each combination of three friends to exclude? So you add or subtract it back an appropriate number of times. Then you do the same thing for excluding four friends, and that's your answer, because you can't exclude more than four friends.

 

[MathematicalPhysicist]

bart, do you have a final result, or it's also an undercount?

 

[Bartholomew]

No, I believe that last post is the correct answer. I haven't worked it out to find out what number it actually is.

 

[AKG]

I think you're on the right track for problem 1. It might get messy in the computations, but you've got the right idea, as far as I can tell. For problem 2, each person will meet 2 people at a time, and has to meet 2 new people each time. There are 3k people, and if we consider person A, there are 3k - 1 other people. He has to meet them all, and since he's meeting them 2 at a time, the total number of sittings would have to be:

$$\frac{3k - 1}{2} = \frac{1}{2}(n - 1)$$

If n is even, then n-1 is odd, and half of an odd number is not an integer, so clearly it won't work out. Now, when n is even, it's obvious to see that if we had more than 0.5(n - 1) seatings, some people would meet twice, and if we had less than that many, some people wouldn't meet. On the other hand, if n is odd, since that number up there evaluates to a fraction, we will necessarily have either less or more seatings, and so will necessarily have those problems I just mentioned.

The general expression is:

$$\frac{t - 1}{s - 1}$$

 

[Bartholomew]

I think you're on the right track for problem 1.

I'M not the one who's asking for help!