Lucky Number 13 Part 2

As Fabricio notes, only the second constraint need be considered, as the first follows naturally: $a_n \le n + 1 \le a_{n + 2}$ , and equality cannot hold on both sides. Therefore, such an arrangement is a permutation of the normal numerical order in which each number is either in its original position or has been swapped with its neighbor on either side. For example,

$(1, 2, 4, 3, 5, 7, 6, 9, 8, 11, 13, 12)$ .

More generally, the question then becomes: how many disjoint sets of pairs of consecutive numbers can be chosen from the set $\{1, 2, \dots, n\}$ ? These will be the pairs that are swapped to create an arrangement. (In our situation $n = 13$ , of course.) Denote this number by $P_n$ . By direct computation we have $P_1 = 1, P_2 = 2$ . For $n > 2$ , such a permutation either fixes $1$ or swaps it with $2$ . If $1$ is fixed, there are $P_{n - 1}$ possible arrangements for the remaining $n - 1$ numbers. If $1$ and $2$ are swapped, there are $P_{n - 2}$ possible arrangements for the remaining $n - 2$ numbers. This means

$P_n = P_{n - 1} + P_{n - 2}$ ,

i.e. this sequence is nothing more than our old friend the Fibonacci sequence! Specifically $P_n = F_{n + 1}$ . Therefore the solution for the given problem is $P_{13} = F_{14} = 377$ . $\quad \square$

Consider the second constraint only. We won't need the first, because it is implied by the second:

The maximum value $a_n$ can take, for any $n = 1,2,...,11$ , is $n+1=n+2-1$ , which, once taken, limits the possible values for $a_{n+2}$ to $n+2$ and $n+2+1$ , implying $a_{n+2}$ > $a_n$ .

Note that:

• There are two possible positions for the number 1. Also, if $a_2=1$ , then $a_1=2$ necessarily.

• There are two possible positions for 2 if $a_1=1$ , and one if $a_2=1$ .

In general, after the positions for the first $k$ numbers are picked, we have $k$ numbers distributed among the first $k+1$ spaces of the list, and two things may
happen:

• $a_k$ is not occupied, in which case, there is only one possibility for $k+1$ , as it has to be in $a_k$ otherwise $a_k$ will be empty (as all its possible values will be taken).
• $a_k$ is occupied, in which case, there are two possibilities for $k+1$ ( $a_{k+1}$ and $a_{k+2}$ ). That is, until we reach 13, in which case, there can be only one spot left.

How, then, can we find a closed expression for the number of possibilities with such a strange tree of ramifications? I don't know for certain, so I wrote a bit of code to count for me, which gave me 377. The code itself is not the prettiest, but hopefully it is understandable.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int possibilities=0;
int a[13];    
void count_possibilities(int item);

int main(){
    int i; // start by initializing the array
    for(i=0;i<13;i++) a[i]=-1;
    count_possibilities(1); // first recursive call
    printf("%d",possibilities); // prints result
}

void count_possibilities(int item){
   // there are two possibilities for number 1
    if(item == 1){
        a[0]=1;
        count_possibilities(2);
        a[0]=-1;
        a[1]=1;
        count_possibilities(2);
        a[1]=-1;
    }else{
        if(item == 13){
            possibilities++; // there is only one possibility for 13 if you got this far
        }else{
            if(a[item-2]==-1){ // if the position ak-1 is not occupied, then k needs to go to ak-1, 
                                        // otherwise ak-1 will remain empty 
                a[item-2]=item;
                count_possibilities(item+1);
                a[item-2]=-1;
            }else{ // testing the two possibilities that remain when ak-1 is taken
                a[item-1]=item;
                count_possibilities(item+1);
                a[item-1]=-1;
                a[item]=item;
                count_possibilities(item+1);
                a[item]=-1;
            }
        }       
    }
} 

Can you say Fibonacci?

As a CS grad student, I start every problem with the naive solution and optimize it to get efficient ones.

As a habit, I first thought about the solution in the following way :

Generate all possible permutations (13!) and check for the constraints whether they are satisfied or not and increment a counter every time it does.

As you can see,It is horrifyingly inefficient.

So, then I solved the Inspiration problem first, without taking help of any Intel chips. and reached the answer : 1716

Now all I had to do is generate all these (1716) possibilities and check for the constraints which could be done in O(1).

The following is the code which shall do (Output : all the valid arrangements followed by the count of it).

import itertools as it
A = list(it.combinations(range(1,14),7))
count=0
for a in A:
    i=1
    for aa in a:
        if(aa == (i-1) or aa == (i) or aa == (i+1)):
            i=i+2
        else:
            break
    if(i==15):
        count=count+1
        print (a)
print (count)

Consider the general case for m integers 1..m, with boundary conditions n=1...m-2 in the first and n=1...m in the second condition. Let f(m) be the number of such arrangements. if we fix $a_m=m$ , we observe that there are f(m-1) possibilities for the arrangement before it. The only other option is $a_m=m-1$ , implying that $a_{m-1}=m$ , so that there are f(m-2) possibilities for the arrangement before that. So f(m)=f(m-2)+f(m-1). Together with the starting condition f(1)=1, f(2)=2 it is the fibonacci sequence, so f(13)=377.