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.

0, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 2, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 1, 2, 0, 2, 0, 2, 1, 12, 1, 0, 2, 2, 2, 0, 1, 2, 2, 2, 1, 12, 1, 2, 2, 2, 1, 2, 0, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 44, 1, 2, 2, 0, 2, 12, 1, 2, 2, 12, 1, 4, 1, 2, 2, 2, 2, 12, 1, 2, 0, 2, 1, 44, 2, 2, 2, 2, 1, 44, 2, 2, 2, 2, 2, 2, 1, 2, 2, 0, 1, 12, 1, 2, 12, 2, 1, 4, 1, 12, 2, 2, 1, 12, 2, 2, 2, 2, 2, 164, 0, 2, 2, 2, 0, 44, 1, 0

Offset: 1

Author

Vladimir Shevelev, Aug 07 2010

Keywords

• nonn

Comments

a(n) depends on 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 and such that, joining to the last submultiset one element, we again obtain A. How many ways to do this?

Via Seqfan Discussion List (Aug 07 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 A003042. - Vladimir Shevelev, Nov 07 2014

Examples

			If n=p*q, then we have exactly two required chains: p*q, p, 1, q and p*q, q, 1, p. Thus a(6)=a(10)=a(14)=...=2.
		

Links

• 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, Zesz. Nauk. PS., Mat. Stosow., Zeszyt 4, pp. 5-16. (2014).

Crossrefs

Cf. A179926, A000005, A001221, A003042.

Formula

a(p)=1, and, for k>=2, a(p^k)=0; a(p*q)=a(p^2*q)=a(p^3*q)=2; a(p^2*q^2)=0; a(p*q*r)=12, etc. (here p,q,r are distinct primes).

Extensions

Corrected and extended by Alois P. Heinz from a(48) via Seqfan Discussion List (Aug 07 2010)