A003043 -id:A003043 - cp's OEIS frontend

A003042 Number of directed Hamiltonian cycles (or Gray codes) on n-cube.

Original entry on oeis.org

1, 2, 12, 2688, 1813091520, 71676427445141767741440

Offset: 1

N. J. A. Sloane

Finding a(6) is Problem 43 in the Knuth reference.

Martin Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.
Donald E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, (to appear), section 7.2.1.1.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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]
Harri Haanpaa and Patric R. J. Östergård, Counting Hamiltonian cycles in bipartite graphs, Math. Comp. 83 (2014), 979-995.
John Jungck, Genetic Codes as Codes: Towards a Theoretical Basis for Bioinformatics, International Symposium on Mathematical and Computational Biology (BIOMAT 2008), see p. 19.
Jerry Silverman, Virgil E. Vickers, and John L. Sampson, Statistical estimates of the n-bit Gray codes by restricted random generation of permutations of 1 to 2^n, IEEE Trans. Inform. Theory 29 (1983), no. 6, 894-901.
Vladimir Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
Vladimir Shevelev, Combinatorial minors of matrix functions and their applications
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hypercube Graph

Equals A006069 divided by 2^n.

Cf. A006070, A091299, A003043, A091302, A066037, A159344, A180026.

a(n) = 2 * A066037(n).

a(6) from Michel Deza, Mar 28 2010

a(6) corrected by Haanpaa and Östergård, 2012. - N. J. A. Sloane, Sep 06 2012

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

A091299 Number of (directed) Hamiltonian paths (or Gray codes) on the n-cube.

Original entry on oeis.org

2, 8, 144, 91392, 187499658240

Offset: 1

N. J. A. Sloane, Feb 20 2004

More precisely, 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. The final node may or may not be adjacent to the first.

			a(1) = 2: we have 1,2 or 2,1. a(2) = 8: label the nodes 1, 2, ..., 4. Then the 8 possibilities are 1,2,3,4; 1,3,4,2; 2,3,4,1; 2,1,4,3; etc.

M. Gardner, Knotted Doughnuts and Other Mathematical Entertainments. Freeman, NY, 1986, p. 24.

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hypercube Graph

Equals A006069 + A006070. Divide by 2^n to get A003043.

Cf. A003042, A066037, A091302, A284673.

# A function that calculates A091299[n] from Janez Brank.
def CountGray(n):
    def Recurse(unused, lastVal, nextSet):
        count = 0
        for changedBit in range(0, min(nextSet + 1, n)):
            newVal = lastVal ^ (1 << changedBit)
            mask = 1 << newVal
            if unused & mask:
                if unused == mask:
                    count += 1
                else:
                    count += Recurse(
                        unused & ~mask, newVal, max(nextSet, changedBit + 1)
                    )
        return count
    count = Recurse((1 << (1 << n)) - 2, 0, 0)
    for i in range(1, n + 1):
        count *= 2 * i
    return max(1, count)
[CountGray(n) for n in range(1, 4)]

a(5) from Janez Brank (janez.brank(AT)ijs.si), Mar 02 2005

A179926 Number of permutations of the divisors of n of the form d_1=n, d_2, d_3, ..., d_tau(n) such that d_(i+1)/d_i is a prime or 1/prime for all i.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 18, 1, 1, 2, 2, 2, 8, 1, 2, 2, 4, 1, 18, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 106, 1, 2, 3, 1, 2, 18, 1, 3, 2, 18, 1, 17, 1, 2, 3, 3, 2, 18, 1, 5, 1, 2, 1, 106, 2, 2, 2, 4, 1, 106, 2, 3, 2, 2, 2, 6, 1, 3, 3, 8, 1, 18, 1, 4, 18, 2, 1, 17, 1, 18, 2, 5, 1, 18, 2, 3, 3, 2, 2, 572

Offset: 1

Vladimir Shevelev, Aug 02 2010

nonn

In view of formulas given below, there are many common first terms with A001221. Note that, for n >= 1, a(n) is positive; it is function of exponents of prime power factorization of n only; moreover, it is invariant with respect to permutations of them.
An equivalent multiset formulation of the problem: for a given finite multiset A, we should, beginning with A, to get all submultisets of A, if, by every step, we remove or join 1 element. How many ways are there to do this?
Via Seqfan Discussion List (Aug 03 2010), Alois P. Heinz proved that every subsequence of the form a(p), a(p*q), a(p*q*r), ..., where p, q, r, ... are distinct primes, coincides with A003043. - Vladimir Shevelev, Aug 09 2010
The parity (odd or even) of bigomega(d_i) in a permutation of divisors of n alternates. - David A. Corneth, Nov 25 2017
Equivalently, the number of Hamiltonian paths in a graph with vertices corresponding to the divisors of n and edges connecting divisors that differ by a prime with the path starting on the vertex associated with 1. - Andrew Howroyd, Oct 26 2019

			a(12)=3:
