A329319 -id:A329319 - cp's OEIS frontend

A269565 Array read by antidiagonals: T(n,m) is the number of (directed) Hamiltonian paths in K_n X K_m.

1, 2, 2, 6, 8, 6, 24, 60, 60, 24, 120, 816, 1512, 816, 120, 720, 17520, 83520, 83520, 17520, 720, 5040, 550080, 8869680, 22394880, 8869680, 550080, 5040, 40320, 23839200, 1621680480, 13346910720, 13346910720, 1621680480, 23839200, 40320

Offset: 1

Andrew Howroyd, Feb 29 2016

Equivalently, the number of directed Hamiltonian paths on the n X m rook graph.
Conjecture: T(n,m) mod n!*m! = 0. - Mikhail Kurkov, Feb 08 2019
The above conjecture is true since a path defines an ordering on the rows and columns by the order in which they are first visited by the path. Every permutation of rows and columns therefore gives a different path. - Andrew Howroyd, Feb 08 2021

			Array begins:
===========================================================
n\m|    1      2        3            4               5
---+-------------------------------------------------------
1  |    1,     2,       6,          24,            120, ...
2  |    2,     8,      60,         816,          17520, ...
3  |    6,    60,    1512,       83520,        8869680, ...
4  |   24,   816,   83520,    22394880,    13346910720, ...
5  |  120, 17520, 8869680, 13346910720, 50657369241600, ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..96
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A096970.
Columns 2..3 are A096121, A329319.
Cf. A286418, A269562.

From Andrew Howroyd, Oct 20 2019: (Start)
T(n,m) = T(m,n).
T(n,1) = n!. (End)

A329320 a(n) = Sum_{k=0..floor(log_2(n))} 1 - A035263(1 + floor(n/2^k)).

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 1, 2, 2, 2, 2, 3, 2, 3, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 3, 3, 3, 3, 4, 3

Offset: 0

Mikhail Kurkov, Nov 10 2019 [verification needed]

Sequence which arise from attempts to simplify computing of A329319.

For all positive integers k, the subsequence a(2^k) to a(3*2^(k-1)-1) is identical to the subsequence a(3*2^(k-1)) to a(2^(k+1)-1). Also subsequences a(2^k) to a(3*2^(k-1)-1) and a(0) to a(2^(k-1)-1) always differ by 1.

Mikhail Kurkov, Table of n, a(n) for n = 0..8191 [verification needed]

Cf. A035263, A329319.

a(n) = if (n==0, 0, a(floor(n/2)) + valuation(n+1, 2) %  2); \\ Michel Marcus, Nov 13 2019

a(n)=my(s,t); while(n, n>>=valuation(n,2); t=valuation(n+1,2); s+=(t+1)\2; n>>=t); s \\ Charles R Greathouse IV, Oct 14 2021

a(n) = a(floor(n/2)) + 1 - A035263(n+1) for n>0 with a(0)=0.

a(2^m+k) = a(k mod 2^(m-1)) + 1 for 0<=k<2^m, m>0 with a(0)=0, a(1)=1.

cp's OEIS Frontend

A269565 Array read by antidiagonals: T(n,m) is the number of (directed) Hamiltonian paths in K_n X K_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula