# Counting the number of ways one could choose $x_{1},x_{2}, \cdots x_{n}$ such that..

My question is related to the following question. Finding the number of integers $(x_1,...,x_k)$ such that $1\leq x_1<x_2<\cdots<x_k\leq n$

Say, in this context, we need to choose stictrly positive integers $x_{1},x_{2}, \cdots x_{n}$ such that $1 \leq x_{1} <x_{2}<x_{3} \cdots <x_{n} \leq N$. The link above says that there are ${ N \choose n}$ ways of doing this. Now, assume that I fix $x_{j}$ for some $1 \leq j \leq n$. In how many ways can this be done?

• That depends on what $x_j$ is fixed to be. Regardless, you break the problem into two., finding the number of solutions to $(x_1,x_2,\dots,x_{j-1})$ such that $1\leq x_1<x_2<\dots<x_{j-1}\leq x_j-1$ for whatever $x_j-1$ happens to be fixed to, and multiply by the number of solutions to $(x_{j+1},x_{j+2},\dots,x_k)$ such that $x_j+1\leq x_{j+1}<x_{j+2}<\dots<x_k\leq n$. It is of course possible that the answer to one or both of those sub-problems is zero., e.g. with $k=5, n=10, j=2, x_j=9$ – JMoravitz Sep 18 '16 at 19:39

If you fix your $x_j$, then the problem becomes: find $x_1,\ldots,x_{j-1}$ in $[\![ 1,x_j-1]\!]$ and $x_{j+1},\ldots,x_n$ in $[\![ x_j+1,\ldots,N ]\!]$. The answer should be ${x_j-1 \choose j-1 }{N-x_j \choose n-j}$.
Note that if $j-1>x_j-1$ or $n-j>N-x_j$ then the binomial coefficients become zero. So this number is correct even in these situations.