GeOlymp Forum: ხარისხების ჯამების დათვლა

ხარისხების ჯამების დათვლა

ავტორი tsotne

1^k+2^k+3^k+...+n^k

წერილები: 83

8 მაისი 2012, 14:23

ამ თემის შექმნა შთამაგონა ზურა ისაკაძის (@scientist1642) თემამ. ძალიან ბევრი ასეთი ჯამების დათვლა საბოლოოდ დადის შემდეგი ფორმულის სწრაფად დათვლაზე:
$f(n,k)=1^k+2^k+...+n^k$
მე პირადად არ გამომიყენებია k>3 შემთხვევებში ფორმულა, თუმცა ამ თემაში ვისაუბრებ თუ როგორ შეიძლება ამ ფორმულების მიღება. პროგრამულად, ნებისმიერი f(n,1), f(n,2), ... , f(n,k)-სთვის პრეკალკულაციას ჭირდება O(k^3) დრო და O(k^2) მეხსიერება, და შემდეგ f(n,k) ითვლება O(k) დროში. თუმცა, უბრალოდ საინტერესოა, სუფთა თეორიაში, ქაღალდზე, როგორ გამოვიყვანოთ ეს ფორმულები. ცნობისათვის,
$f(n,1)=\frac{n*(n+1)}{2}$
$f(n,2)=\frac{n*(n+1)*(2n+1)}{6}$
$f(n,3)=(\frac{n*(n+1)}{2})^2$
(სხვათა შორის, შეამჩნევდით, რომ f(n,3)=f(n,1)^2. ძალიან საინტერესო ტოლობაა, სკოლის ასაკში შეიძლება შეგხვედრიათ და ამოგიხსნიათ კიდეც).

მაშ ასე, დავიწყოთ დამტკიცება! მოდით განვიხილოთ რისი ტოლია $n^k-(n-1)^k$ .

$n^k-(n-1)^k=n^{k-1}+n^{k-2}*(n-1)+n^{k-3}*(n-1)^2+...+n*(n-1)^{k-2}+(n-1)^{k-1}=\sum_{i=0}^{k-1} (n^{k-1-i}*(n-1)^i)=\sum_{i=0}^{k-1} (n^{k-1}-C_{i}^{1}*n^{k-2}+C_{i}^{2}*n^{k-3}-...+(-1)^i*n^{k-1-i})=k*n^{k-1}-(C_{1}^{1}+C_{2}^1+...+C_{k-1}^{1})*n^{k-2}+(C_{2}^{2}+C{3}^{2}+...+C_{k-1}^2)*n^{k-3}-...+(-1)^{k-1}=\sum_{i=0}^{k-1}((-1)^i*(C_i^i+C_{i+1}^i+...+C_{k-1}^i)*n^{k-1-i})$

ახლა გამოვიყენებთ ფორმულას
$C_i^i+C_{i+1}^i+...+C_{k-1}^i=C_k^{i+1}$
და მივიღებთ, რომ
$n^k-(n-1)^k=\sum_{i=0}^{k-1}((-1)^i*C_k^{i+1}*n^{k-1-i})$

ეს ყველაფერი კაია, მაგრამ გაგიჩნდებათ კითხვა, აქედან სასარგებლოს რას ვღებულობთ ჩვენი ამოცანისთვის :D

მოდით დავითვალოთ რისი ტოლია n^(k+1).

$n^{k+1}=(n^{k+1}-(n-1)^{k+1})+((n-1)^{k+1}-(n-2)^{k+1})+...+(1^{k+1}-0^{k+1})=\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*n^{k-i})+\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*(n-1)^{k-i})+...+\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*1^{k-i})=\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*(n^{k-i}+(n-1)^{k-i}+...+1^{k-i}))=\sum_{i=0}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))=(k+1)*f(n,k)+\sum_{i=1}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))$

ახლა გამოვთვალოთ f(n,k).

რადგანაც
$n^{k+1}=(k+1)*f(n,k)+\sum_{i=1}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))$
ამიტომ

$f(n,k)=\frac{n^{k+1}-\sum_{i=1}^{k}((-1)^i*C_{k+1}^{i+1}*f(n,k-i))}{k+1}$

შევნიშნოთ, რომ განტოლების მარჯვენა მხარეს ყოველი f(n,x) ფუნქციაში, x<k. მეტიც, ჩვენ ვიყენებთ მხოლოდ f(n,1), f(n,2), f(n,3), ... , f(n,k-1). ამიტომ დავიწყოთ იქიდან, რომ f(n,0)=1^0+2^0+...+n^0=n. და k-ს ზრდის მიხედვით ავყვეთ. მივიღებთ ფუნქციას ყველა k-სთვის :)

