I need a math formula for counting distinct n- letter long array permutations.
Let me explain. Let's say we have 3 arrays of following letters: A, B, C, where A is a 4 member long array (A[0],A[1],A[2],A[3]), B is a 4 member long array and C is a 1 member long array.
How do I calculate the total number of all unique n-letter long permutations, without programmatically permuting through them?
--
EXAMPLE
Letter combination:
A, B, B, C
Given array lengths of each letter (as described above) I know there are 768 unique permutations. I got to 768 by writing a program that goes through all of the combinations, discarding duplicates.
These are unique combinations such as:
A[0],B[0],B[0],C[0]
or
C[0],B[3],A[3],B[1]
However, I need a mathematical formula to answer how many unique permutations are there for any number of letters and any length of the letter arrays.
I need this for my open source project that solves tetronimo based puzzles: https://github.com/JozefJarosciak/TetronimoPuzzleSolver/
I'll state the problem as follows: we have $k$ different arrays, and in each array $A_\ell$ (for $1 \leq \ell \leq k$), we have a choice of $m_\ell$ elements. We are given a number of elements $n_\ell$ to use from each array $A_\ell$ to create an (ordered) $n$-element string, with $n = \sum_{\ell=1}^kn_\ell$. (The choice is made "with replacement," i.e., the same element is allowed to appear multliple times in the string.) How many strings are possible?
One method to do this is to first determine the ordering of the arrays, then make the choices in each slot. I.e., first we create a string that looks like $A_1 A_3 A_2 A_2$, then we choose a particular element from $A_1$ for the first slot, a particular element from $A_3$ for the second slot, etc. The number of ways to order the arrays is given by the multinomial coefficient $$\binom{n}{n_1, n_2, \dotsc, n_k} = \frac{n!}{n_1!n_2!\cdots n_k!}$$ The number of choices in a particular slot in which $A_\ell$ appears is $m_\ell$, and since $A_\ell$ appears in $n_\ell$ slots, the total number of choices for all appearances of $A_\ell$ is $m_\ell^{n_\ell}$. Thus the total number of possible strings is $$\frac{n!}{n_1!n_2!\cdots n_k!} m_1^{n_1} m_2^{n_2} \dotsc m_k^{n_k} $$
In your example, I'll call your arrays $A = A_1$, $B = A_2$, and $C= A_3$. Then we have $m_1 = m_2 = 4$, $m_3 = 1$, $n_1 = n_3 = 1$, $n_2 = 2$, $n = 1 + 2 + 1 = 4$. We thus get an answer of $$ \frac{4!}{1!2!1!}4^14^21^1 = 768$$