|
|
A119842
|
|
Number of alternating linear extensions of the divisor lattice of n.
|
|
13
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,36
|
|
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
|
|
LINKS
|
T. Y. Chow, H. Eriksson, C. K. Fan, Chess Tableaux, The Electronic Journal of Combinatorics, vol. 11(2), 2004.
|
|
EXAMPLE
|
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.
|
|
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:
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|