2
$\begingroup$

Given two permutation of $1, \ldots, N$. Where 3<=N<=1000 Example

For $N=4$

First is $\begin{pmatrix}3& 1& 2& 4\end{pmatrix}$.

Second is $\begin{pmatrix}2& 4& 1& 3\end{pmatrix}$.

Find the number of possible permutations $X_1, \ldots, X_N$ of $1, \ldots, N$ such that if we write all three in $3\times N$ matrix, each column must have unique elements.

$\begin{pmatrix}3 & 1 & 2 & 4\\ 2 & 4 & 1 & 3\\ X_1 & X_2 & X_3 & X_4\end{pmatrix},$

here $X_1$ can't be 3 or 2, $X_2$ can't be 1 or 4, $X_3$ can't be 2 or 1, $X_4$ cant be 4 or 3,

Answer to above sample is 2 and possible permutation for third row is $\begin{pmatrix}1 & 3 & 4 & 2\end{pmatrix}$ and $\begin{pmatrix}4 & 2 & 3& 1\end{pmatrix}$.

Example 2

First is $\begin{pmatrix}2 & 4 & 1 & 3\end{pmatrix}$.

Second is $\begin{pmatrix}1 & 3 & 2 & 4\end{pmatrix}$.

Anwser is 4. Possible permutations for third row are $\begin{pmatrix}3&1&4&2\end{pmatrix}$, $\begin{pmatrix}3&2&4&1\end{pmatrix}$, $\begin{pmatrix}4&1&3&2\end{pmatrix}$ and $\begin{pmatrix}4&2&3&1\end{pmatrix}$.

$\endgroup$
  • 1
    $\begingroup$ What are you asking us? $\endgroup$ – Henry Oct 15 '13 at 14:24
  • $\begingroup$ number of possible permutation such of 1...N,such that when this permutation and the given two permutation are written in an 3*N matrix, then each cells in a column has unique and different value ,(for all column) $\endgroup$ – balli Oct 15 '13 at 14:25

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.