[12, 6, 3, 1, 2, 4]
[12, 4, 2, 6, 3, 1]
[12, 4, 2, 1, 3, 6]
a(45)=3:
[45, 15, 5, 1, 3, 9]
[45, 9, 3, 15, 5, 1]
[45, 9, 3, 1, 5, 15]

Alois P. Heinz, Table of n, a(n) for n = 1..1259 (first 719 terms from David A. Corneth)
David A. Corneth, The permutations of divisors for a(60) ordered by their last element.
V. Shevelev, Combinatorial minors of matrix functions and their applications, arXiv:1105.3154 [math.CO], 2011-2014.
V. Shevelev, Combinatorial minors of matrix functions and their applications, Zesz. Nauk. PS., Mat. Stosow., Zeszyt 4, pp. 5-16. (2014).
Index entries for sequences computed from exponents in factorization of n

Cf. A000005, A001221, A180026, A003043, A003042. - Vladimir Shevelev, Aug 09 2010
See A173675 for another version.
Cf. A119842, A295785.

q:= (i, j)-> is(i/j, integer) and isprime(i/j):
b:= proc(s, l) option remember; `if`(s={}, 1, add(
     `if`(q(l, j) or q(j, l), b(s minus{j}, j), 0), j=s))
    end:
a:= n-> (s-> b(s minus {n}, n))(numtheory[divisors](n)):
seq(a(n), n=1..100);  # Alois P. Heinz, Nov 26 2017

q[i_, j_] := PrimeQ[i/j];
b[s_, l_] := b[s, l] = If[s == {}, 1, Sum[If[q[l, j] || q[j, l], b[s  ~Complement~ {j}, j], 0], {j, s}]];
a[n_] := Function[s, b[s ~Complement~ {n}, n]][Divisors[n]];
Array[a, 120] (* Jean-François Alcover, Dec 13 2017, after Alois P. Heinz *)

