[seqfan] Re: A combinatorial problem

Vladimir Shevelev shevelev at bgu.ac.il
Wed Aug 4 13:52:34 CEST 2010


1) I mind partitions with taking account of order of summands (it is better say "compositions").
2) I err in the calculation of  Sum{j=1,...,n-1}L_j for n=4. We have L_1=1; since 2=2=1+1, then L_2=2*1+1=3; since 3=3=2+1=1+2=1+1+1, then L_3=3*2+2*1+2*1+1=11 and 
Sum{j=1,...,n-1}L_j=1+3+11=15. Therefore, by the formula
 a(p_1*p_2*p_3*p_4)=4*18*15=1080 (not 1368).

If anyone can confirm this result by a direct calculation?

Regards,
Vladimir

----- Original Message -----
From: Vladimir Shevelev <shevelev at bgu.ac.il>
Date: Wednesday, August 4, 2010 9:55
Subject: [seqfan] Re: A combinatorial problem
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>

> I get a recursion soluton when A is a finite set or, 
> equivalently, I obtained a recursion for
>  a(p_1*p_2*...*p_n), where  a(n)=A179926(n). It is: 
> a(p_1)=1 and for n>=2 we have
> 
> a(p_1*p_2*...*p_n)=n*a(p_1*p_2*...*p_(n-1))*Sum{j=1,...,n-1}L_j,
> 
> where
> 
> L_j=SumProd{t=1,...,j}(i_t!*(i_t-1)!),
> 
> where sum is over all partitions of j with parts i_t>=1.
> 
> For n=1,2,3,4, I get 1,3,18,1368.
> 
> More terms? 
> 
> Regards,
> Vladimir
> 
> 
> 
> ----- Original Message -----
> From: Vladimir Shevelev <shevelev at bgu.ac.il>
> Date: Tuesday, August 3, 2010 12:30
> Subject: [seqfan] Re: A combinatorial problem
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> 
> >    I would like indicate 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. How ways to do 
> this? 
> >   It is interesting even a subproblem, if A is a 
> finite set.
> >   Maybe, anyone met such statement of  a problem?
> > 
> > Regards,
> > Vladimir
> > 
> > ----- Original Message -----
> > From: Vladimir Shevelev <shevelev at bgu.ac.il>
> > Date: Monday, August 2, 2010 22:59
> > Subject: [seqfan] Re: A combinatorial problem
> > To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> > 
> > > 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_i^a_i)+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‎
> > > 
> > > _______________________________________________
> > > 
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > > 
> > 
> >  Shevelev Vladimir‎
> > 
> > _______________________________________________
> > 
> > Seqfan Mailing list - http://list.seqfan.eu/
> > 
> 
>  Shevelev Vladimir‎
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/
> 

 Shevelev Vladimir‎



More information about the SeqFan mailing list