4
$\begingroup$

I was pondering over a closed formula for the number of arrangements of elements ('digits') $1,2,\dots,n$ into a string of $n+r$ elements, such that all digits are present at least once. So $r$ is the number of non-unique occurrences. If $r=0$ we get permutations, which are $n!$ in number. If $r=1$, we get $n$ choices for a repeated digit, then $n+1\choose 2$ choices to place two non-unique digits, and then $(n-1)!$ choices for the remaining unique digits, totaling in $n {n+1\choose 2} (n-1)!={n+1\choose 2} n!$ arrangements. However, when $r$ grows we have many shapes for repeated digits, corresponding to partitions of $r$, and the formulas seem intimidating.

Another way to describe this class of arrangements, is to call them permutations with unspecified repetitions, i.e. we have all digits present, the order matters, but we are not given which digits repeat. The strings of digits having these properties are sometimes called 'pandigital numbers' (except that they don't allow $0$ in the first position).

Question: is there a nice closed formula for the number of such class of arrangements?

UPDATE: User "Especially Lime" has provided a nice answer using inclusion-exclusion principle (and I accepted his answer). It turned out that his formula simplifies to $$ n! S(n+r,n) $$ where $S(n,m)$ is the Stirling number of the second kind, measuring the number of ways to partition an $n$-element set into $m$ nonempty subsets. Now it is obvious how to obtain this number from the very beginning: the shapes describing which positions among places $1,2,\dots,n+r$ are unique and which repeat, define a partition of the $n+r$-element set into $n$ nonempty subsets. Acting by $n!$ permutations by renumbering labels on parts yields the result.

$\endgroup$
4
$\begingroup$

I think the best you can do is the inclusion-exclusion formula. There are $n^{n+r}$ total sequences. For each digit $k$ there are $(n-1)^{n+r}$ sequences which don't contain $k$, so subtract those off (that is, subtract $\binom n1(n-1)^{n+r}$, since there are $\binom n1$ choices of $k$). Unfortunately we've now subtracted off the sequences that don't contain $k_1$ or $k_2$ twice, so we need to add those on again. Continuing in this manner we get $$\sum_{a=0}^{n-1}(-1)^a\binom na(n-a)^{n+r},$$ where the term for $a$ counts all the sequences missing some particular set of $a$ digits, and multiplies by the number of sets of $a$ digits.

$\endgroup$
  • $\begingroup$ This appears to absolutely correct and follows along the lines of what I first thought, but then for some reason I went down the path given in my answer. $\endgroup$ – String Aug 14 '17 at 7:42
  • $\begingroup$ Great! This formula simplifies to a $$ n! S(n+r,n) $$ where $S(n,m)$ is the Stirling number of the second kind, measuring the number of ways to partition an $n$-element set into $m$ nonempty subsets. Now it is obvious how to obtain this number from the very beginning: the shapes of which positions are unique, and which repeat define a partition of the $n+r$-element set into $n$ nonempty subsets. Acting by $n!$ permutations by renumbering labels on parts yields the result. $\endgroup$ – mathreader Aug 14 '17 at 8:05
2
$\begingroup$

DISCLAIMER: This post provides a less efficient answer than the other post. I will leave it here if it is of interest to anyone. Otherwise I might delete it if suggested.


Let $f(m,n)$ denote the number of strings of length $m\geq n$ that can be formed using a list of $n$ digits so that each digit occurs at least once. Then we must have $$ \binom n1f(m,1)+\binom n2f(m,2)+...+\binom n{n-1}f(m,n-1)+f(m,n)=n^m $$ and then $$ f(m,1)=1 $$ so that $$ \begin{aligned} f(m,2)&=2^m-\binom21f(m,1)\\ &=2^m-2 \end{aligned} $$ and furthermore $$ \begin{aligned} f(m,3)&=3^m-\binom 32f(m,2)-\binom31f(m,1)\\ &=3^m-3(2^m-2)-3 \end{aligned} $$ and so on. It does not seem to get prettier as $n$ grows, but perhaps some pattern will emerge and someone may be able to bring it on a more compact form.

$\endgroup$
  • 1
    $\begingroup$ (+1) This isn't really different than the other answers. What you have here is a slightly different derivation for the Stirling Numbers of the second kind $f(m,n)=n!S(m,n)$. If you follow through with your examples $f(m,4)$, $f(m,5)$ etc. expanding fully each time, you will get the same alternating sum as the other answer. $\endgroup$ – N. Shales Aug 14 '17 at 14:57

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.