a(n) = {my(f = factor(n), l = List(), chain = List()); res = 0; forvec(x = vector(#f~, i, [0, f[i, 2]]), listput(l, x)); listput(chain, l[#l]); listpop(l, #l); iterate(chain, l); res}
iterate(c, l) = {if(#l == 1, if(vecsum(abs(c[#c] - l[1])) == 1, res++), my(cc, cl);
for(i = 1, #l, if(vecsum(abs(c[#c] - l[i])) == 1, cc = c; cl = l; listput(cc, l[i]); listpop(cl, i); iterate(cc, cl))))}
first(n) = {my(res = vector(n), m = Map()); res[1] = 1; for(i = 2, n, cn = a046523(i); if(cn == i, mapput(m, i, a(i))); res[i] = mapget(m, cn)); res}
a046523(n)=my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f,(p=nextprime(p+1))^f[i]) \\ (a046523 from Charles R Greathouse IV), David A. Corneth, Nov 24 2017

a(p^k)=1, a(p^k*q)=k+1, a(p^2*q^2)=8, a(p^2*q^3)=17, a(pqr)=18, a(p^2*q*r)=106, a(p^3*q*r)=572, etc. (here p,q,r are distinct primes, k >= 0).

Corrected by D. S. McNeil and Alois P. Heinz and extended by Alois P. Heinz from a(46) via the Seqfan Discussion List (Aug 02 2010)

A295785 a(n) = A179926(A025487(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 4, 18, 1, 8, 5, 106, 1, 17, 6, 572, 1, 38, 2202, 7, 5712, 52, 2918, 1, 78, 41495, 8, 998928, 160, 14376, 1, 164, 742773, 9, 161737320, 469, 392628, 69162, 1, 2719708, 332, 4281895264, 824, 12825336, 10, 24698696592, 1337, 56372096, 327128, 1, 168712111, 680, 5859364320

Offset: 1

David A. Corneth, Dec 25 2017

nonn

Terms in A179926 are only determined by their prime signature. A025487 gives the least positive integer having its prime signature. Combining these sequences removes a lot of duplicates making it somewhat easier to show terms.

a(54) = A003043(5) = 5859364320. - Andrew Howroyd, Oct 26 2019

David A. Corneth, Prime signatures for some k and the corresponding values for A179926(k).

Cf. A025487, A179926.

Terms a(43) and beyond from Andrew Howroyd, Oct 26 2019

A342631 Number of Hamiltonian paths (or Gray codes) on n-cube with the origin as the starting node, up to a permutation of the coordinates.

Original entry on oeis.org

1, 1, 3, 238, 48828036

Offset: 1

Luc Rousseau, May 24 2021

			For n=2, the two Hamiltonian paths of the square that start at (0,0), i.e.,
  (0,0) -->-- (1,0)               (0,0)       (1,0)
                |                   |           |
                V        and        V           ^
                |                   |           |
  (0,1) --<-- (1,1)               (0,1) -->-- (1,1),
only account for one, as one is obtained from the other by the x <-> y permutation; so a(2) = 1.

Luc Rousseau, A C program that computes a(n)
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A003043, A091299.

C
```
/* See Rousseau link. */
```

a(n) = A003043(n) / n!.

A259839 Number of order-preserving Hamiltonian paths in the n-cube (Gray codes); see the comments for the precise definition of order-preserving.

Original entry on oeis.org

1, 1, 1, 1, 1, 10, 123, 1492723

Offset: 0

Torsten Muetze, Jul 06 2015

An order-preserving Hamiltonian path in the n-cube is a listing S_1,...,S_N of all N:=2^n many subsets of [n]:={1,2,...,n}, such that if S_j is a subset of S_i then j <= i+1. For the counting we ignore paths that differ only by renaming elements of the ground set (=automorphisms of the n-cube), i.e., without loss of generality every such path starts as follows: S_1={}, S_2={1}, S_3={1,2}, S_4={2}, S_5={2,3}, S_6={3}, S_7={3,4}, S_8={4},..., S_{2n-2}={n-1}, S_{2n-1}={n-1,n}, S_{2n}={n} (after visiting the set {n}, there are multiple ways to proceed).
It is shown in [Felsner, Trotter 95] that an order-preserving Hamiltonian path is level-accurate in the following sense: After visiting a set of size k, the path will never visit a set of size (k-2) (*).
For odd n we will have S_N={1,2,...,n} (i.e., |S_N|=n) and for even n we will have |S_N|=n-1.
Hamiltonian paths that have property (*) have been constructed in [Savage, Winkler 95] for all n (but these paths are not order-preserving).
For n=8,9,10 we know that a(n)>=1. It is unknown whether a(n)>=1 for n>=11 (i.e., it is not known whether such order-preserving paths exist). Some partial results have been obtained in [Biro, Howard 09].

			For n=4 the a(4)=1 solution is S_1={}, S_2={1}, S_3={1,2}, S_4={2}, S_5={2,3}, S_6={3}, S_7={3,4}, S_8={4}, S_9={2,4}, S_10={1,2,4}, S_11={1,4}, S_12={1,3,4}, S_13={1,3}, S_14={1,2,3}, S_15={1,2,3,4}, S_16={2,3,4}.

C. Biro and D. Howard, The first three levels of an order preserving Hamiltonian path in the subset lattice, Order, 26(2):101-107, 2009.
S. Felsner and W. Trotter, Colorings of diagrams of interval orders and alpha-sequences of sets, Discrete Math., 144(1-3):23-31, 1995.
C. Savage and P. Winkler, Monotone Gray codes and the middle levels problem, J. Combin. Theory Ser. A, 70(2):230-248, 1995.

Cf. A003042, A003043, A006069, A006070, A066037, A091302, A159344.

cp's OEIS Frontend

A003042 Number of directed Hamiltonian cycles (or Gray codes) on n-cube.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

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

A091299 Number of (directed) Hamiltonian paths (or Gray codes) on the n-cube.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Extensions

A179926 Number of permutations of the divisors of n of the form d_1=n, d_2, d_3, ..., d_tau(n) such that d_(i+1)/d_i is a prime or 1/prime for all i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A295785 a(n) = A179926(A025487(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A342631 Number of Hamiltonian paths (or Gray codes) on n-cube with the origin as the starting node, up to a permutation of the coordinates.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

C

Formula

A259839 Number of order-preserving Hamiltonian paths in the n-cube (Gray codes); see the comments for the precise definition of order-preserving.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs