A352857 a(n) is the number of permutations p of {1, 2, ..., n} such that for any k in 1..n, k and p(k) share a common 1-bit.

1, 1, 1, 3, 3, 11, 61, 601, 601, 2881, 20867, 286065, 2821431, 45564697, 775615705, 16612433139, 16612433139, 116158938203, 1150638257617, 23090252128971, 299243344044281, 6870621769276771, 164016991433619495, 5064921427930587339, 86249855741531767869

Offset

0,4

Links

Table of n, a(n) for n=0..24.

Example

For n = 5:
- we have the following permutations (shown in decimal and in binary):
  p\k  1  2  3  4  5  |    1  10   11  100  101
  --- ----------------+------------------------
  p1   5  3  2  4  1  |  101  11   10  100    1
  p2   5  2  3  4  1  |  101  10   11  100    1
  p3   3  2  5  4  1  |   11  10  101  100    1
  p4   5  2  1  4  3  |  101  10    1  100   11
  p5   1  2  5  4  3  |    1  10  101  100   11
  p6   3  2  1  5  4  |   11  10    1  101  100
  p7   1  3  2  5  4  |    1  11   10  101  100
  p8   1  2  3  5  4  |    1  10   11  101  100
  p9   3  2  1  4  5  |   11  10    1  100  101
  p10  1  3  2  4  5  |    1  11   10  100  101
  p11  1  2  3  4  5  |    1  10   11  100  101
- so a(5) = 11.

Prog

(PARI) a(n) = matpermanent(matrix(n, n, i, j, bitand(i, j)>0))

Crossrefs

Cf. A351722.

Sequence in context: A334283 A365110 A350921 * A352582 A078225 A244247

Adjacent sequences: A352854 A352855 A352856 * A352858 A352859 A352860

Keyword

nonn,base

Author

Rémy Sigrist, Apr 06 2022

Status

approved