What is the number of permutations for given N numbers, such that the first part is non-decreasing?

Question

Let $A$ be a list of $n$ numbers in range $[1,100]$ (numbers can repeat). I'm looking for the number of permutations of $A$ which start with a non-decreasing part, where this part ends with the first instance of the highest number, call this "index $i$" (1 based)from the left. After $i$, the remaining permutation is an arbitrary arrangement.

Examples

• For $n=1$ and $A=\{9\}$, we have $1$ way only.

• For $n=2$ and $A=\{2,5\}$, we have $2!$ ways in total.

  • For $i=1$ we have $1$ way $(5,2)$ only.
  • For $i=2$ we have $1$ way $(2,5)$ only.

• If we were given , $A=\{5,5\}$, we have 2 ways totally:

  • For $i=1$ we have one way, namely $(5,5)$, where the first $5$ coincides with first occurrence of $5$ in $A$, and
  • For $i=2$ we have one way, namely $(5,5)$, where the second $5$ coincides with first occurrence of $5$ in $A$

• For $n=3$ and $A=\{1, 4, 3\}$, we have $3!$ ways in total.

  • For $i=1$, we have $2!$ permutations starting with $4$, namely $(4,3,1)$ and $(4,1,3)$.
  • For $i=2$ , $2!$ ways $(1,4,3)$ and $(3,4,1)$ in which $4$ is at $2$nd place.
  • For $i=3$ , $2!$ ways $(1,3,4)$ and $(3,1,4)$ ending with $4$.

To be exact : the number of permutations, without replacement, of given $n$ numbers such that the numbers up to $i$th place from left (say index) are in non-decreasing order, $i$-th place is occupied by first instance of largest number and rest can be random...

p.s. I cannot be more specific...

Answer 1

Consider a finite sequence $s$ of length $n$ on integers that range from 0 to 100. Since repetition of numbers is allowed, let's denote with $t^a$ the number of occurrences of the number $a$ within $s$. We also denote with $l$ the largest number within $s$ (I guess it won't always be 100).

Now, assume a given $i$, where $i\leq n$. We want to permute $s$ in a way, that

1. the first $i$ digits are in a non-descending order
2. the $i$-th digit is the first occurrence of the largest number available in $s$ and
3. the rest part of the permutation (from $i+1$ to $n$) is arbitrary.

Let's see conditions (1) and (2): If from $s$ we select $i$ numbers (repetition allowed) where one of them is always the first occurrence of $l$, then this is the same as first choosing the first occurrence of $l$ and then choosing in addition $i-1$ numbers from the sequence produced by $s$ after removing the first occurrence of $l$. The selection of the $i$ numbers will constitute the ordered part of the permutation.

There is only one way to choose the first occurrence of $l$ and there are $\binom{n-1}{i-1}$ ways to choose the next $i-1$ numbers. Now, put $t_1^a$ to be the number of occurrences of $a$ within the selection of the $i-1$ numbers and $t^a_2=t^a-t^a_1$ (the number of occurrences of $a$ that are not in the selection). Finally, let $S$ be the set (not multiset) produced by the union of $l$ and the selection of the $i-1$ numbers. Then, for each selection of $i-1$ numbers in $s$, there are $$\prod_{a\in S} t^a_1!$$ ways to order them in a non-descending manner. So, the first $i$ digits of the permutation can be constructed in $$\sum_{S\subseteq [1,100]~\text{and}~ |S|=i-1}\left[\binom{n-1}{i-1}\cdot\prod_{a\in S} t^a_1!\right]$$ ways. Note, the summation is not over $i$, but over all possible sets $S$. Actually, $S$ is a subset of $\{1,\ldots,100\}$ which always contains $l$ and has $i-1$ elements. Here $i$ is given and fixed.

From condition (3), for each selection of $i-1$ numbers in $s$, the rest of the permutation can be constructed in $$\left(\prod_{a\in S} t^a_2!\right)\cdot\left(\prod_{a\notin S} t^a!\right)$$ ways.

So totally, the number of permutations that satisfy the three properties is $$\sum_{S\subseteq [1,100]~\text{and}~ |S|=i-1}\left[\binom{n-1}{i-1}\cdot\left(\prod_{a\in S} t^a_1!\right)\cdot\left(\prod_{a\in S} t^a_2!\right)\cdot\left(\prod_{a\notin S} t^a!\right)\right]$$

Finally, if you want to compute this for all $i=1,\ldots,n$, you just sum the last expression over $i$. $$\sum_{i=1}^n\left(\sum_{S\subseteq [1,100]~\text{and}~ |S|=i-1}\left[\binom{n-1}{i-1}\cdot\left(\prod_{a\in S} t^a_1!\right)\cdot\left(\prod_{a\in S} t^a_2!\right)\cdot\left(\prod_{a\notin S} t^a!\right)\right]\right)$$

Answer 2

Let's say you have $t_i$ times integer $i$, with $i$ from $0$ to $9$. The number of permutations of the tuple $(a_1, \ldots, a_{t_1 + \cdots + t_9})$ with $0 \leq a_i \leq 9$, such that $a_i \leq a_j$ if $i < j$, is $$t_1!\cdots t_9!$$