# Permuting natural numbers

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.

• What is your motivation? What have you tried? – Yuval Filmus Jun 8 '13 at 5:47
• @YuvalFilmus I have added the limits for z,k there must be some closed form for the above conditions, since brute forcing them seems unfeasable. I am guessing at a dp solution. I tried writing down the values for small values of z,k and trying to guess a pattern, but no good till now. – Alice Jun 8 '13 at 9:03
• @YuvalFilmus I have added my approach. – Alice Jun 8 '13 at 21:23
• Here is the user's motivation: codechef.com/JUNE13/problems/PERMUTE. – Yuval Filmus Jun 15 '13 at 19:50

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]
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

• Any hints for the dynamic programming structure? This recurrance looks more complex than i imagined it to be. If I calculate this value modulus a prime number. Would that help? – Alice Jun 9 '13 at 0:49
• If you calculate the actual values for $z \approx 10^6$ then the numbers would be gigantic, so this is only really possible if you compute it modulo something. – Yuval Filmus Jun 9 '13 at 1:35
• yes and how to proceed with dynamic programming? Can this be done using matrices for multiplication? Like a transformation matrix T^x * initial state? – Alice Jun 9 '13 at 1:38
• As for implementation using DP, I added a few comments. If you're lazy you can always use memoization, which is dynamic programming without planning ahead. (Memoization: store all values of $D(z,k,l)$ you compute in a table, and don't recompute a value which is already in the table.) – Yuval Filmus Jun 9 '13 at 1:38
• The DP implementation calculates $D(z,k,\cdot)$ from $D(z-1,k-2,\cdot)$ (if $k > z+1$) and $D(z,z+1,\cdot)$ from $D(z-1,z,\cdot)$, so you can implement it using matrix multiplication. I'll leave you the details. You only need linear space. – Yuval Filmus Jun 9 '13 at 1:42