5
$\begingroup$

EDIT How can we modify the expression in the case where each object can occur once or twice, but not 0 times, such that the resulting permutation p has size N <= |p| <= 2N?

(I feel that this, too, must be in OEIS, but it is escaping me).

For this case, I have:

$$\sum_{i=0}^N{N!\over i!\,(N-i)!}\ {(i+2(N-i))!\over 2^{N-i}}\ .$$

Can someone verify? (or, is there an obvious search term in OEIS that I'm missing?)


I am working on a CS paper, and it would be very helpful to be able to determine the following, which essentially counts the unique ways to make an input for an algorithm.

Here is the simplest way I can explain it:

  • We have $N$ people
  • Each person can be
    1. not chosen
    2. chosen once
    3. chosen twice
  • Then we take all of the people who are chosen once or twice and order them in an ordered set.

The question is:

How many unique ordered sets $S$ (of any length $0\le|S|\le2N$) can we make as a function of $N$?

For example, suppose there are $4$ people named $\{1,2,3,4\}$

Suppose:

$1$ is chosen once

$2$ is not chosen

$3$ is chosen twice

$4$ is not chosen

Then one unique set might then be the ordered set $\{3,3,1\}$. Another is $\{3,1,3\}$.

It seems clear that there are $3^N$ unique unordered sets, as for each person we have 3 options (not chosen, chosen once, or chosen twice).

The part I find challenging is that a person can be chosen twice, and switching order with oneself in the ordered set does not lead to a different unique ordered set.

Can anyone suggest the solution? Instinct suggests that there might be a way to incorporate Stirling numbers of the First Kind to remove these permutation cycles from the total count.

$\endgroup$
4
$\begingroup$

We can select $i\geq0$ persons to be used once in ${N\choose i}$ ways, and then can select $j\geq0$ persons to be used twice in ${N-i\choose j}$ ways. Necessarily $i+j\leq N$.

Assume that the $i$, resp. $j$, persons have been selected. We then produce a clone of each of the $j$ persons and have before us $i+2j$ persons, $j$ of them clones. These $i+2j$ persons can be linearly arranged in $(i+2j)!$ ways, but we have to divide this number by $2^j$ since we cannot distinguish between a real person and its clone.

It follows that the total number of admissible arrangements comes to $$\sum_{i=0}^N\sum_{j=0}^{N-i}{N!\over i!\,j!\,(N-i-j)!}\ {(i+2j)!\over 2^j}\ .$$ Maybe this expression can be simplified somewhat.

$\endgroup$
  • $\begingroup$ Formula verified (+1). $\endgroup$ – Markus Scheuer Nov 5 '17 at 16:20
  • $\begingroup$ Thank you very much for this solution & clear explanation! $\endgroup$ – cataclysmic Nov 5 '17 at 22:32
2
$\begingroup$

Hint: The first few values of the formula \begin{align*} a_N=\sum_{i=0}^N\sum_{j=0}^{N-i}{N!\over i!\,j!\,(N-i-j)!}\ {(i+2j)!\over 2^j} \end{align*} stated in the answer of @ChristianBlatter are

$$\begin{array}{rr} N&a_N\\ \hline 0&1\\ 1&3\\ 2&19\\ 3&271\\ 4&7\,365\\ 5&326\,011\\ 6&21\,295\,783\\ 7&1\,924\,223\,799\\ 8&229\,714\,292\,041\\ 9&385\,007\,742\,568\,755\\ 10&6\,630\,796\,801\,779\,771\\ 11&1\,527\,863\,209\,528\,564\,063\\ 12&420\,814\,980\,652\,048\,751\,629\\ 13&136\,526\,522\,051\,229\,388\,285\,611\\ \vdots&\vdots \end{array}$$ They are stored as A003011 in OEIS giving the number of permutations of up to $n$ kinds of objects, where each kind of object can occur at most two times.

Since there is no simpler formula stated an essential simplification of the formula is not plausible.

$\endgroup$
  • $\begingroup$ I was unfamiliar with oeis.org prior to reading your post. This is very helpful. Thank you!! $\endgroup$ – cataclysmic Nov 5 '17 at 22:33
  • $\begingroup$ @cataclysmic: You're welcome! :-) $\endgroup$ – Markus Scheuer Nov 5 '17 at 22:33
  • $\begingroup$ One last question: If I understand the formula and the OEIS notes correctly, then it scales as a polynomial function of N. Is this correct? Thank you again for your help. $\endgroup$ – cataclysmic Nov 5 '17 at 22:55
  • $\begingroup$ @cataclysmic: The order is not polynomial $O(N^k)$ and even more than exponential $O(k^N)$ since according to an entry from Vaclav Kotesovec we have $a_N\sim \sqrt{\pi}2^{N+1}\color{blue}{N^{2N+\frac{1}{2}}}e^{-2N+1}$. $\endgroup$ – Markus Scheuer Nov 5 '17 at 23:14
  • 1
    $\begingroup$ Ahh -- I see this. I was looking at the polynomial function in the note directly above the one you reference, but I had not noticed the a(n-1), a(n-2), etc. terms on the tail of the longer terms (which means that I was staring at the recurrence relation for the sequence rather than a solution). It seemed to good to be true... Thanks again for your help. $\endgroup$ – cataclysmic Nov 7 '17 at 0:55

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.