|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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.
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,fini
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
