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.

  • 2
    $\begingroup$ What is your motivation? What have you tried? $\endgroup$ Commented Jun 8, 2013 at 5:47
  • $\begingroup$ @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. $\endgroup$
    – Alice
    Commented Jun 8, 2013 at 9:03
  • $\begingroup$ @YuvalFilmus I have added my approach. $\endgroup$
    – Alice
    Commented Jun 8, 2013 at 21:23
  • $\begingroup$ Here is the user's motivation: codechef.com/JUNE13/problems/PERMUTE. $\endgroup$ Commented Jun 15, 2013 at 19:50

1 Answer 1


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]
  • $\begingroup$ 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? $\endgroup$
    – Alice
    Commented Jun 9, 2013 at 0:49
  • $\begingroup$ 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. $\endgroup$ Commented Jun 9, 2013 at 1:35
  • $\begingroup$ yes and how to proceed with dynamic programming? Can this be done using matrices for multiplication? Like a transformation matrix T^x * initial state? $\endgroup$
    – Alice
    Commented Jun 9, 2013 at 1:38
  • $\begingroup$ 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.) $\endgroup$ Commented Jun 9, 2013 at 1:38
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jun 9, 2013 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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