What is the minimum number of gems required to make a garland (circular) which contains all permutations, with unique colored gems considered as a valid permutation, of size n, when we have infinite number of gems of N colors.
The garland is circular, so we don't need to consider reverse direction of same permutation (eg. if 123 is present, 321 is also present) Also, we don't need to consider concatinating extra gems at the end, if the are present in the beginning (eg, 123 also contain 231) Example : for 4 colors, we need our garland to have (123, 124, 132, 134, 142, 143 etc...)
It is different from de bruijn sequence, as de bruijn sequence will contain 111, 121 etc as well, so it will be LONGER, and these permutations are not counted.
My approach : suppose n = 3, and N = 5. then, we will have numOfCombs = (N! / ((N-n)! * n!) ) combinations of them. for any combinations, "123", we can make a string "12312", which will have all permutations. So, as there are numOfCombs combinations, and for each combination we can have a string of length 5 which contains all permutations. so (numOfCombs * 5), in this case, gives 50. However, this can be optimized. as, 12312, and 12412, can be grouped together, as 12312412, we can decrease this length. We will not have common length 3, we can have only 2 and 1 as common length, so after optimizing this, we can have string of length 40.
However, this was for length 3, for which i calculated this manually. for 4, 5... i am not able to get any relation...
I believe this is a variant of a question first asked by Hansraj Gupta in 1981. Michael Engen and I surveyed many similar problems in a paper called Containing all permutations; this particular variant is discussed briefly in the second item of the conclusion.