A236602 -id:A236602 - cp's OEIS frontend

A242519 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is 2^k for some k=0,1,2,...

0, 1, 1, 1, 4, 8, 14, 32, 142, 426, 1204, 3747, 9374, 26306, 77700, 219877, 1169656, 4736264, 17360564, 69631372, 242754286, 891384309, 3412857926, 12836957200, 42721475348, 152125749587, 549831594988

Offset: 1

Stanislav Sykora, May 27 2014

a(n)=NPC(n;S;P) is the count of all neighbor-property cycles for a specific set S of n elements and a specific pair-property P. Evaluating this sequence for n>=3 is equivalent to counting Hamiltonian cycles in a pair-property graph with n vertices and is often quite hard. For more details, see the link.

			The four such cycles of length 5 are:
C_1={1,2,3,4,5}, C_2={1,2,4,3,5}, C_3={1,2,4,5,3}, C_4={1,3,2,4,5}.
The first and the last of the 426 such cycles of length 10 are:
C_1={1,2,3,4,5,6,7,8,10,9}, C_426={1,5,7,8,6,4,3,2,10,9}.

Hiroaki Yamanouchi, Table of n, a(n) for n = 1..27 (first 21 terms from Stanislav Sykora)
S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.

Cf. A001710, A236602, A242520, A242521, A242522, A242523, A242524, A242525, A242526, A242527, A242528, A242529, A242530, A242531, A242532, A242533, A242534.

