[seqfan] Re: A combinatorial problem
Alois Heinz
heinz at hs-heilbronn.de
Tue Aug 3 16:36:38 CEST 2010
Alois Heinz schrieb:
> So I computed a(p*q*r*s) = 5712 for distinct primes p,q,r,s.
>
> Now we have:
> a(p), a(p*q), a(p*q*r), a(p*q*r*s) = 1, 2, 18, 5712
> which looks like the beginning of sequence
> http://www.research.att.com/~njas/sequences/A003043
> Can you prove that there is any connection?
>
Ok, the proof is easy.
For distinct primes p_1, ..., p_n
m = p_1 * p_2 * ... p_n has 2^n divisors.
a(m) counts all permutations of the divisors
(d_1=m, d_2..., d_{2^n}) where neighbors
d_j, d_{j+1} differ in exactly one prime factor.
Thus a(m) equals the number of Hamiltonian paths
on an n-cube with a marked starting node.
So we have a(p*q*r*s*t) = 5859364320
for distinct primes p,q,r,s,t, according to
http://www.research.att.com/~njas/sequences/A003043
Alois
More information about the SeqFan
mailing list