3
$\begingroup$

Let $n,k$ be positive integers. What is the number of sets of $k$ distinct ordered pairs $\{(a_1,b_1),\ldots,(a_k,b_k)\}$ such that $1\leq a_i,b_i\leq n$ are integers, and for no $i\neq j$ is it the case that $a_i<a_j$ but $b_i>b_j$?

Is there an exact formula? If not, what are some estimates?

Note: For example, $\{(1,1),(1,2)\}$ and $\{(1,2),(1,1)\}$ are considered to be the same, since we're dealing with sets.

$\endgroup$
  • $\begingroup$ $a_i \leq b_i$ is not required, is it? And just to be clear: Your restriction is: For all $i \neq j$ we have $a_i < a_j \Rightarrow b_i \leq b_j$, right? $\endgroup$ – GenericNickname Nov 14 '14 at 20:21
  • $\begingroup$ @GenericNickname Right (for both questions) $\endgroup$ – Dexter Nov 14 '14 at 20:30
  • $\begingroup$ One special case: for $k=2n-1$ the answer is $\binom{2n-2}{n-1}$, corresponding to the $\binom{2n-2}{n-1}$ paths from $(1,1)$ to $(n,n)$. And for $k\ge2n$ the answer is $0$, since then two of the sums $a_j+b_j$ (which are all between $2$ and $2n$) would have to be equal by the pigeonhole principle. $\endgroup$ – Greg Martin Nov 14 '14 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.