Number of ways to arrange pairs of integers with distance constraint

Question

Given a sequence 0,1,1,2,2,3,3,...,n,n, find the number of ways to arrange the elements in the sequence so that there's exactly one digit between the two 1's, two digits between the two 2's, three digits between the two 3's, so on and so forth, and there are exactly n digits between the two n's.

For n=2, a possible solution would be 12102. For n=5, a possible solution would be 53141352402.

I have calculated that when n=2, the answer is 2; when n=3, the answer is 6; when n=4, the answer is 10; and when n=5, the answer is 22. But when n=6, my raw permutation function looks over 13! values and takes over an hour to calculate on my computer. I cannot think of any combinatorial enumeration or dynamic programming methods for this either. The best I can manage at the moment is backtracking with symmetry.

So my question is, what is the fastest way to compute the answer to this question for a large n and what are the mathematical intuitions for this problem? For example, is there a nontrivial upper / lower bound for the computational complexity for this problem?

Thanks for the answers in advance.

I first came across this problem in a Chinese coder forum.

Answer 1

An observation (too long for comment) that may speed up your recursive backtracking (though probably not by an order of magnitude).

In an acceptable permutation, the first occurrence of $k$ in position $p$ forces $k$ in position $k+p+1$ and precludes continuing with $k(k-1)$ or $kx(k-2)$ or $kxx(k-3)$ and so on.

Since half the entries are forced by the first occurrences of each $k$ you should have to examine something like $(n/2)!$ permutations, not all $n!$.

Answer 2

Using the insight from @EthanBolker's answer, I wrote a quick script in Python which seems to work for the first several, which I compute are:

[1, 2, 6, 10, 22, 76, 364, 1876, 8316, 46768]

For larger values, I would probably need to try a more efficient approach, like using a generator instead of a list of all of the permutations like this script does.

import itertools

maxn = 10
counts = [None]*(maxn-1)
for i in range(1,maxn):
    print(f"\nFor {i}:")
    total = 0
    nums = list(range(i+1))
    
    # all permutations of the integers from 0 to i
    perms = list(itertools.permutations(nums))
    
    # try each permutation:
    for j in range(len(perms)):
        
        # create a list to contain the digits
        slots = [None]*(2*i+1)
        
        # go through the digits in that order
        for k in perms[j]:
            
            # see if there is an open entry
            try:
                n = slots.index(None)
            except ValueError:
                n = -1
                
            # if not, the list matches the pattern
            if n == -1:
                total += 1
                #print(slots)
                break
                
            # fill the first open entry with the next digit
            slots[n] = k
            
            # if the corresponding entry doesn't exist... break
            if n+k+1>=(2*i+1):
                break
                
            if k!=0:
                
                # if the corresponding entry is open... fill it also
                if slots[n+k+1] == None:
                    slots[n+k+1] = k
                
                # or is already full... break
                else:
                    break
                    
        # if the list is full, then it matches the pattern
        try:
            n = slots.index(None)
        except ValueError:
            n = -1
        if n == -1:
            total += 1
            #print(slots)
            
    # record the total matches for this value of i
    counts[i-1] = total
    print(f"\tTotal = {total}\n")
    
print(counts)

The print statements could be uncommented to if you wanted to see the strings that it computes as matching the pattern.