login
A351722
a(n) is the number of permutations p of {1, 2, ..., 2*n} such that for any k in 1..2*n, k and p(k) do not share a common 1-bit.
1
1, 1, 1, 1, 1, 9, 9, 1, 1, 121, 1089, 729, 729, 1521, 169, 1, 1, 2601, 314721, 1771561, 15944049
OFFSET
0,6
COMMENTS
By the pigeonhole principle, and simply considering parities of k and p(k), there are no such permutation of {1, 2, ..., 2*n+1}.
FORMULA
a(n) = 1 for any n in A000225 (the only solution is k -> 2*n+1-k).
a(2^k) = 1 for any k >= 0 (the only solution is row 2^k in A253515).
EXAMPLE
For n = 5:
- we have the following 9 permutations (shown in decimal and in binary):
p\k 1 2 3 4 5 6 7 8 9 10 | 1 10 11 100 101 110 111 1000 1001 1010
--- -----------------------+------------------------------------------------
p1 6 5 4 3 10 9 8 7 2 1 | 110 101 100 11 1010 1001 1000 111 10 1
p2 10 5 4 3 2 9 8 7 6 1 | 1010 101 100 11 10 1001 1000 111 110 1
p3 2 5 4 3 10 9 8 7 6 1 | 10 101 100 11 1010 1001 1000 111 110 1
p4 6 9 4 3 10 1 8 7 2 5 | 110 1001 100 11 1010 1 1000 111 10 101
p5 6 1 4 3 10 9 8 7 2 5 | 110 1 100 11 1010 1001 1000 111 10 101
p6 10 9 4 3 2 1 8 7 6 5 | 1010 1001 100 11 10 1 1000 111 110 101
p7 2 9 4 3 10 1 8 7 6 5 | 10 1001 100 11 1010 1 1000 111 110 101
p8 10 1 4 3 2 9 8 7 6 5 | 1010 1 100 11 10 1001 1000 111 110 101
p9 2 1 4 3 10 9 8 7 6 5 | 10 1 100 11 1010 1001 1000 111 110 101
- so a(5) = 9.
PROG
(PARI) a(n) = matpermanent(matrix(2*n, 2*n, i, j, bitand(i, j)==0))
CROSSREFS
KEYWORD
nonn,base,more
AUTHOR
Rémy Sigrist, Apr 06 2022
STATUS
approved