How to calculate permutations with limited repetitions

53 Views Asked by At

I have $246$ appointments, that can be scheduled in only $10$ timeslots. However, $5$ time slots can take up to $30$ ($s_1$) appointments, and the other $5$ can take up to $20$ ($s_2$) appointments.

How to calculate the Permutations with limited repetitions of this problem:

$$n=10, r=246, s_1=30\text{ and }s_2=20$$

What if we simplified the problem to:

$$n=10, r=246, s= 30\text{ for all slots}$$

If the $246$ are variables: $x_1, x_2, x_3,\ldots x_{246}$, and the $10$ timeslots are: $y_1,y_2,\ldots y_{10}$

How to write an equation/constraint that limits the possible Permutations to be only the ones that satisfy the limited repetition (max $30$ of each time slot)?

1

There are 1 best solutions below

0
On

As a starting hint, consider the development of the following multinomial

$$ \begin{array}{l} \left( {s_1 + s_2 + s_3 + s_4 + s_5 } \right)^{246} = \\ = \cdots \; + \underbrace {\left( {s_1 ^1 s_2 ^0 s_3 ^0 s_4 ^0 s_5 ^0 } \right)}_{1st\;app.\;in\,\;slot\;1} \underbrace {\left( {s_1 ^0 s_2 ^0 s_3 ^0 s_4 ^1 s_5 ^0 } \right)}_{2nd\;app.\;in\,\;slot\;4} \cdots \underbrace {\left( {s_1 ^0 s_2 ^1 s_3 ^0 s_4 ^0 s_5 ^0 } \right)}_{246th\;app.\;in\,\;slot\;2} + \; \cdots = \\ = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,k_{\,j} \, \le 30} \\ {k_{\,1} + k_{\,2} + \, \cdots + k_{\,5} \, = \,246} \\ \end{array}} \right.\;} {\left( \begin{array}{c} n \\ k_{\,1} ,\,k_{\,2} ,\, \cdots ,\,k_{\,5} \\ \end{array} \right)s_{\,1} ^{k_{\,1} } s_{\,2} ^{k_{\,2} } \cdots s_{\,5} ^{k_{\,5} } } \\ \end{array} $$

where in the multinomial sum we limit the exponents to be not more than $30$
(Note: actually in this case the sum of the five slots could not reach to 246, but take it to be $m$ and just consider the approach)

Then pass to consider $$ \left( {s_1 + s_2 + s_3 + s_4 + s_5 } \right)^m \left( {r_1 + r_2 + r_3 + r_4 + r_5 } \right)^n \quad \left| \begin{array}{l} \;m + n = 246 \\ \;0 \le s_j \le 30 \\ \;0 \le r_j \le 20 \\ \end{array} \right. $$

However, since $5 \cdot 30 + 5 \cdot 20 = 250$, you have better to consider the number of ways to distribute $4$ null-appointments into a filled-up agenda.