[seqfan] A combinatorial problem: non-sorting algorithms for A179926 and A180026
Vladimir Shevelev
shevelev at bgu.ac.il
Tue Aug 24 15:28:19 CEST 2010
1) We start with A180026: "a(n) is the number of arrangements of all divisors of n of the form d_1=n, d_2, d_3,...,d_tau(n) such that every ratio d_(i+1)/d_i and d_tau(n)/d_1 is prime or 1/prime".
Knowing any permissible permutation of divisors delta_1=n, delta_2,...,delta_tau(n), we can calculate the number of all permissible permutations by the following way. Consider square (0,1)-matrix B={b_(i,j)} of order tau(n) in which b_(i,j)=1, if delta_i /delta_j is prime or 1/prime, and
b_(i,j)=0, otherwise. Then a(n) is the number of full cycles (i.e. of length tau(n)) formed by 1's of B.
Let us denote this matrix function by Cycle(B). One can prove that for Cycle(B) the following version of the Laplace expansion along the first row is true:
Cycle(B)=b_(1,2)*Cycle(B^*_(1,2))+b_(1,3)*Cycle(B^*_(1,3))+...
+b_(1,tau(n))*Cycle(B^*_(1,tau(n))),
where B^*_(1,i) is obtained from minor matrix B_(1,i) by cyclic permutation of its first i-1columns:
2=>1, 3=>2,..., i-1=>i-2, 1=>i-1.
Probably, there exists a more effective algorithm of calculation Cycle(B) (?)
2) Let us pass to A179926 :"a(n) is the number of arrangements of all divisors of n of the form d_1=n, d_2, d_3,...,d_tau(n) such that d_(i+1)/d_i is prime or 1/prime". In this case we should
calculate not only full cycles formed by 1's of B but also full cycles formed by 0 in the first column of B and tau(n)-1 1's. Therefore, instead of B, let us consider matrix C which is obtained from B by replacing its first column by column (1,1,...,1). Now here a(n) is the number of full cycles (i.e. of length tau(n)) formed by 1's of C.
Regards,
Vladimir
Shevelev Vladimir
More information about the SeqFan
mailing list