Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #17 Apr 15 2018 14:15:42
%S 24,18,18,12,18,12,12,6,18,14,12,8,14,10,8,4,18,14,14,10,12,8,8,4,12,
%T 10,8,6,8,6,4,2,18,14,14,10,12,8,8,4,14,11,10,7,10,7,6,3,12,10,10,8,6,
%U 4,4,2,8,7,6,5,4,3,2,1,18,12,14,8,14,8,10,4,12,8,8,4
%N a(n) is the number of permutations of {1, 2, 3, 4} that avoid the list of pairs encrypted in n (see comments below).
%C This sequence contains 2^(2 * 6) = 4096 terms; a(n) for n = 0..4095. We consider the digits of the binary expansion of n, i. e. the bits from the first (least significant) bit to the twelfth (most significant) bit. We define a correspondence between the bit number 1..16 and the pair or numbers 1..4: (1, [1, 2]), (2, [1, 3]), (3, [1, 4]), (4, [2, 3]), (5, [2, 4]), (6, [3, 4]), (7, [2, 1]), (8, [3, 1]), (9, [4, 1]), (10, [3, 2]), (11, [4, 2]), (12, [4, 3]). Then consider a permutation of {1, 2, 3, 4}; if a bit of n is 1 then the corresponding pair is not allowed in the permutation. The number of permutations that satisfy this restriction is a(n).
%C Distinct terms in this sequence are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 18 and 24 which occur 772, 936, 672, 328, 336, 288, 272, 120, 129, 48, 84, 24, 38, 36, 12 and 1 times respectively.
%C a(65 * n) lists number of permutations such that pairs avoided in permutations numbered by a(n) aren't adjacent to each other.
%e The binary expansion of 195 is 11000011. The 1st, 2nd, 7th, and 8th bits are 1, so we avoid the corresponding pairs, which are [1, 2], [1, 3], [2, 1], and [3, 1] respectively. There are 4 permutations that avoid these completely; they are [1, 4, 2, 3], [1, 4, 3, 2], [2, 3, 4, 1] and [3, 2, 4, 1]. Therefore, a(195) = 4.
%e Note that 195 is a multiple of 65 and so a(195) gives the elements from pairs corresponding to a(195/65) = a(3), which are [1, 2] and [1, 3] aren't adjacent to each other.
%t With[{p = Permutations[Range@4]}, Table[Count[p, _?(AllTrue[Pick[{{4, 3}, {4, 2}, {3, 2}, {4, 1}, {3, 1}, {2, 1}, {3, 4}, {2, 4}, {2, 3}, {1, 4}, {1, 3}, {1, 2}}, PadLeft[IntegerDigits[n, 2], 12], 1], Function[k, SequenceCount[#, k] == 0]] &)], {n, 0, 75}]] (* _Michael De Vlieger_, Oct 30 2017 *)
%o (PARI) a(n) = {my(b = binary(n), pairs, avoid = List(), perm); b = concat(vector(12-#b), b); pairs = [[4,3], [4,2], [3,2], [4,1], [3,1], [2,1], [3, 4], [2, 4], [2, 3], [1, 4], [1, 3], [1, 2]]; for(i=1, 12, if(b[i] == 1, listput(avoid, pairs[i]))); sum(i=0,23,avoids(numtoperm(4, i), avoid))}
%o avoids(perm, avoid) = {for(i=1, #perm - 1, for(j=1, #avoid, if(perm[i] == avoid[j][1], if(perm[i+1] == avoid[j][2], return(0))))); 1}
%Y Cf. A163820.
%K nonn,fini
%O 0,1
%A _David A. Corneth_, Oct 24 2017