Tough Combinatorics Question (possibly related to Stirling numbers)

Question

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.

Answer 1

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.

Answer 2

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.