4
$\begingroup$

Is there a formula to calculate all possible unique permutations of n elements over p positions?

Please imagine the following scenario: I have p positions (cells/spaces) to fill each with one element, let's have use letters as elements for example. I have n letters in total and there may be some duplicate ones among them but I know in advance how many unique letters I have, s, and how many duplicates I have for each letter (0 or more).

So, resuming the situation, we have:

p = number of positions (cells/spaces to be filled with one element each);

n = number of total elements available (we'll take letters);

s = number of single symbols (= the total number of elements not counting duplicated ones, so let's have S is the set containing these symbols, s is its cardinality: s=|S|);

Obvious rule here is:

n >= p >= 1

and

n >= s >= 1

('cause s is a sort of subset of the n elements without duplicates, n = s when there's no duplicated elements.)

Then we can have Oi, with i = 1...s, to know either the number of duplicates (0 <= Oi < n) -OR- instances (1 <= Oi <= n) of every S symbol (free choice on this, even I prefer the latter approach).

As a clarification case let's consider the letters that form the word "danicotra" and suppose we have 9 free spaces to fill with them. In this case we will have: p = 9, n = 9 and s = 8 (s is 8 because there are two "a" in "danicotra" so we have 9 elements (n) but only 8 single symbols (s) keeping the duplicate elements aside); the "symbols set" is S={d,a,n,i,c,o,t,r} and therefore we'll have the following 8 single symbols:

Symbol1 = "d"
Symbol2 = "a"
Symbol3 = "n"
Symbol4 = "i"
Symbol5 = "c"
Symbol6 = "o"
Symbol7 = "t"
Symbol8 = "r"

and Oi (with i = 1...8), if we count number of duplicates per symbol, like this:

O1=0
O2=1
O3=0
O4=0
O5=0
O6=0
O7=0
O8=0

or if we count number of instances per symbol (that is my favored), like this:

O1=1
O2=2
O3=1
O4=1
O5=1
O6=1
O7=1
O8=1

Ok, now that we took the above as sample case (and I described what p, n, s, S and Oi are like in this situation), let's get back to the question: is there a general formula I can apply to know the number of the possible unique(*) permutations with it?

(*) unique = I mean, 'cause I might happen having repetitions/duplicates if a same "symbol" is present more than once amongst the elements and I don't want to take 'em into account (see image below for example)

enter image description here

EDIT:

There's a general formula that works only "partially":

$$ \frac{n!}{(n-p)! \ (\prod_{i=1}^s O_i!)} $$

BUT, as I just said, it only works "partially", that is:

  • it gives correct results only if I have no duplicated symbols amongst n elements (n = s) OR when I have (n-1) <= p <= n,
  • while it fails when I have duplicated elements amongst n symbols (1 <= s < n) AND I have 1 <= p < (n-1).

In other words, it works with the above example with the word "danicotra" just because I have 9 elements and 9 positions to fill (n = p) but if I need to calculate the same thing with, for instance, p = 7 ... that's the pain! :(

So far I'm still looking for the right formula, that works always.

Thanks for help

$\endgroup$
3
  • 2
    $\begingroup$ My post at stats.stackexchange.com/a/415878/919 provides a general solution to this kind of problem. $\endgroup$ – whuber Nov 1 '19 at 17:27
  • $\begingroup$ @whuber so far it sounds like a -spoiler alert- there's no general formula to calculate it, so you have to work it out "case by case"... Anyway I'll have a more careful reading to better understand, thanks! :) $\endgroup$ – danicotra Nov 2 '19 at 13:53
  • $\begingroup$ @whuber, I am pessimistic, that your general result helps here, since the calculation of $g_i$ in your formula is part of the problem and imho non-trivial. Could you provide an example for applying the formula with some non-trivial values of n, p, s and Oi? $\endgroup$ – ghlavin Nov 2 '19 at 14:22
2
$\begingroup$

I think a formula might be harder to describe than a simple algorithm.

You appear to characterize a multiset $X = \{x_1^{k_1}, x_2^{k_2}, \ldots, x_s^{k_s}\}.$ This notation refers to $k_i$ copies of the element $x_i.$ (Your number $n$ is the sum of the $k_i.$) I am going to order the elements of $X$ so that $x_1$ is followed by $x_2$ etc. (Such an ordering is not part of the usual notion of a multiset but will be useful for the analysis.)

Write $\mathbf{k}=(k_1,k_2, \ldots, k_s).$ For any natural number $p,$ let $f(p,\mathbf{k})$ be the number of permutations of length $p$ from $X$ (which clearly depends only on $\mathbf{k}$ and not on what the objects $x_i$ might be). That is, any such permutation $\sigma = (\sigma_1, \sigma_2, \ldots, \sigma_p)$ consists of elements of $X,$ with any $x_i$ appearing no more than $k_i$ times; and two such permutations $\sigma$ and $\tau$ are considered the same when $\sigma_i=\tau_i$ for all $i.$

Any such permutation has a re-ordering in which its first elements are $x_1,$ the next ones are $x_2,$ and so on. Let's call this a "sequenced" permutation. Let $l_i$ be the number of times $x_i$ appears (entailing $0\le l_i \le k_i,$ obviously, and the sum of the $l_i$ is $p$). (Considerations outlined in my post at https://stats.stackexchange.com/a/415878/919 make it clear that the number of such re-orderings is $p!$ divided by the product of all the $l_i!$. This justifies the last calculation in the function g defined below.)

We may therefore count all such permutations by enumerating sequenced permutations. These naturally fall into at most $k_1+1$ groups according to how many copies of $x_1$ appear in the permutation; namely $l_1.$ Once we know the elements of the permutation other than $x_1$ and their sequence within the permutation, the number of distinct possible positions for those copies of $x_1$ is the binomial coefficient $\binom{p}{l_1}.$

This yields the recursion

$$f(p,\mathbf{k}) = \sum_{i=0}^{\min(k_1,p)} \binom{p}{i}f(p-i, \mathbf{k}_{\hat 1})$$

where $\mathbf{k}_{\hat 1} = (k_2, k_3, \ldots, k_s)$ and $s\gt 1,$ with the base case

$$f(p, (k_s)) = \left\{\matrix{1 & \text{if }p\le k_s \\ 0 & \text{otherwise.}}\right.$$

The worst-case computational effort is proportional to the product of the $(k_i+1).$ Not good, but practicable for small multisets representing, say, words in natural languages.


As an example, consider the string "mississippi" considered as the (ordered) multiset $\{i^4, s^4, p^2, m^1\}$ so that $\mathbf{k}=(4,4,2,1).$ Letting $p=2,$ for instance, we find nine sequenced permutations ii, is, ip, im, ss, sp, sm, pp, and pm. Corresponding to sequences of the same letter like "ii" there is just one permutation while corresponding to sequences of distinct letters like "is" there are two permutations ("is" and "si"). The resulting total is $15.$

With the recursion we find

$$f(2, (2,1)) = \binom{2}{0} f(2,(1)) + \binom{2}{1} f(1, (1)) + \binom{2}{2} f(0,(1)) = 0 + 2 + 1 = 3;$$

$$f(1, (2,1)) = \binom{1}{0} f(1,(1)) + \binom{1}{1} f(0,(1)) = 1+1=2;$$

and

$$f(0, (2,1)) = 1.$$

Therefore

$$f(2,(4,2,1)) = \binom{2}{0} f(2,(2,1)) + \binom{2}{1} f(1,(2,1)) + \binom{2}{2} f(0,(2,1))= 3 + 4 + 1= 8.$$

Similarly we can work out that $f(1,(4,2,1)) = 3$ and $f(0,(4,2,1))=1,$ whence

$$f(2,(4,4,2,1)) = \binom{2}{0}f(2,(4,2,1)) + \binom{2}{1}f(1,(4,2,1)) + \binom{2}{2}f(0,(4,2,1) = 8+6+1 = 15,$$

agreeing with the previous enumeration.


Here is an R implementation of $f.$

f <- Vectorize(function(n, k) {
  if (length(k) == 1) {
    ifelse(n <= k, 1, 0)
  } else {
    sum(sapply(0:min(n,k[1]), function(i) choose(n, i) * f(n-i, k[-1])))
  }
}, "n")

For example,

f(2, c(4,4,2,1))
[1] 15

As a check, here is a brute-force count (which assumes k is a named vector and n is no greater than the sum of its elements):

g <- Vectorize(function(n, k) {
  x <- unlist(lapply(names(k), function(s) rep(s, k[s])))
  l.x <- lapply(seq.int(n), function(i) seq_along(x))
  A <- t(combn(seq_along(x), n))
  X <- matrix(x[as.matrix(A)], nrow=nrow(A), ncol=ncol(A))
  if(dim(X)[2] > 0) X <- X[!duplicated(X), , drop=FALSE]
  sum(apply(X, 1, function(x) {
    k <- table(x)
    round(exp(lfactorial(sum(k)) - sum(lfactorial(k))))
  }))
}, "n")

(The reason for naming elements of k, which otherwise is unnecessary, will be apparent upon inspecting the table X: its rows are the sequenced permutations.)

For example,

k <- c(i=4,s=4,p=2,m=1)
g(2,k)

produces the same output as before. (R aficionados may notice how multisets are so natural on that platform: they are neatly represented by arrays of non-negative integers having unique component names.)

As a test, we may list the counts of permutations of all possible lengths for the "mississippi" multiset:

p <- c(0, seq_along(x))
results <- rbind(Formula=f(p,k), `Brute force`=g(p,k))
dimnames(results) <- list(rownames(results), n=p)
(results)
             p
              0 1  2  3   4   5    6    7     8     9    10    11
  Formula     1 4 15 53 176 550 1610 4340 10430 21420 34650 34650
  Brute force 1 4 15 53 176 550 1610 4340 10430 21420 34650 34650

They agree out to length $11;$ there are no other permutations.

$\endgroup$
1
  • 1
    $\begingroup$ Whoa, I'd upvote it twice if I could, thanks for your answer! I really appreciated both the explanations and the R code examples, great! I was hoping for a more "straight to apply" formula for it but I think I realized such a thing couldn't exist due to the (not so immediately clear) complexity of these class of problems, so I'll accept this as the answer, thank you very much! $\endgroup$ – danicotra Nov 5 '19 at 21:30
0
$\begingroup$

Solutions to a couple of famous problems of this type:

Arrangements of letters in MISSISSIPPI: $11!/(4!\cdot 4! \cdot 2!).$

And in STATISTICS: $10!/(3!\cdot 3! \cdot 2!).$ Also, ${10 \choose 3}{7 \choose 3}{4 \choose 2}2!.$

Relevant to binomial PDF: Arrangements of letters in SSSFF: $5!/(3!\cdot 2!) = {5 \choose 2}.$

$\endgroup$
1
  • $\begingroup$ Yeah, your examples work in cases where p = n (I just updated my question with a general formula that works "partially", btw) but what if I have duplicated elements and p < n-1? Thanks $\endgroup$ – danicotra Nov 2 '19 at 14:18
0
$\begingroup$

I will try to give an answer, altough the formula is not as nice, as I would like it to be, but I have no idea, how to simplify it further. Also yesterday I made an attempt for the formula. There the final "correction" was wrong, since it is not so trivial as I thought it will be.

Hopefully the correct answer: Let $K_i$ be, what you denoted by $Oi$ (in your second interpretation, meaning, that $K_i$ is always greater than zero).

In a first step fix values of $k_i$ such, that $0\le k_i \le K_i$ and $\sum_{i=1}^s k_i=p$.

How many permutations exist, such that symbol 1 appears $k_1$ times, symbol 2 appears $k_2$ times and so on. The answer is $p!$.

We don't want all $p!$ permutations, but want to correct for the fact, that symbols may appear more than once in the sequence.

This results in $\frac{p!}{k_1!\cdots k_s!}$ sequences.

Now we want to add up these sequences

\begin{equation} \sum_{k_1=0}^{K_1}\cdots\sum_{k_s=0}^{K_s}\mathbb{1}_{p}(k_1+\cdots+k_s)\frac{p!}{k_1!\cdots k_s!}, \end{equation}

where $\mathbb{1}_{p}(k_1+\cdots+k_s) $ is the indicator function, that is 1, if the argument is equal to $p$ and else zero.

Hope this is helpful

Edit: Add rudimentary R code, with the example "mississippi" hardcoded. Corresponds with the numbers of recursive solution of whuber

K1 <- 1
K2 <- 4
K3 <- 4
K4 <- 2

p <- 10

iter <- 0
iter2 <- 0
res <- 0
tic <- Sys.time()
for(k1 in 0:K1) {
  for(k2 in 0:K2) {
    for(k3 in 0:K3) {
      for(k4 in 0:K4) {
        iter <- iter + 1
        if (k1 + k2 + k3 + k4 == p) {
          iter2 <- iter2 + 1
          res <- res + factorial(p)/(factorial(k1)*factorial(k2)*factorial(k3)*factorial(k4))
          break
        }
        else if (k1 + k2 + k3 >= p) break
      }
    }
  }
}
toc <- Sys.time()
(toc - tic)
res

Wrong answer:

The number of all possible permutations of $n$ elements is $n!$.

But you are only interested in the first $p$ positions of these permutations, so for each sequence of the first $p$ elements, you have $(n-p)!$ irrelevant duplicates, therefore you correct for this and you end up with $\frac{n!}{(n-p)!}$ possibilities.

Still you count irrelevant duplicates, due to the duplication of letters. You have to correct for that.

Let me define a new notation $k_i$ is what you denoted as 0i (with your latter interpretation, that means k_i is never zero).

The final formula than is: $\frac{n!}{(n-p)!k_1!\cdots k_s!}$.

$\endgroup$
3
  • $\begingroup$ Your formula doesn't look like it always yields an integer, as it must. For instance, take $s=1,$ $k_s=n,$ and $p=1.$ $\endgroup$ – whuber Nov 1 '19 at 17:48
  • $\begingroup$ Something is not correct, you are right. I will check this, thanks for your comment, $\endgroup$ – ghlavin Nov 1 '19 at 18:05
  • $\begingroup$ Thank you for the efforts in helping here and for your answer, I think you got some good point in it, going the right way towards the solution and so I think you don't deserve a negative score, have my upvote! $\endgroup$ – danicotra Nov 5 '19 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.