5

What is the number of permutations of $m$ objects in $n$ spaces such that there are exactly $l$ repetitions in the permutation?

for example, if $m = 5, n = 7, l = 4$
then $$a_1, a_1, a_1, a_3, a_3, a_4,a_4$$ is a legal sequence (4 repetitions, $a_1$ twice, $a_3$ once and $a_4$ once) but
$$a_1, a_2, a_3, a_1, a_3, a_5, a_3$$ is not (only 3 repetitions). and neither is
$$a_1,a_1,a_1,a_1,a_1,a_1,a_1$$ legal.

The main difference of this problem from other posts such as Calculating number of permutations given N repeats allowed is that my number of repeats is global, i.e I require that the number of repetitions of all objects together is exactly l.

Pbehhe
  • 53
  • This seems like a tough one. If I have understood the query correclty, then (for example), if $n = 4, m = 2,$ and $l = 2$ then you could have either $x_1,x_1,x_2,x_2 : \binom{4}{2}$ or $x_1, x_1, x_1, x_2 : \binom{4}{1}$ or $x_2, x_2, x_2, x_1 : \binom{4}{1}.$ Then the total would be $(6 + 4 +4 = 14).$ This one is no walk in the park. – user2661923 Nov 28 '20 at 13:37
  • Where is m=5 figuring ? Also, if you have, say, $a_1, a_1, a_1$ it is normally considered as three repetitions of $a_1$ – true blue anil Nov 28 '20 at 13:38
  • @trueblueanil $m=5$ means that there are $m$ distinct elements that may be used in the sequence: $x_1, x_2, \cdots, x_5.$ Although your point about the connotation of repetitions is well taken, it is also irrelevant to the query. The OP has unambiguously defined how repetitions are to be counted, and the query must be attacked under the OP's (arbitrary) definition. – user2661923 Nov 28 '20 at 13:41

1 Answers1

3

You can pick the elements to be in the sequence that are going to be repeated(say $k$ of them) and then consider the repetitions by constructing a sequence $x_i=\text{# times object i repeats},$ so that $$\sum _{i=1}^kx_i=l,\, x_i\geq 1.$$ Notice that if we call $k$ the ones that are going to be repeated, then $n-(l+k)$ are non repeated elements. So your expression is $$\sum _{k=0}^m\binom{m}{k}\binom{m-k}{n-(l+k)}\sum _{x_1+\cdots +x_k=l}\binom{n}{\underbrace{1,\cdots ,1}_{n-(l+k)},x_1+1,\cdots ,x_k+1}.$$ Now, if this can be expressed in easier terms seems a problem for generating functions, the problem being multivariate by nature.

Phicar
  • 14,722
  • Would the formula be simpler if I asked for at most l repetitions? – Pbehhe Nov 28 '20 at 14:42
  • 1
    You will have to define to me "simpler", the problem is that one has to take care of each repeated term by a separate factorial, that is why the second sum is not expressed in easier terms(as far as I can see). If you do it for at most $l,$ we will have another sum, actually. Not sure if anything will be simplified. Is this a problem for research? If so I would suggest coding this and trying to search for some OEIS sequence fixing some of the variables involved. – Phicar Nov 28 '20 at 14:45
  • @Phicar would you add an edit with this example please because I can't understand exactly what k and some parts of formula should be filled. The example is: all the permutations of 10-digit numbers from digits 0 to 9 with global repetition of 3, like: 9576545100, 9901286787, 7890000234. – Eftekhari Sep 09 '21 at 19:23
  • @phicar is it possible to get number of variations in a range of numbers with only knowing the l and not k? I mean just knowing there are for example 3 repetitions in numbers that we want and we do not know which digits are repeated. – Eftekhari Sep 11 '21 at 16:50