Combinatorics teaser (counting problem)

In summary, the problem involves a teaching event where n people give talks on two days, with at most one talk per person. A few talks are selected for a book at the end of the event. The number of ways this can happen is dependent on the number of talks given and the number of ways they can be split between the two days. If order is important, a sum must be used to find the total number of ways. If order is not important, the solution involves selecting two subsets from a set of n elements, which can be solved using Stirling numbers of the second kind.
  • #1
proptrader
10
0

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.
 
Physics news on Phys.org
  • #2
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
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
perhaps you need to sum over all possible m?
 
  • #5
proptrader said:
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.
proptrader said:
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
proptrader said:
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
 
Last edited:
  • #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?
 
  • #7
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
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
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?
 
  • #10

FAQ: Combinatorics teaser (counting problem)

1. What is combinatorics?

Combinatorics is a branch of mathematics that deals with counting and arrangements of objects without actually listing out all the possibilities.

2. What is a combinatorics teaser or counting problem?

A combinatorics teaser, also known as a counting problem, is a puzzle or problem that involves finding the number of ways that a certain set of objects or events can be arranged or combined.

3. What are some common types of combinatorics teasers?

Some common types of combinatorics teasers include permutation problems, combination problems, and binomial coefficient problems. These problems often involve counting the number of ways to arrange or select objects from a given set.

4. How can I approach solving a combinatorics teaser?

To solve a combinatorics teaser, it is important to carefully read and understand the problem, identify the type of problem it is, and then use the appropriate counting techniques (such as the multiplication principle or the binomial coefficient formula) to find the solution.

5. What are some real-world applications of combinatorics?

Combinatorics has many applications in fields such as computer science, genetics, and statistics. It can be used to calculate probabilities, design efficient algorithms, and analyze data sets with large numbers of possibilities.

Back
Top