A119842 Number of alternating linear extensions of the divisor lattice of n.

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 6, 1, 0, 1, 1, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 2, 1, 0

Offset: 1

Author

Antti Karttunen, Jun 04 2006

Keywords

• nonn

Comments

For prime powers there is only one solution. For integers with prime signature p1^2 * p2 there's exactly one solution, for p1^4 * p2 there are two and in general for p1^(2k) * p2 there are A000108(k) solutions. - Mitch Harris, Apr 27 2006

Examples

			In other words, the number of ways to arrange the divisors of n in such a way that no divisor has any of its own divisors following it AND the divisors d_i, d_j, d_k, etc. are arranged so that values bigomega(d_i) (cf. A001222), bigomega(d_j), bigomega(d_k) are alternatively even and odd. E.g., a(12)=1, as of the five arrangements shown in A114717, here the only one allowed is 1,2,4,3,6,12, with A001222(1)=0, A001222(2)=1, A001222(4)=2, A001222(3)=1, A001222(6)=2, A001222(12)=3. a(36) = 2, as there are two solutions for 36: 1,2,4,3,6,12,9,18,36 and 1,3,9,2,6,18,4,12,36.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..10000
• T. Y. Chow, H. Eriksson, C. K. Fan, Chess Tableaux, The Electronic Journal of Combinatorics, vol. 11(2), 2004.
• T. Y. Chow, H. Eriksson, C. K. Fan, Chess Tableaux and Chess Problems, slides for MIT Combinatorics Seminar, 20 October 2004.
• Index entries for sequences computed from exponents in factorization of n

Crossrefs

a(n) <= A114717(n). Cf. A119844, A119846, A119847, A119849.

Programs

Maple

with(numtheory):
b:= proc(s, t) option remember; `if`(nops(s)<1, 1, add(
      `if`(irem(bigomega(x), 2)=1-t and nops(select(y->
      irem(y, x)=0, s))=1, b(s minus {x}, 1-t), 0), x=s))
    end:
a:= proc(n) option remember; local l, m;
      l:= sort(ifactors(n)[2], (x, y)-> x[2]>y[2]);
      m:= mul(ithprime(i)^l[i][2], i=1..nops(l));
      b(divisors(m) minus {1, m}, irem(bigomega(m), 2))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Feb 26 2016

Mathematica

b[s_, t_] := b[s, t] = If[Length[s] < 1, 1, Sum[If[Mod[PrimeOmega[x], 2] == 1-t && Length[Select[s, Mod[#, x] == 0&]] == 1, b[s ~Complement~ {x}, 1-t ], 0], {x, s}]]; a[n_] := a[n] = Module[{l, m}, l = Sort[FactorInteger[n ], #1[[2]] > #2[[2]]&]; m = Product[Prime[i]^l[[i]][[2]], {i, 1, Length[ l]}]; b[Divisors[m][[2 ;; -2]], Mod[PrimeOmega[m], 2]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Feb 27 2016, after Alois P. Heinz *)