Let $A=\{1,2,3,...,n\}$ .
For a permutation $P=(P(1),P(2),P(3)....,P(n))$ of the elements of $A$ , let $P(1)$ denote the first element of $P$ . Find the number of all such permutations $P$ so that for all $i,j \in A$
If $i\lt j \lt P(1) $, then $j$ appears before $i$ in $P$
If $P(1) \lt i \lt j$ then $i$ appears before $j$ in $P$
I know that this is previuosly asked question (Permutation such that • if i < j < P(1), then j appears before i in P; and • if P(1) < i < j,then i appears before j in P) but unfortunately I am not quite satisfied with the answers especially with the numeric value and particularly the approach. . So here's my thinking .
My Thinking :
Clearly , the elements above $P(1)$ are in ascending order and the elements below it are in descending order where I am assuming $1\lt P(1) \lt n$
To gain an understanding of how this works.
Let $n=10$ . Then $A=\{1,2,3,..,10\}$
If $P(1)=7$ , then the relative arrangement between the elements of the set $\{1,2,3,4,5,6\}$ is $(6 ,5, 4 ,3, 2, 1)$ and that of the elements of the set $\{8,9,10\}$ is $(8,9,10)$
Now I need to find all the permutations that can be formed by merging the above two arrangements and then adjoin $P(1)=7$ at the beginning to get a full permutation of $A$ which satisfies the conditions.
Ok , that means I have to think what numbers from the set $\{ 8,9 ,10\}$ can be placed in the following blanks and in how many ways
_ $6 $_ $5 $_ $4$_ $3$ _ $2$ _ $1$_
where one blank can contain more than one number from the above set. Note that I am only worried about the distinct distributions that can be made in the blank places and not on the orders in which they are distributed since there is only way they can be in ascending order.
This leads me to conclude that the required no. of such distributions and hence the required no. of such permutations is given by the number of non-negative integer solutions to the equation
$x_1+x_2+x_3+x_4+x_5+x_6+x_7=3 \quad (*) $ where each $0\le x_i \le 3, i=1(1) 7$
So my answer should be the coefficient of $x^3$ in the expansion of $(1+x+x^2+x^3)^7$
Am I on the right track ??
Now, thinking to generalise this, shouldn't the answer be
The requiered no. of such permutations is the coefficient of $x^{n-k}$ in the expansion of
$(1+x+x^2+...+x^{n-k})^k$ where $P(1)=k$ .
Need your guidance. Please help.
Thanks a lot for your time.
$A=\{1,2,3,...,n\}$. say, $P(1) = k \,$ where $1 \le k \le n$.
Now you have set $A(1)$ with $(k-1)$ elements sorted in one order and set $A(2)$ with $(n-k)$ elements sorted in another, totaling to $(n-1)$ elements. The internal order of $A(1)$ and $A(2)$ is fixed. You can choose $(k-1)$ positions from a total of $(n-1)$ positions in $^{(n-1)}C_{(k-1)}$ ways. Once you choose positions of $A(1)$, their order is fixed and the positions of $A(2)$ is also fixed and so is their order. So the problem just reduces to choosing $(k-1)$ or $(n-k)$ positions from total of $(n-1)$ positions.
So, the answer is simply $^{(n-1)}C_{(k-1)} \,$ where $k = P(1), 1 \le k \le n$.