[Solved]: Permuting natural numbers

Problem Detail: 

We have two integers $z, k$

We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, \ldots z$.

Now we have to find total number of permutations of this sequence such that the sum of any two adjacent numbers is $ \le k$

( $z \leq 10^6$, $\;\;z < k < 2*z$ )

Here is what I have been able to think untill now. If k=2*z-1, the answer is z!

Now if we reduce the value of k to 2*z-2, then we take the highest pair as a group and permute with rest of the elements, we subtract this value from the previous case of k=2*z-1

i.e. dp(z,k)= z! for k=2*z-1. and dp(z,k-1)=dp(z,k)-(z-1)!*2 for k=2*z-2.

I want to know if I am going in the right direction. Any help on the closed form would be good.

Asked By : Alice

Answered By : Yuval Filmus

Let $D(z,k,l)$ be the number of permutations $p_1,\ldots,p_z$ of $1,\ldots,z$ in which the condition $p_i + p_{i+1} \leq k$ is violated exactly $l$ times. Then $D(z,k,l)$ is given by the following recurrence relation, which is valid whenever $z \geq 2$ and $z+1 \leq k \leq 2z-1$: $$ D(z,k,l) = \begin{cases} (z-l) D(z-1,z,z-2-l) + (l+1) D(z-1,z,z-3-l), & k = z+1, \\ (z-l) D(z-1,k-2,l) + (l+1) D(z-1,k-2,l+1), & k \neq z+1. \end{cases} $$ I leave the proof of correctness to you.

^{(Here is a hint for the first case: show that $D(z,z+1,l) = D(z,z,z-1-l)$ and that $D(z,z,l) = (z-l) D(z-1, z, l-2) + (l+1) D(z-1, z, l-1)$.)}

The following Python program implements this recurrence:

def D(z, k, l):     if z < 2 or k < z+1 or k >= 2*z:         raise "Error"     if z == 2:         return 2 * int(l == 0)     if k == z+1:         return (z-l) * D(z-1, z, z-2-l) + (l+1) * D(z-1, z, z-3-l)     return (z-l) * D(z-1, k-2, l) + (l+1) * D(z-1, k-2, l+1) 

A more efficient implementation will use dynamic programming, I leave that also to you. One thing to notice is that case II preserves the quantity $2z-k$ while case I always has $k = z+1$, so the algorithm is quadratic rather than cubic.

For concreteness, here is a Python implementation of the dynamic programming method:

def DP(z, k):     if not (z >= 2 and z+1 <= k <= 2*z-1):         raise "Error"     z_crit = 2*z-k+1     L = [2, 0]     for w in range(3, z_crit+1):         L = [(w-l) * L[w-2-l] + (l+1) * L[w-3-l] for l in range(w-2)] + [2 * L[0], 0]     for w in range(z_crit+1, z+1):         L = [(w-l) * L[l] + (l+1) * L[l+1] for l in range(w-2)] + [2 * L[w-2], 0]     return L[0] 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12522

 Ask a Question

 Download Related Notes/Documents