login
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).
0
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, 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, 4, 4, 2, 8, 7, 6, 5, 4, 3, 2, 1, 18, 12, 14, 8, 14, 8, 10, 4, 12, 8, 8, 4
OFFSET
0,1
COMMENTS
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).
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.
a(65 * n) lists number of permutations such that pairs avoided in permutations numbered by a(n) aren't adjacent to each other.
EXAMPLE
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.
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.
MATHEMATICA
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 *)
PROG
(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))}
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}
CROSSREFS
Cf. A163820.
Sequence in context: A028696 A284874 A216841 * A153729 A357972 A357974
KEYWORD
nonn,fini
AUTHOR
David A. Corneth, Oct 24 2017
STATUS
approved