A242519[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
lpf[x_] := Length[Select[Abs[Differences[x]], ! MemberQ[t, #] &]];
t = Table[2^k, {k, 0, 10}];
Join[{0, 1}, Table[A242519[n], {n, 3, 10}]]
(* OR, a less simple, but more efficient implementation. *)
A242519[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[MemberQ[t, Abs[First[perm] - Last[perm]]], ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[! MemberQ[t, Abs[Last[perm] - new]], Continue[]];
      A242519[n, Join[perm, {new}],
       Complement[Range[2, n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
t = Table[2^k, {k, 0, 10}];
Join[{0, 1}, Table[ct = 0; A242519[n, {1}, Range[2, n]]/2, {n, 3, 12}]] (* Robert Price, Oct 22 2018 *)

For any S and any P, and for n>=3, NPC(n;S;P)<=A001710(n-1).

a(22)-a(27) from Hiroaki Yamanouchi, Aug 29 2014

A242530 Number of cyclic arrangements of S={1,2,...,2n} such that the binary expansions of any two neighbors differ by one bit.

Original entry on oeis.org

0, 0, 1, 0, 2, 8, 0, 0, 224, 754, 0, 26256, 0, 0, 22472304, 0, 90654576, 277251016, 0, 7852128780

Offset: 1

Stanislav Sykora, May 30 2014

Here, a(n)=NPC(2n;S;P) is the count of all neighbor-property cycles for a specific set S of 2n elements and a pair-property P. For more details, see the link and A242519.

In this case the property P is the Gray condition. The choice of the set S is important; when it is replaced by {0,1,2,...,2n-1}, the sequence changes completely and becomes A236602.

			The two cycles for n=5 (cycle length 10) are:
C_1={1,3,7,5,4,6,2,10,8,9}, C_2={1,5,4,6,7,3,2,10,8,9}.

S. Sykora, On Neighbor-Property Cycles, Stan's Library, Volume V, 2014.

Cf. A236602, A242519, A242520, A242521, A242522, A242523, A242524, A242525, A242526, A242527, A242528, A242529, A242531, A242532, A242533, A242534.

A242530[n_] := Count[Map[lpf, Map[j1f, Permutations[Range[2, 2 n]]]], 0]/2;
j1f[x_] := Join[{1}, x, {1}];
btf[x_] := Module[{i},
   Table[DigitCount[BitXor[x[[i]], x[[i + 1]]], 2, 1], {i,
     Length[x] - 1}]];
lpf[x_] := Length[Select[btf[x], # != 1 &]];
Table[A242530[n], {n, 1, 5}]
 (* OR, a less simple, but more efficient implementation. *)
A242530[n_, perm_, remain_] := Module[{opt, lr, i, new},
   If[remain == {},
     If[DigitCount[BitXor[First[perm], Last[perm]], 2, 1] == 1, ct++];
     Return[ct],
     opt = remain; lr = Length[remain];
     For[i = 1, i <= lr, i++,
      new = First[opt]; opt = Rest[opt];
      If[DigitCount[BitXor[Last[perm], new], 2, 1] != 1, Continue[]];
      A242530[n, Join[perm, {new}],
       Complement[Range[2, 2 n], perm, {new}]];
      ];
     Return[ct];
     ];
   ];
Table[ct = 0; A242530[n, {1}, Range[2, 2 n]]/2, {n, 1, 10}] (* Robert Price, Oct 25 2018 *)

a(16)-a(20) from Fausto A. C. Cariboni, May 10 2017, May 15 2017

A066037 Number of (undirected) Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.

Original entry on oeis.org

1, 1, 6, 1344, 906545760, 35838213722570883870720

Offset: 1

John Tromp, Dec 12 2001

This is the number of ways of making a list of the 2^n nodes of the n-cube, with a distinguished starting position and a direction, such that each node is adjacent to the previous one and the last node is adjacent to the first; and then dividing the total by 2^(n+1) because the starting node and the direction do not really matter.

The number is a multiple of n!/2 since any directed cycle starting from 0^n induces a permutation on the n bits, namely the order in which they first get set to 1.

			The 2-cube has a single cycle consisting of all 4 edges.

Michel Deza and Roman Shklyar, Enumeration of Hamiltonian Cycles in 6-cube, arXiv:1003.4391 [cs.DM], 2010. [There may be errors - see Haanpaa and Ostergard, 2012]
R. J. Douglas, Bounds on the number of Hamiltonian circuits in the n-cube, Discrete Mathematics, 17 (1977), 143-146.
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
Harary, Hayes, and Wu, A survey of the theory of hypercube graphs, Computers and Mathematics with Applications, 15(4), 1988, 277-289.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph

Equals A006069/2^(n+1) and A003042/2.
Cf. A006070, A091299, A003043, A091302.
Cf. A236602 (superset). - Stanislav Sykora, Feb 01 2014

Prepend[Table[Length[FindHamiltonianCycle[HypercubeGraph[n], All]], {n, 2, 4}], 1] (* Eric W. Weisstein, Apr 01 2017 *)

a(6) from Michel Deza, Mar 28 2010
a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012
Name clarified by Eric W. Weisstein, May 06 2019

A350784 Number of Gray code sequences of length 2n where numbers are between 0 and 2n-1.

Original entry on oeis.org

1, 2, 2, 12, 8, 44, 192, 2688, 1344, 6896, 24228, 316848, 812624, 9158880, 75652512, 1813091520, 725236608, 3568226496, 11152502816, 137997707616, 309878131724

Offset: 1

Thomas König, Jan 16 2022

The sequences are given with the first term as zero.

			The following Gray codes of length 10 contain only the numbers between 0 and 9:
  0, 2, 3, 7, 6, 4, 5, 1, 9, 8;
  0, 2, 6, 4, 5, 7, 3, 1, 9, 8;
  0, 4, 5, 7, 6, 2, 3, 1, 9, 8;
  0, 4, 6, 2, 3, 7, 5, 1, 9, 8;
  0, 8, 9, 1, 3, 2, 6, 7, 5, 4;
  0, 8, 9, 1, 3, 7, 5, 4, 6, 2;
  0, 8, 9, 1, 5, 4, 6, 7, 3, 2;
  0, 8, 9, 1, 5, 7, 3, 2, 6, 4.
Therefore a(5) = 8.

Thomas König, Fortran program for calculating the sequence
Wikipedia, Gray code
Wikipedia, Hamming distance

Cf. A003042 (a subsequence), A003188, A236602, A290772.

Fortran
```
! See König link.
```

a(2^m) = A003042(m+1).

a(n) = 2 * A236602(n) for n >= 2. - Alois P. Heinz, Feb 01 2022

a(17)-a(18) (via A236602) from Alois P. Heinz, Feb 01 2022
a(19)-a(20) from Martin Ehrenstein, Feb 16 2022
a(21) from Martin Ehrenstein, Feb 21 2022

A236603 Lowest canonical Gray cycles of length 2n.

Original entry on oeis.org

0, 1, 0, 1, 3, 2, 0, 2, 3, 1, 5, 4, 0, 1, 3, 2, 6, 7, 5, 4, 0, 2, 3, 7, 6, 4, 5, 1, 9, 8, 0, 1, 3, 7, 5, 4, 6, 2, 10, 11, 9, 8, 0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 9, 11, 10, 8, 0, 1, 3, 2, 6, 4, 5, 7, 15, 11, 9, 13, 12, 14, 10, 8, 0, 2, 3, 7, 5, 4, 6, 14, 10, 8, 12, 13, 15, 11, 9, 1, 17, 16

Offset: 1

Stanislav Sykora, Feb 01 2014

See A236602 for definitions regarding canonical Gray sequences (CGC). The CGC's of a given length can be sorted 'lexically'; for example, the CGC {0 1 5 4 6 7 3 2} precedes {0 1 5 7 3 2 6 4}. This sequence is then the flattened triangular table of the terms of the lowest CGC for each even length L, where L = 2*.

Note: zero unequivocally marks the start of each CGC.

			L    CGC
2    0, 1
4    0, 1, 3, 2
6    0, 2, 3, 1, 5, 4
8    0, 1, 3, 2, 6, 7, 5, 4
10   0, 2, 3, 7, 6, 4, 5, 1, 9, 8

Martin Ehrenstein, Table of n, a(n) for n = 1..1056 (first 306 terms from Stanislav Sykora)
Martin Ehrenstein, Triangle for A236603 (first 17 rows from Stanislav Sykora)
Stanislav Sykora, On Canonical Gray Cycles, Stan's Library, Vol.V, January 2014, DOI: 10.3247/SL5Math14.001

Cf. A236602 (CGC counts).

cp's OEIS Frontend

A242519 Number of cyclic arrangements of S={1,2,...,n} such that the difference between any two neighbors is 2^k for some k=0,1,2,...

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A242530 Number of cyclic arrangements of S={1,2,...,2n} such that the binary expansions of any two neighbors differ by one bit.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A066037 Number of (undirected) Hamiltonian cycles in the binary n-cube, or the number of cyclic n-bit Gray codes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A350784 Number of Gray code sequences of length 2*n where numbers are between 0 and 2*n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Fortran

Formula

Extensions

A236603 Lowest canonical Gray cycles of length 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A350784 Number of Gray code sequences of length 2n where numbers are between 0 and 2n-1.