Karlheinz Stockhausen's Klavierstück XI consists of 19 fragments. The performer may begin with any fragment, and continue to any other, until a fragment has been reached for the third time, when the performance ends.
I need to calculate how many ways it can be played.
Some observations:
-
minimum length of performance is 5: let $a$, $b$, $c$ be any fragments, where $b\neq a, c \neq a$ and order would be $a$ $b$ $a$ $c$ $a$. There is $19 \cdot 18 \cdot 18 = 6156$ possible ways to play it in most short form.
-
maximum length is 39: every fragment is played twice then any is played for the third time, and the performance ends. If fragment can be played twice in a row, then number of variants would be equal to $$\frac{19! \cdot 18}{2^{19}}$$ (count of multiset permutations of $\{1, 1, 2, 2, … 19, 19\}$ multiplied to 18 final fragments, because it can not be same as previous).
Also when length is non-maximal, some elements can occur only once and therefore number of possible final elements is lesser than 19. I suppose it is possible to split that calculation in two parts:
For each $n$ from $1$ to $19$:
- calculate number of multisets, where exactly $n$ elements occurs twice
- calculate number of permutations with restrictions from that multiset (that part cause troubles)
UPD: thanks to user, correct formula for length 19 orders is $\frac{38! \cdot 18}{2^{19}}$, not $\frac{19! \cdot 18}{2^{19}}$
Best Answer
First note: if the order of fragments could be arbitrary the correct answer would be: $$ 18\times\frac {38!}{2^{19}}, $$ where 18 counts the number of ways to choose the last fragment (it cannot be the same as the last of the previous 38).
If no fragment can be played in a row, we should exclude such paired events. This can be done using inclusion exclusion principle and the final answer is: $$ 18 \times \sum_{j=0}^{19}(-1)^j\binom{19}j\frac {(38-j)!}{2^{19-j}}. $$