[seqfan] A combinatorial problem: generalization

[Vladimir Shevelev]

(With corrections)

At the last time, by my initiative, we considered a calculation problem for A179926(N) in case when N=2*3*...*p_n  (it is sufficient to consider case when p_n is the n-th prime). Alois proved that A179926(N) equals the number of Hamiltonian paths on an n-cube with a marked starting node
(cf. A003043). Now I consider a combinatorial generalization of the last problem in the following form:
 
"Ladies' good companies problem".
 
 In a company there are s women w_1,...,w_s and s men g_1,...,g_s. In total men(women) speak  m languages (list of them) that in total women (men) know, while every member of the company knows exactly k<=m  languages of opposite sex (list of them for every member). By how many ways one can seat them at  circular (rectangle) table, men and women in alternative positions, so that every woman could speak with both of adjacent men? 
In case of rectangle table one woman speaks with one man only.
 
Denote F(s,m,k) (U(s,m,k) the number of such ways in case of rectangle (circular) table.
 
Connection with considered problem of calculation of A179926(N).
 Number N has 2^n divisors from which 2^(n-1) are products of even number of primes (including 1)
[type 1] and  2^(n-1) are products of odd number of primes. Put s=2^(n-1) [type 2]. Divisors of N of type i (i=0 or 1) we call "woman's " if  n==i (mod 2) and othe divisors we call man's. Let N correspond to w_1 and "seat" it on the first place (from the left). Thus we shoul "seat" other "woman's " s=2^(n-1) divisors on the odd places. Put , m=2^n, such that to every divisor d_i of N corresponds a language <d_i> with no two the same languages. Put also k=n such that d_i  speaks languages  <d_i*p_j> or <d_i/p_j>. E.g., in case of N=2*3*5*7*, divisor d=3*7 "knows"
the following n=4 languages of opposthe sex: <3>,<7>,<3*5*7>,<2*3*7>; divisor d=1 "knows"
the following n=4 languages of opposthe sex: <2>,<3>,<5>,<7>, etc.
Then it is easy to see that F(2^(n-1),2^n,n)/2^n gives A179926(N). Indeed, seating the women first, we can do this by 2*(2^(n-1)!) ways, while  if w_1 seats on the first place, then we have (2^(n-1)-1)! ways only.
 
In conclusion, I present  the following new sequence:
 
%I A180026
%S A180026 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,
%T A180026 0,1,2,2,2,1,12,1,2,2,2,1
%N 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 
%C A180026 a(n) is depends on exponents of prime power factorization of n only; moreover, 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 1 element we obtain A. How many ways to do this? 
%F A180026 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). 
%e A180026 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. 
%Y A180026 A179926 A000005 A001221 
%K A180026 nonn
%O A180026 1,6

Thanks to Alois which corrected  a(p*q*r)=12 (instead of 6 as I calculated)

Regards,
Vladimir

 Shevelev Vladimir‎