1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics teaser (counting problem)

  1. Sep 11, 2011 #1
    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. jcsd
  3. Sep 11, 2011 #2

    lanedance

    User Avatar
    Homework Helper

    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
     
  4. Sep 11, 2011 #3
    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.
     
  5. Sep 11, 2011 #4

    lanedance

    User Avatar
    Homework Helper

    perhaps you need to sum over all possible m?
     
  6. Sep 11, 2011 #5

    lanedance

    User Avatar
    Homework Helper

    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
  7. Sep 12, 2011 #6
    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?
     
  8. Sep 12, 2011 #7

    lanedance

    User Avatar
    Homework Helper

    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).
     
  9. Sep 12, 2011 #8
    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.
     
  10. Sep 12, 2011 #9
    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?
     
  11. Sep 12, 2011 #10

    lanedance

    User Avatar
    Homework Helper

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics teaser (counting problem)
  1. Combinatorics problem (Replies: 7)

  2. Combinatorics problem (Replies: 2)

  3. Combinatorics problems (Replies: 8)

Loading...