0

Given a number N what is the number of Permutations in a Space of size N, of these N values.

Example: N=2

$${P} = \{ (0,0,0), (0,0,1),(0,1,0),(1,0,0),(1,0,1),(1,1,0),(0,1,2),(1,0,2),(0,2,1),(1,2,0),(2,0,1),(2,1,0)\}$$

The restrictions to this are:

  1. All Values have to be in the range of $\{0 ,..., (N-1)\}$
  2. in a permutation with only $k$ unique values, these unique values have to be in the range $\{0 ,..., (k-1)\}$

basically, we exclude permutations like $(1,1,1)$, because they are the same as $(0,0,0)$, all equal values. we exclude $(0,0,2)$, because there exists an equivalent permutation $(0,0,1)$, with a lower maximum value.

One more way to describe this, is if you are given a set of N values, possibly distinct or not, and you only know the inequallities or equalities between the values in the set. Choose the lowest number $k$, so that the set contains only the values ranging from $0$ to $k$ and still fullfills all the inequalities and equalites. example: $$(a,b,c), a<b, a<c, b>c$$ would give you the set $(0,2,1)$.

The question is, how many sets/permutations are there, if you are given a space of size N (in terms of N).

For $N = 2$, it should be $3 = 2^2-1$

For $N = 3$, it should be $13 = 2^3-1+3!$

Control
  • 162
  • 1
    It sounds like you are describing the Bell numbers except you care to remember the label on each part in the partition rather than treating them as unlabeled (evidenced by (1,0,1) being treated as different than (0,1,0)). The same logic to generating those values should apply here, just rather just $\sum\limits_{k=1}^n{n\brace k}$ you also have a factorial so it is $\sum\limits_{k=1}^nk!{n\brace k}$ – JMoravitz Mar 09 '21 at 19:20
  • The sequence continues $3,13,75,541,4683,\dots$ See http://oeis.org/A000670 and Ordered Bell Numbers for more. – JMoravitz Mar 09 '21 at 19:24

0 Answers0