Combinatorics teaser (counting problem)

[proptrader]

Homework Statement

A teaching event takes two days and involves n people. Some of the
people give a talk on day 1, some others give a talk on day 2.
Everybody gives at most 1 talk, and there can be some teachers who
do not give a talk in either of the two days. At the end of the event, a few talks
are picked to be included in a book. In how many different ways can
this all happen? (there has to be at least one talk selected)

Homework Equations

The Attempt at a Solution

I suspect that once you have found in how many ways can you have people give talks in either of the two days (say x), you can use that a set containing x elements has 2^(x) subsets and this would be the number of possible ways to select the talks.

 

[lanedance]

i would start as follows:
how many talks total are given (m)
how many different orders and people can the m talks be given (ignoring the split between days)
how many ways can you split m ordered talks between 2 days
then given there are m talks, how can you choose a subset of these to be included in the book and is order important

 

[proptrader]

I can't see how this procedure would lead me to an answer. Specifically I don't see how to get rid of m.

Here is what I've got:
I suspect that each person has 3 choices: to talk on the first day, to talk on the second day, or not to talk at all. This implies that there are 3^n ways of forming the talking schedule. However, the question asks how many ways are there to pick talks for a book.

Another thing i know is that if we have m people that spoke at the event we have 2^m ways of picking the talks for the book. I can't see how to find that m from what i have claimed earlier.

 

[lanedance]

perhaps you need to sum over all possible m?

 

[lanedance]

I can't see how this procedure would lead me to an answer. Specifically I don't see how to get rid of m.

Here is what I've got:
I suspect that each person has 3 choices: to talk on the first day, to talk on the second day, or not to talk at all. This implies that there are 3^n ways of forming the talking schedule.

this does not take into account the ordering of the talks on the day. This may be ok but you will need to be clear exactly what is important.

However, the question asks how many ways are there to pick talks for a book.

this is not how i read the question in your initial post (post#1) - you should write the question exactly as it was written

Another thing i know is that if we have m people that spoke at the event we have 2^m ways of picking the talks for the book. I can't see how to find that m from what i have claimed earlier.

as mentioned with the currently proposed method, you will probably need to sum over m

 

[Robert1986]

Hmmm. What about this:

Assume that all n teachers have prepared a talk, so there are n talks. Now, how many ways can each talk turn out (ie, a talk can be given on the first day and included in the book, given on the first day and not included in the book, not be given at all, etc.). Does this seem like it might help?

 

[lanedance]

not a bad idea, depending on whether order is important, however you will have to be careful abut 1 talk being selected (i assume this applies to each day and and the book).

 

[Robert1986]

Yeah, if order matters I haven't yet come up with a solution that does not involve a sum. But, if order doesn't matter, and you take into consideration the things you mentioned, this'll work.

 

[proptrader]

As simple as this idea is - it sounds great.

I suppose if you could come up with a solution to the following problem this would help solve the current: Our goal is to select two subsets A and B of {1,2,3,4...,n} such that A∩B=Ø. In how many ways is this possible?

 

[lanedance]

shouldn't it be 5 subsets?

This would lead you to something similar to Stirling numbers of the 2nd kind
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

however I do think you can solve this one easy enough, and inclduing a sum shouldn't be an issue