cp's OEIS Frontend

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

%I A119842 #25 Feb 17 2024 23:43:59
%S A119842 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,
%T A119842 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,
%U A119842 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
%N A119842 Number of alternating linear extensions of the divisor lattice of n.
%C A119842 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
%H A119842 Alois P. Heinz, <a href="/A119842/b119842.txt">Table of n, a(n) for n = 1..10000</a>
%H A119842 T. Y. Chow, H. Eriksson, C. K. Fan, <a href="http://www.combinatorics.org/Volume_11/Abstracts/v11i2a3.html">Chess Tableaux</a>, The Electronic Journal of Combinatorics, vol. 11(2), 2004.
%H A119842 T. Y. Chow, H. Eriksson, C. K. Fan, <a href="http://www-math.mit.edu/~tchow/chesstalk.pdf">Chess Tableaux and Chess Problems</a>, slides for MIT Combinatorics Seminar, 20 October 2004.
%H A119842 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>
%e A119842 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.
%p A119842 with(numtheory):
%p A119842 b:= proc(s, t) option remember; `if`(nops(s)<1, 1, add(
%p A119842       `if`(irem(bigomega(x), 2)=1-t and nops(select(y->
%p A119842       irem(y, x)=0, s))=1, b(s minus {x}, 1-t), 0), x=s))
%p A119842     end:
%p A119842 a:= proc(n) option remember; local l, m;
%p A119842       l:= sort(ifactors(n)[2], (x, y)-> x[2]>y[2]);
%p A119842       m:= mul(ithprime(i)^l[i][2], i=1..nops(l));
%p A119842       b(divisors(m) minus {1, m}, irem(bigomega(m), 2))
%p A119842     end:
%p A119842 seq(a(n), n=1..100);  # _Alois P. Heinz_, Feb 26 2016
%t A119842 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_ *)
%Y A119842 a(n) <= A114717(n). Cf. A119844, A119846, A119847, A119849.
%K A119842 nonn
%O A119842 1,36
%A A119842 _Antti Karttunen_, Jun 04 2006