# Homework Help: Combinatorics teaser (counting problem)

1. Sep 11, 2011

1. The problem statement, all variables and given/known data
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)

2. Relevant equations

3. 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.

2. Sep 11, 2011

### 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

3. Sep 11, 2011

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.

4. Sep 11, 2011

### lanedance

perhaps you need to sum over all possible m?

5. Sep 11, 2011

### lanedance

this does not take in to account the ordering of the talks on the day. This may be ok but you will need to be clear exactly what is important.
this is not how i read the question in your initial post (post#1) - you should write the question exactly as it was written
as mentioned with the currently proposed method, you will probably need to sum over m

Last edited: Sep 11, 2011
6. Sep 12, 2011

### Robert1986

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?

7. Sep 12, 2011

### 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).

8. Sep 12, 2011

### 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.

9. Sep 12, 2011