cp's OEIS Frontend

A293782 a(n) is the number of permutations of {1, 2, 3, 4} that avoid the list of pairs encrypted in n (see comments below).

%I A293782 #17 Apr 15 2018 14:15:42
%S A293782 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 A293782 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 A293782 4,4,2,8,7,6,5,4,3,2,1,18,12,14,8,14,8,10,4,12,8,8,4
%N A293782 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 A293782 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 A293782 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 A293782 a(65 * n) lists number of permutations such that pairs avoided in permutations numbered by a(n) aren't adjacent to each other.
%e A293782 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 A293782 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 A293782 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 A293782 (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 A293782 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 A293782 Cf. A163820.
%K A293782 nonn,fini
%O A293782 0,1
%A A293782 _David A. Corneth_, Oct 24 2017