[seqfan] Re: A combinatorial problem

[Vladimir Shevelev]

Yes, you are right:  here I use "arrangements" in this sense.
Of course, a(45)=a(12) since a(n) is function of exponents of prime power factorization of n only (moreover, it is invariant with respect of permutations of them).

Let us prove that, for n>=2, a(n)>=1. Let v(n) denote the number of prime divisors of n. If  v(n)=1, n=p^a, then the unique required arrangement of divisors is p^a, p^(a-1),...,p,1.
Suppose that, for m with v(m)=k and with prime divisors p_1,...,p_k, a required arrangement  exists. Let it be d_1=m, d_2,...,d_tau(m).
Consider now n=m*p_(k+1)^a. For divisors of n we have an arrangement:
d_1*p_(k+1)^a =n, d_2*p_(k+1)^a,...,d_tau(m)*p_(k+1)^a,
d_tau(m)*p_(k+1)^(a-1), d_(tau(m)-1)*p_(k+1)^(a-1),...,d_1*p_(k+1)^(a-1),
 d_1*p_(k+1)^(a-2),...,d_tau(m)*p_(k+1)^(a-2), ...
such that, finally, we obtain a required arrangement for divisors of n.

Using this idea, for n=p_1^a_1*p_2^a_2*...*p_k^a_k, we have

a(n)>=Sum {i=1,...,k}a(n/p_1^a_1)+Sum {1<=i<j<=k}a(n/(p_i^a_i*p_j^a_j))*a(p_i^a_i*p_j^a_j)+...
Therefore,on every subsequence of the form n_1,n_2,... ,when v(n_1)<v(n_2)<..., sequence a(n_i) grows very fast.

Regards,
Vladimir

 

 


----- Original Message -----
From: Alois Heinz <heinz at hs-heilbronn.de>
Date: Monday, August 2, 2010 21:57
Subject: [seqfan] Re: A combinatorial problem
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> 
> By "arrangements" you probably mean "permutations", see also
> http://mathworld.wolfram.com/Arrangement.html
> 
> I computed different values of A179926(n) for the following n:
> 12, 18, 20, 28, 30, 36, 42, 44, 45
> 
> First example: A179926(12)=3:
>  [12, 6, 3, 1, 2, 4]
>  [12, 4, 2, 6, 3, 1]
>  [12, 4, 2, 1, 3, 6]
> Last example: A179926(45)=3:
>  [45, 15, 5, 1, 3, 9]
>  [45, 9, 3, 15, 5, 1]
>  [45, 9, 3, 1, 5, 15]
> 
> seq (A179926(n), n=1..120);
>  0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2,
>  1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 18,
>  1, 1, 2, 2, 2, 8, 1, 2, 2, 4, 1, 18, 1, 3, 3,
>  2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 106,
>  1, 2, 3, 1, 2, 18, 1, 3, 2, 18, 1, 17, 1, 2,
>  3, 3, 2, 18, 1, 5, 1, 2, 1, 106, 2, 2, 2, 4,
>  1, 106, 2, 3, 2, 2, 2, 6, 1, 3, 3, 8, 1, 18,
>  1, 4, 18, 2, 1, 17, 1, 18, 2, 5, 1, 18, 2, 3,
>  3, 2, 2, 572
> 
> Alois
> 
> Vladimir Shevelev schrieb:
> > Dear SeqFans,
> >
> > I have submitted the following sequence:
> >
> > %I A179926
> > %S A179926 
> 0,1,1,1,1,2,1,1,1,2,1,2,1,2,2,1,1,2,1,2,2,2,1,4,1,2,1,2,1,12,1,1,2,2,2,> %T A179926 2,1,2,2,4,1,12,1,2,2,2,1
> > %N A179926 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 
> d_(i+1)/d_i is prime or 1/prime 
> > %C A179926 In view of formulas given below, there are many 
> common first terms with A001221. 
> > %F A179926 a(p^k)=1, a(p*q)=a(p^2*q)=a(p^2*q^2)=2, a(p^3*q)=4, 
> a(pqr)=12 (here p,q,r are distinct primes, k>=1). 
> > %Y A179926 A000005 A001221 
> > %K A179926 nonn
> > %O A179926 1,1
> >
> > More terms? More formulas? Corrections?
> >
> > Regards,
> > Vladimir
> >
> >  Shevelev Vladimir‎
> >   
> 
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