I came across the following solved question in a book and am having difficulty understanding the answer given for it.

Q: A conference is to have eight presentations over the course of one day, consisting of three long presentations, and five short presentations. If the conference organizer doesn't want consecutive long presentations, and the conference is to start with a short presentation, how many schedules of presentations are possible?

A: Let S and L stand for a short and long presentation respectively. The schedule must start with a short presentation, and every long presentation must be followed by at least one short presentation. So the schedule must be SLSLSLS, along with one more short presentation inserted somewhere. There are four ways to do this - SSLSLSLS, SLSSLSLS, SLSLSSLS, and SLSLSLSS. For each of these there are 5! * 3! possible schedules, giving a total of 2880 schedules.

My analysis gave 7200 schedules instead as follows.

The first S is fixed. This leaves four S's and three L's to be permuted with the no-two-consecutive-L restriction. Or let's generalize it to a S's and b L's. Then the number of compatible permutations, written as N(a, b), can be expressed as the recurrence N(a - 1, b) + N(a - 1, b - 1). Observing the terminal values N(0, 1) = 1, N(1, 0) = 1, N(1, 1) = 2 and N(0, 2) = 0, and substituting a = 4 and b = 3, the number comes to 10. This gives a total of 10 * 5! * 3! = 7200 schedules.

What am I missing?

  • $\begingroup$ So are you saying that you're getting two different answers by two different methods? I've deleted my answer because I'm not entirely sure I understood your question when I answered. $\endgroup$ – Ataraxia Jul 9 '13 at 21:50

The solution in the book is wrong as it ignores cases with $L$ at the end. Using, ZettaSuro's notation: $$ S\_S\_S\_S\_S\_$$ Each of the three long presentations can go in one of the 5 blankes: $$5\choose 3 $$ which ultimately gives $$ {5\choose 3 }\cdot 5!\cdot 3! = 7200.$$

  • $\begingroup$ But there is no case with $L$ at the end: "every long presentation must be followed by at least one short presentation" $\endgroup$ – Tomas Jul 9 '13 at 21:56
  • 1
    $\begingroup$ @Tomas Look carefully, where you got that quote from! Not from the question, which says "doesn't want consecutive long presentation" $\endgroup$ – Hagen von Eitzen Jul 9 '13 at 22:00
  • $\begingroup$ Sorry, I was too fast. You are of course right. $\endgroup$ – Tomas Jul 9 '13 at 22:09
  • $\begingroup$ @Anant: Using your setup, we can translate Hagens remark to: The book wrongly assumes $N(1, 0) = 0, N(1, 1) = 1$. (Using this start values, you actually get 2880) $\endgroup$ – Tomas Jul 9 '13 at 22:32
  • $\begingroup$ @Hagen Thanks for the elegant answer! $\endgroup$ – Anant Jul 10 '13 at 8:11

Arrange the $5$ short presentations in $5!$ ways, alternating with four slots.

Arrange the $3$ short presentations in $3!$ ways.

Pick a slot to leave empty in $4$ ways.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.