The big question:
- Suppose we have n-permutators, i.e. permutators of total size n (a 7 permutator will contain numbers from 1 to 7). How many n-permutators have loop length l?
How to approach this: We must go case-wise, and first analyse the numbers given to determine what method we should use.
Here are the following possible cases:
C1: $l\le n, l$ is prime
We must use only translation method.
Reasoning: We cannot use LCM method, as since $l$ is prime it will not have any factors other than 1 and itself.
- Note that using $l,1$ as the factors makes no sense, as a group of means nothing can be changed.
- Hence, we would be doing just $l$, which is the same as the translation method.
- Hence the LCM method kinda does apply? We can consider the translation method a subpart of the LCM method.
C2: $l \le n,l$ is not prime
We must use both translation and LCM method (or as stated above, LCM including translation)
Reasoning: Translation is viable as $l\le n$. LCM is viable since $l$ is not prime, i.e. has common factors that can produce $l$ as their LCM.
C3: $l>n,l$ is prime
Neither method used. Total n-permutators = 0.
Reasoning: Translation is not viable as $l>n$. LCM is not viable as $l$ is prime. Hence, there is no method to find n-permutators, hence none exist.
C4: $l>n, l$ is not prime
l
We must only use LCM method.
Reasoning: Translation is not viable as $l>n$. LCM is viable as $l$ is not prime.
Methods
Translation
Suppose we have $l \le n$.
That means we can directly choose a group of numbers of size $l$, and by arranging the numbers in this group such that none remain in their original spot, we have produced an n-permutator with loop length $l$.
The formula for this is as follows:
$n$-permutators =${n\choose l} \times (l-1)!$
LCM Method
Suppose $l$ is not prime.
$l$ thus has factors other than one and itself. Let us express $l$ as these factors:
$l = a\times b \times c \times \dots$, where $a,b,c,\dots$ have no common factor.
Hence, we must consider grouping each of these factors.
The formula for this is as follows:
$n$-permutators $= {n \choose (a+b+c+\dots)} \times {(a+b+c+\dots) \choose a} \times {(b+c+\dots) \choose b} \times \dots \times (a-1)!\times (b-1)!$
Very important things to realise!
Composite compatibility
Suppose $l$ is not prime.
The equations only hold if, and only if the factors of $l$ add up to $\le l$ AND share no common factors within the factors of $l$, alongside the other conditions.
For example, take a loop length of 12 for a 7-permutator.
12's factors are 1,2,3,4,6,12. We don't count 1 cause bruh.
Hence, 2,3,4,6,12 are potential groupings. We eliminate those greater than n, i.e. 12.
We are left with 2,3,4,6 as potential groupings.
In this case, we know that the groupings must have LCM of 12 AND their sum be less than 7.
$2\times 6$ would be viable, yielding $12$, but $2+6 = 8, 8>7$.
We are left with $3,4$. These are factors that share no common factors within themselves, and have LCM of $l$.
It follows these are the only solutions to $n=7,l=12$.
Now take a loop length of 8 for a 7-permutator.
Once again, factors of 8 are 1,2,4,8. One is not counted, and as $8>7$, it is not possible.
Hence, we are left with factors $2,4$. But the issue is, these factors share common factor of 2! Hence we must also disregard this case, and are left with no possible factors.
And thus, there are no solutions for loop length 8, 7-permutator.
Multiple groups of same size
Sometimes, if the value of $l$ is small enough such that the sum of its factors are $\ll n$, we can add groups with the same size as one of the factors to create new permutators, still within the limit of $
Take $n=7,l=6$.
Initially, one would approach this by determining the 7-permutators with the following groupings:
{6},{2,3}
Notice how $2+3=5, 5\le7$. But if we were to do ${2,2,3}$, we would get $2+2+3=7, 7\le 7$.
Hence, we can essentially double or triple up on groupings of small factors to create new permutators.
Hence, revisiting the total groupings:
{6},{2,3},{2,2,3}
These are all the possible groupings.
Let $r$ be the amount of times we repeat factor a. When calculating the LCM formula for said grouping, i.e. {$a,a,a(r \ times),b$} we must divide by $r!$.
Suppose $n=7,l=6$.
It follows that the segment of the solution corresponding to ${2,2,3}$ is:
$\frac{{n \choose (ra+b)} \times {(ra+b) \choose a} \times {((r-1)a + b) \choose a} \times \dots \times {b \choose b} \times ((a-1)!)^{r}\times (b-1)!}{r!}$
We can have multiple factors with multiple instances of their groupings. This is especially true for greater values of $n,l$.
Key examples
$n=7,l=6$
We know $l \le n, l$ is non-prime.
Hence, we must use translation and LCM method.
Hence, the groupings are as follows:
{6},{2,3},{2,2,3}
Hence, the total 7-permutators are as follows:
$${7 \choose 6}\times (6-1)! + {7 \choose 5} \times ({5 \choose 2} \times {3 \choose 3} \times (2-1)! \times (3-1)!) + {7 \choose 7} \times \frac{{7\choose 2} \times {5 \choose 3} \times {3 \choose 3} \times (2-1)! \times (2-1)! \times (3-1)!}{2!}$$
$n=12, l = 6$
We know $l \le n, l$ is non-prime.
Hence, we must use translation and LCM method.
Hence, the groupings are as follows:
{6},{2,3},{2,2,3},{2,2,2,3},{2,2,2,2,3},{2,3,3},{2,3,3,3}
I will leave the rest of the solution as an exercise for the reader. Note that we will probably not get a question of such a scale.
$n=7, l = 8$
We know that $l>8, l$ is non-prime, so we can only use LCM method.
Yet, LCM method does not give any possible groupings, as all viable groupings have common factors and thus do not have LCM of 8.
(This can be summaried by saying 8 has no factors that sum to less than 7 that give LCM of 8.)
Hence, no groupings exist for LCM.
Thus, there exists 0 7-permutators for loop length 8.
$n=7,l=5$
We know $l\le n, l$ is prime.
So we can only use translation method.
Thus,
7-permutators $= {7 \choose 5}\times(5-1)!$
$n = 5, l = 7$
We know $l > n,l$ is prime.
This means we cannot use both translation and LCM method. There is thus no way to create a 5-permutator with loop length 7.
Hence, 5-permutators = 0
DONE
With love(but not for dasindu)
Ed
