Enumeration formulas involving partitions
Christian G. Bower
bowerc at usa.net
Fri May 2 20:01:45 CEST 2008
structures then Euler transform of a(n) (or EULER(a)(n)) is the total number
From: "webonfim" <webonfim at bol.com.br>
To: "seqfan" <seqfan at ext.jussieu.fr>
Subject: Enumeration formulas involving partitions
graphs with connected components of that class. Objects with a given number
Return-Path: <israel at math.ubc.ca>
X-Ids: 168
Date: Fri, 2 May 2008 11:05:21 -0700 (PDT)
From: Robert Israel <israel at math.ubc.ca>
To: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>
cc: seqfan at ext.jussieu.fr, qq-quet at mindspring.com
Subject: Re: A138812 & A138813 Asymptotics
In-Reply-To: <256312.91440.qm at web45602.mail.sp1.yahoo.com>
Message-ID: <Pine.GSO.4.64.0805021041060.23295 at hilbert.math.ubc.ca>
References: <256312.91440.qm at web45602.mail.sp1.yahoo.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.168]); Fri, 02 May 2008 20:05:25 +0200 (CEST)
X-Virus-Scanned: ClamAV 0.92/7012/Fri May 2 16:53:34 2008 on shiva.jussieu.fr
X-Virus-Status: Clean
X-Miltered: at jchkmail.jussieu.fr with ID 481B57E4.002 by Joe's j-chkmail (http : // j-chkmail dot ensmp dot fr)!
X-j-chkmail-Enveloppe: 481B57E4.002/137.82.36.61/viol.math.ubc.ca/viol.math.ubc.ca/<israel at math.ubc.ca>
X-j-chkmail-Score: MSGID : 481B57E4.002 on jchkmail.jussieu.fr : j-chkmail score : XX : R=. U=. O=. B=0.340 -> S=0.340
X-j-chkmail-Status: Unsure
Those can't be right. If a(n) < C n for n < m,
we'd have a(m) > sum_{k=1}^{m-1} (m/(C k) - 1) ~ m ln(m)/C.
I think it ought to be a(n) ~ sqrt(2) n ln(n)^(1/2), since
sum_{k=1}^{n-1} n/(sqrt(2) k ln(k)^(1/2)) ~ sqrt(2) n ln(n)^(1/2).
Robert Israel israel at math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
On Fri, 2 May 2008, Leroy Quet wrote:
> Consider these two sequences.
>
> A138812: a(0)=1. a(n) = sum{k=0 to n-1}
> floor(n/a(k)).
>
> A138813: a(0)=1. a(n) = sum{k=0 to n-1}
> ceiling(n/a(k)).
>
> Plotting A138812 and A138813, it LOOKS like
> A138812(n) ~ c*n and that A138813(n) ~ d*n, where
> c and d are some constants and d > c.
>
> But I doubt this is really the case.
> I think that A138812 may actually start to rise
> faster than A138813 at some point, and overtake
> it. Is that hunch correct?
>
> In any case, can someone calculate many more
> terms of these sequences so as to see what
> A138812 and A138813 might be asymptotical to?
>
> Thanks,
> Leroy Quet
>
>
>
>
> ____________________________________________________________________________________
> Be a better friend, newshound, and
> know-it-all with Yahoo! Mobile. Try it now. http://mobile.yahoo.com/;_ylt=Ahu06i62sR8HDtDypao8Wcj9tAcJ
>
I agree with Robert, it can't be linear. Here are some data that appear
consistent with his proposed sqrt(2)n*sqrt(ln(n)) bound:
A138812:
a( 2)= 4 a(n)/n=2.0000 a(n)/(n*sqrt(ln(n)))=2.4022
a( 4)= 9 a(n)/n=2.2500 a(n)/(n*sqrt(ln(n)))=1.9110
a( 8)= 19 a(n)/n=2.3750 a(n)/(n*sqrt(ln(n)))=1.6470
a( 16)= 42 a(n)/n=2.6250 a(n)/(n*sqrt(ln(n)))=1.5765
a( 32)= 91 a(n)/n=2.8438 a(n)/(n*sqrt(ln(n)))=1.5275
a( 64)= 196 a(n)/n=3.0625 a(n)/(n*sqrt(ln(n)))=1.5017
a( 128)= 421 a(n)/n=3.2891 a(n)/(n*sqrt(ln(n)))=1.4932
a( 256)= 896 a(n)/n=3.5000 a(n)/(n*sqrt(ln(n)))=1.4863
a( 512)= 1892 a(n)/n=3.6953 a(n)/(n*sqrt(ln(n)))=1.4795
a( 1024)= 3979 a(n)/n=3.8857 a(n)/(n*sqrt(ln(n)))=1.4759
a( 2048)= 8335 a(n)/n=4.0698 a(n)/(n*sqrt(ln(n)))=1.4739
a( 4096)= 17386 a(n)/n=4.2446 a(n)/(n*sqrt(ln(n)))=1.4718
a( 8192)= 36146 a(n)/n=4.4124 a(n)/(n*sqrt(ln(n)))=1.4699
a( 16384)= 74931 a(n)/n=4.5734 a(n)/(n*sqrt(ln(n)))=1.4681
a( 32768)= 154964 a(n)/n=4.7291 a(n)/(n*sqrt(ln(n)))=1.4666
a( 65536)= 319818 a(n)/n=4.8800 a(n)/(n*sqrt(ln(n)))=1.4654
a(131072)= 658761 a(n)/n=5.0259 a(n)/(n*sqrt(ln(n)))=1.4641
A138813:
a( 2)= 4 a(n)/n=2.0000 a(n)/(n*sqrt(ln(n)))=2.4022
a( 4)= 10 a(n)/n=2.5000 a(n)/(n*sqrt(ln(n)))=2.1233
a( 8)= 24 a(n)/n=3.0000 a(n)/(n*sqrt(ln(n)))=2.0804
a( 16)= 53 a(n)/n=3.3125 a(n)/(n*sqrt(ln(n)))=1.9894
a( 32)= 115 a(n)/n=3.5938 a(n)/(n*sqrt(ln(n)))=1.9304
a( 64)= 244 a(n)/n=3.8125 a(n)/(n*sqrt(ln(n)))=1.8695
a( 128)= 514 a(n)/n=4.0156 a(n)/(n*sqrt(ln(n)))=1.8230
a( 256)= 1075 a(n)/n=4.1992 a(n)/(n*sqrt(ln(n)))=1.7832
a( 512)= 2237 a(n)/n=4.3691 a(n)/(n*sqrt(ln(n)))=1.7493
a( 1024)= 4642 a(n)/n=4.5332 a(n)/(n*sqrt(ln(n)))=1.7218
a( 2048)= 9608 a(n)/n=4.6914 a(n)/(n*sqrt(ln(n)))=1.6990
a( 4096)= 19843 a(n)/n=4.8445 a(n)/(n*sqrt(ln(n)))=1.6797
a( 8192)= 40895 a(n)/n=4.9921 a(n)/(n*sqrt(ln(n)))=1.6630
a( 16384)= 84129 a(n)/n=5.1348 a(n)/(n*sqrt(ln(n)))=1.6483
a( 32768)= 172797 a(n)/n=5.2733 a(n)/(n*sqrt(ln(n)))=1.6354
a( 65536)= 354437 a(n)/n=5.4083 a(n)/(n*sqrt(ln(n)))=1.6240
a(131072)= 726143 a(n)/n=5.5400 a(n)/(n*sqrt(ln(n)))=1.6139
Regards,
Drew
On May 2 2008, Robert Israel wrote:
>Those can't be right. If a(n) < C n for n < m,
>we'd have a(m) > sum_{k=1}^{m-1} (m/(C k) - 1) ~ m ln(m)/C.
>I think it ought to be a(n) ~ sqrt(2) n ln(n)^(1/2), since
>sum_{k=1}^{n-1} n/(sqrt(2) k ln(k)^(1/2)) ~ sqrt(2) n ln(n)^(1/2).
>
>Robert Israel israel at math.ubc.ca
>Department of Mathematics http://www.math.ubc.ca/~israel
>University of British Columbia Vancouver, BC, Canada
>
>
>On Fri, 2 May 2008, Leroy Quet wrote:
>
>> Consider these two sequences.
>>
>> A138812: a(0)=1. a(n) = sum{k=0 to n-1}
>> floor(n/a(k)).
>>
>> A138813: a(0)=1. a(n) = sum{k=0 to n-1}
>> ceiling(n/a(k)).
>>
>> Plotting A138812 and A138813, it LOOKS like
>> A138812(n) ~ c*n and that A138813(n) ~ d*n, where
>> c and d are some constants and d > c.
>>
>> But I doubt this is really the case.
>> I think that A138812 may actually start to rise
>> faster than A138813 at some point, and overtake
>> it. Is that hunch correct?
>>
>> In any case, can someone calculate many more
>> terms of these sequences so as to see what
>> A138812 and A138813 might be asymptotical to?
>>
>> Thanks,
>> Leroy Quet
>>
>>
>>
>
More information about the SeqFan
mailing list