3
$\begingroup$

Suppose you have a $k.n \times 2$ matrix. You have to fill up the numbers $1,2,3, \cdots, n$ as entries in such a way that in each column it is non-decreasing, in each row it is strictly increasing and each number should appear exactly $2k$ times. How many ways one can fill up the matrix ?

$\endgroup$
0
0
$\begingroup$

There are no ways to fill out a matrix with these constraints. Think about where the 1's in the first column must go. They must be first, because they cannot come after any other number. So the first k entries in the first column are 1's. What can go to the right of those? It must be a 2 or larger. But, where will the one's go in the second column? Anywhere you put them will remove the non-decreasing requirement on the second column. So it cannot be done.

$\endgroup$
1
  • $\begingroup$ No, it is possible. For example take $k=1$ and $n=5$. Then the rows of the matrix are $(1,2),(1,2),(3,4),(3,5),(4,5)$. $\endgroup$ – Harry Feb 11 '15 at 14:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.