ვისაც ეს ფორმულა ურჩხული გგონიათ, ძალიან ცდებით. მოდით გამოვიანგარიშოთ f(n,1), f(n,2), f(n,3). საინტერესო იქნება f(n,4)-ის მნიშვნელობის გამოთვლა, რომელიც მეც არ ვიცი ჯერჯერობით, თუმცა დაპოსტვის შემდეგ მეცოდინება :)

$f(n,1)=\frac{n^{2}-\sum_{i=1}^{1}((-1)^i*C_{2}^{i+1}*f(n,1-i))}{2}=\frac{n^{2}+C_{2}^{2}*f(n,0))}{2}=\frac{n^{2}+n}{2}=\frac{n*(n+1)}{2}$

$f(n,2)=\frac{n^{3}-\sum_{i=1}^{2}((-1)^i*C_{3}^{i+1}*f(n,2-i))}{3}=\frac{n^{3}+C_3^2*f(n,1)-C_3^3*f(n,0)}{3}=\frac{n^{3}+3*\frac{n^2+n}{2}-n}{3}=\frac{2*n^{3}+3*n^2+3*n-2*n}{6}=\frac{n*(2*n^{2}+3*n+1)}{6}=\frac{n(n+1)(2n+1)}{6}$

$f(n,3)=\frac{n^{4}-\sum_{i=1}^{3}((-1)^i*C_{4}^{i+1}*f(n,3-i))}{4}=\frac{n^{4}+C_4^2*f(n,2)-C_4^3*f(n,1)+C_4^4*f(n,0)}{4}=\frac{n^{4}+6*\frac{n(n+1)(2n+1)}{6}-4*\frac{n*(n+1)}{2}+n}{4}=\frac{n^{4}+n(n+1)(2n+1)-2n(n+1)+n}{4}=\frac{n(n^3+(n+1)(2n+1)-2(n+1)+1)}{4}=\frac{n(n+1)((n^2-n+1)+(2n+1)-2)}{4}=\frac{n(n+1)*n(n+1)}{4}=(\frac{n(n+1)}{2})^2$

საინტერესოა რა იქნება f(n,4)-ის ფორმულა :)

აჰა! ვიწვალე და გამოვთვალე :)

$f(n,4)=\frac{n^5-\sum_{i=1}^4((-1)^i*C_5^{i+1}*f(n,4-i))}{5}=\frac{n^5+C_5^2*f(n,3)-C_5^3*f(n,2)+C_5^4*f(n,1)-C_5^5*f(n,0)}{5}=\frac{n^5+10*\frac{n^2(n+1)^2}{4}-10*\frac{n(n+1)(2n+1)}{6}+5*\frac{n*(n+1)}{2}-n}{5}=\frac{n^5+15n^2(n+1)^2-10n(n+1)(2n+1)+15n*(n+1)-6n}{30}=\frac{n(6(n^4-1)+15n(n+1)^2-10(n+1)(2n+1)+15(n+1))}{30}=\frac{n(n+1)(6(n-1)(n^2+1)+15n(n+1)-10(2n+1)+15)}{30}=\frac{n(n+1)(6n^3+9n^2+n-1)}{30}=\frac{n(n+1)(2n+1)(3n^2+3n-1)}{30}$

პროგრამულად ამის გაკეთებას თქვენვე მოგანდობთ ;)

წერილები: 54

varlevani says:

9 მაისი 2012, 21:32

რამ გაწერინა ამდენი ლატექსში? სააააღოლ! :D

წერილები: 83

tsotne says:

10 მაისი 2012, 0:04

უფრო მეტსაც დავწერ თუ საჭირო გახდა, მაგრამ ეჭვი მეპარება ესეც ვინმემ რომ წაიკითხოს :)

წერილები: 48

nikaj says:

12 მაისი 2012, 5:54

SRM 397 ის Medium იყო ამაზე

გარჩევა:
http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm397

წერილები: 83

tsotne says:

12 მაისი 2012, 9:00

საიდან გახსოვს ყველა ამოცანა მაინც ვერ ვხვდები :) :D მანდ სხვანაირი ამოხსნა წერია, უფრო მარტივად იწერება ცხადია :) ახლა გავიგე ბერნულის რიცხვების შესახებ :) მადლობა ;)

გთხოვთ გაიარეთ ავტორიზაცია კომენტარის გამოსაქვეყნებლად.