This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A119842 Number of alternating linear extensions of the divisor lattice of n. 13


%S 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 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 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 Number of alternating linear extensions of the divisor lattice of n.

%C 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 Alois P. Heinz, <a href="/A119842/b119842.txt">Table of n, a(n) for n = 1..10000</a>

%H 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 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 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>

%e 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 only 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 with(numtheory):

%p b:= proc(s, t) option remember; `if`(nops(s)<1, 1, add(

%p `if`(irem(bigomega(x), 2)=1-t and nops(select(y->

%p irem(y, x)=0, s))=1, b(s minus {x}, 1-t), 0), x=s))

%p end:

%p a:= proc(n) option remember; local l, m;

%p l:= sort(ifactors(n)[2], (x, y)-> x[2]>y[2]);

%p m:= mul(ithprime(i)^l[i][2], i=1..nops(l));

%p b(divisors(m) minus {1, m}, irem(bigomega(m), 2))

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Feb 26 2016

%t 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 a(n) <= A114717(n). Cf. A119844, A119846, A119847, A119849.

%K nonn,hard

%O 1,36

%A _Antti Karttunen_, Jun 04 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 16:40 EST 2019. Contains 319271 sequences. (Running on oeis4.)