||V{maketoc}||
||__~~navy:@#13::: این مطلب از بخش آموزش وب‌سایت المپیاد ریاضی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وب‌سایت المپیاد رشد]موجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین می‌توانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا))‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.:: #@~~__||
^@#16:
!افرازهای یک عدد
افراز یک ((عدد صحیح)) به معنی تقسیم اشیاء یکسان در ظرف‌های یکسان غیرتهی می‌باشد که اگر به جای اشیای یکسان، اشیاء را متفاوت بگیریم به مفهوم مشابه آن یعنی افراز یک مجموعه می‌رسیم.
و اما افراز یک عدد صحیح چیست؟
افرازهای یک عدد صحیح مثبت، راه‌های نوشتن آن عدد به صورت مجموع اعداد صحیح مثبت است. مثلاً افرازهای 5 عبارت‌اند از :
@@{TEX()} {5,4+1,3+1+1,2+1+1+1,3+2,2+2+1,1+1+1+1+1} {TEX}@@
چون تعداد افرازهای 5 برابر 7 است، می‌نویسیم{TEX()} { p(5) = 7 } {TEX} ؛ به طور کلی فرض کنیم{TEX()} { p(n)} {TEX} تعداد افرازهای عدد صحیح مثبت {TEX()} {n} {TEX}را نشان دهد. در افرازی مانند 2 + 3 بالا هریک از اعداد 3 و 2 را یک جمع‌وند می‌گویند. بنابراین عدد 5 دارای افراز با یک جمع‌وند، دو افراز با دو جمع‌وند، دو افراز با سه جمع‌وند، یک افراز با چهار جمع‌وند و یک افراز با پنج جمع‌وند است.
در حالی که 5 دارای دو افراز با سه جمع‌وند است، معادله{TEX()} { x_1 + x_2¬ + x_3 = 5} {TEX} در مجموعه اعداد صحیح مثبت دارای شش جواب است که عبارت‌اند از:
@@{TEX()} {(3,1,1),(1,3,1),(1,1,3),(2,2,1),(2,1,2),(1,2,2)} {TEX}@@
در شمردن تعداد جواب‌های یک معادله، ترتیب در نظر گرفته می‌شود؛ ولی در شمردن تعداد افرازها، ترتیب جمع‌وندها مفهومی ندارد.
---
!!نمودارهای افرازها
به افرازهای 6 توجه کنید:
@@{TEX()} {6,1+1+1+1+1+1,4+1+1,5+1,2+2+1+1,2+1+1+1+1,3+2+1,4+2,3+1+1+1,2+2+2,3+3} {TEX}@@ (1)
یازده افراز وجود دارد، بنابراین می‌نویسیم {TEX()} { p(6) = 11} {TEX} . همچنین می‌بینیم که تعداد افرازهای 6
#@
@#16:
::به 6 جمع‌وند، برابر 1؛ ::
::به 5 جمع‌وند، برابر 1؛::
(2) :: به 4 جمع‌وند، برابر 2؛::
::به 3 جمع‌وند، برابر 3؛::
::به 2 جمع‌وند، برابر 3؛::
::به 1 جمع‌وند، برابر 1؛::
است.
تعداد افرازهای {TEX()} {n} {TEX}را که تعداد جمع‌وندهای آنها کوچکتر یا مساوی {TEX()} {k} {TEX}است با نماد{TEX()} {q_k(n)} {TEX}نشان خواهیم داد. به ازای{TEX()} { n = 6} {TEX} ، فهرست (2)ی بالا نشان می‌دهد که:
(3) @@ {TEX()} {q_6(6)=11 \ q_5(6)=10 \ q_4 (6)=9 \ q_3 (6)=7 \ q_2(6)=4 \ q_1(6)=1} {TEX}@@
چون عدد 6 نمی‌تواند به بیشتر از شش جمع‌وند افراز شود، انتظار داریم که{TEX()} { q¬_6(6) } {TEX}همان {TEX()} { p(6) } {TEX} باشد. به همین ترتیب{TEX()} { q_n(n)} {TEX} ، به معنای تعداد افرازهای {TEX()} {n} {TEX}است که دارای {TEX()} {n} {TEX}جمع‌وند یا کمتراز {TEX()} {n} {TEX}جمع‌وند است و بنابراین
(4) @@ {TEX()} { q_n(n) = p(n) } {TEX} @@
همچنین می‌توان افرازها را بر حسب اندازه جمع‌وندها رده‌بندی کرد. فهرست (1) نشان می‌دهد که تعداد افرازهای 6،
::با 6 به عنوان بزرگترین جمع‌وند، برابر 1 است؛::
::با 5 به عنوان بزرگترین جمع‌وند، برابر 1 است،::
::با 4 به عنوان بزرگترین جمع‌ند، برابر 2 است،::
::با 3 به عنوان بزرگترین جمع‌ند، برابر 3 است،::
::با 2 به عنوان بزرگترین جمع‌وند، برابر 3 است،::
::با 1 به عنوان بزرگترین جمع‌وند، برابر 1 است،::
#@
@#16:
به شباهت این فهرست با فهرست (2) توجه کنید. همان طوری که خواهیم دید این امر تصادفی نیست. به علاوه اگر{TEX()} { p_k(n) } {TEX}را تعداد افرازهایی از {TEX()} {n} {TEX}تعریف کنیم که هیچ یک از جمع‌وندهای آن از {TEX()} {k} {TEX}بزرگتر نباشد، نتیجه می‌گیریم که:
@@{TEX()} {p_6(6)=11 \ p_5(6)=10 \ p_4 (6)=9 \ p_3 (6)=7 \ p_2(6)=4 \ p_1(6)=1} {TEX}@@ (6)
این فهرست مشابه فهرست (3) است. به طور کلی درست است که {TEX()} { p_k(n) = q_k(n) } {TEX} . اکنون توجه خود را به بعضی از حالت‌های خاص معطوف می‌داریم که ببینیم چرا این رابطه برقرار است.
افرازهای 6 با سه جمع‌وند عبارت‌اند از:
(7)@@ {TEX()} {4+1+1,3+2+1,2+2+2} {TEX} @@
افرازهای 6 که بزرگترین جمع‌وند آنها 3 است عبارت‌اند از:
(8) @@ {TEX()} {3+1+1+1,3+2+1,3+3} {TEX} @@
برای اینکه ببینیم تساوی تعداد افرازهای فهرست‌های (7) و (8) (یعنی سه) تصادفی نیست، از آنچه نمودار افرازها نامیده شده است استفاده می‌کنیم. نمودار افراز{TEX()} {4+1+1} {TEX}عبارت است از:
::{picture=img/daneshnameh_up/8/8c/com0043a.jpg}::
به همین ترتیب نمودارهای {TEX()} {3+2+1} {TEX}و {TEX()} {2+2+2} {TEX}به صورت زیرند:
::{picture=img/daneshnameh_up/b/b2/com0043b.jpg}::
بنابراین نمودار یک افراز {TEX()} {n} {TEX}با {TEX()} {k} {TEX}جمع‌وند، صرفاً شامل k سطر از نقطه‌ها، هر سطر برای یک جمع‌وند است؛ سطری که بزرگترین جمع‌وند را نشان می‌دهد در بالا ظاهر می‌شود، نمایش بزرگترین جمع‌وند بعدی در زیر آن ظاهر می‌شود وقس علی هذا. تعداد سطرها برابر تعداد جمع‌وندها است، و تعداد نقطه‌ها در هر سطر برابر با اندازه هر جمع‌وند است. تعداد کل نقطه‌ها در نمودار یک افراز، مساوی {TEX()} {n} {TEX}است.
با عوض کردن سطرهای افقی و عمودی عکس نمودار به دست می‌آید. مثلاً
::{picture=img/daneshnameh_up/8/87/com0043c.jpg}::
عکس ((نمودار)) یک افراز {TEX()} {n} {TEX}، مجدداً نمودار یک افراز {TEX()} {n} {TEX}است. اگر نمودار اولیه افرازی با {TEX()} {k} {TEX}جمع‌وند را نشان دهد (یعنی دارای {TEX()} {k} {TEX}سطر باشد)، آن‌گاه عکس نمودار در اولین (بزرگترین) سطر دارای {TEX()} {k} {TEX}نقطه است و بنابراین افرازی با ماکسیمم جمع‌وند {TEX()} {k} {TEX}را نشان می‌دهد، مثلاً، افراز 12 به 4 جمع‌وند، یعنی {TEX()} {6+4+1+1} {TEX}، نمودار زیر را دارد.
:: {picture=img/daneshnameh_up/c/c0/com0043d.jpg}::
و نمودار عکس آن، یعنی
::{picture=img/daneshnameh_up/9/93/com0043e.jpg}::
افراز {TEX()} {4+2+2+2+1+1} {TEX}عدد 12 را نشان می‌دهد که بزرگترین جمع‌وند آن 4 است. بنابراین می‌توان تناظر یک به یکی را که بین نمودارها و نمودارهای عکس وجود دارد به عنوان یک تناظر یک به یک بین افرازهایی از {TEX()} {n} {TEX}با {TEX()} {k} {TEX}جمع‌وند و افرازهایی از {TEX()} {n} {TEX}با بزرگترین جمع‌وند {TEX()} {k} {TEX}تعبیر کرد. در نتیجه تعداد ((افراز))های {TEX()} {n} {TEX}به {TEX()} {k} {TEX}جمع‌وند با تعداد افرازهایی از {TEX()} {n} {TEX}((ماکسیمم)) جمع‌وند آنها مساوی {TEX()} {k} {TEX}است، برابر است.
به علاوه چون تعداد افرازهایی از {TEX()} {n} {TEX}به 1، یا 2، یا 3، … ، یا {TEX()} {k} {TEX}جمع‌وند مساوی با تعداد افرازهایی از {TEX()} {n} {TEX}است که ماکسیمم جمع‌وندهای آن برابر 1، یا 2، یا 3، …، یا {TEX()} {k} {TEX}است، می‌توان گفت:
تعداد افرازهایی از {TEX()} {n} {TEX}به {TEX()} {k} {TEX}یا کمتر از {TEX()} {k} {TEX}جمع‌وند، برابر با تعداد افرازهایی از {TEX()} {n} {TEX}است که بزرگترین جمع‌وند آنها از {TEX()} {k} {TEX}بزرگتر نیست؛ به صورت نمادی،
(9) @@ {TEX()} { q_k¬(n) = p_k(n) } {TEX} @@
این نتیجه برای حالت خاص{TEX()} { n = 6 } {TEX}در فهرست‌هایی از معادله‌های (3) و (6) تشریح شده است.
---
!!تعداد افرازها
تعداد افرازهای {TEX()} {n} {TEX}را با{TEX()} { p(n) } {TEX} ، و تعداد افرازهایی از {TEX()} {n} {TEX}را که دارای {TEX()} {k} {TEX}یا کمتر از {TEX()} {k} {TEX}جمع‌وند هستند با {TEX()} { q_k(n)} {TEX} و تعداد افرازهایی از {TEX()} {n} {TEX}را که جمع‌وندی بزرگتر از {TEX()} {k} {TEX}ندارند با{TEX()} { p_k(n) } {TEX} نشان دادیم. روابطی که تا حال به دست آمده‌اند عبارت‌اند از
(10) @@{TEX()} { p_k(n) = q_k(n) } {TEX} و {TEX()} { p(n) = q_n(n) = pn_(n)} {TEX} @@
برای محاسبه مقادیر عددی این افرازها، نتیجه دیگری را ثابت می‌کنیم:
(11)@@{TEX()} {p_k(n)=p_{k-1}(n)+p_k(n-k)} {TEX} @@
#@
@#16:
برای اثبات این رابطه به ازای ((اعداد صحیح)) {TEX()} {n} {TEX}و {TEX()} {k} {TEX}که در{TEX()} {1<k<n} {TEX} صدق می‌کنند،{TEX()} { p_k(n) } {TEX} ، یعنی افرازهایی از {TEX()} {n} {TEX}را که جمع‌وندی بزرگتر از {TEX()} {k} {TEX}ندارند به دو نوع تقسیم می‌کنیم:
الف.آنهایی که دارای جمع‌وند {TEX()} {k} {TEX}هستند؛
‌ب.آنهایی که جمع‌وند {TEX()} {k} {TEX}را ندارند.
ابتدا می‌بینیم که افرازهای نوع (ب) دقیقاً{TEX()} { p_{k - 1}(n) } {TEX} افراز از {TEX()} {n} {TEX}هستند که جمع‌وندی بزرگتر از {TEX()} { k - 1 } {TEX} ندارند. سپس توجه می‌کنیم که چون جمع‌وند {TEX()} {k} {TEX}حداقل یک بار در هر افراز از نوع (الف) ظاهر می‌شود، می‌توان از هر یک از افرازها یک جمع‌وند {TEX()} {k} {TEX}را برداشت. اگر این عمل را انجام دهیم، افرازهای حاصل دقیقاً افرازهای{TEX()} { n - k } {TEX} به جمع‌وندهایی هستند که بزرگتر از {TEX()} {k} {TEX}نیستند، و تعداد آنها برابر{TEX()} { p_k(n - k)} {TEX} است.
بنابراین (11) به ازای ((اعداد صحیح)) {TEX()} {n} {TEX}و {TEX()} {k} {TEX}، با شرط{TEX()} {1<k<n} {TEX} ثابت شده است.
برای روشن شدن این استدلال، حالت{TEX()} {n=6} {TEX} و {TEX()} {k=4} {TEX}را در نظر می‌گیریم، به قسمی که فرمول (11) به صورت {TEX()} { p_4(6) = p_3(6) + p_4(2)} {TEX} در می‌آید. تمام افرازهای عدد 6 در (1) بخش قبل فهرست شده‌اند. عدد 6 دارای نه افراز است که جمع‌وندی بزرگتر از 4 ندارند. بنابراین{TEX()} { p_4(6) = 9} {TEX} . این نه افراز به نوع (الف) آنهایی که دارای جمع‌وند 4 هستند، و نوع (ب) آنهایی که دارای جمع‌وند 4 نیستند، تقسیم می‌شوند:
::{picture=img/daneshnameh_up/9/9e/com0043f.jpg}::
افرازهای نوع (ب) تمام افرازهایی از 6 هستند که جمع‌وندی بزرگتر از 3 ندارند؛ تعداد اینها برابر{TEX()} { p_3(6) } {TEX} است. وقتی که جمع‌وند 4 را از هر افراز نوع (الف) برداریم، افرازهای{TEX()} {1+1} {TEX} و 2 به دست می‌آیند. تعداد اینها برابر{TEX()} { p_4(2) } {TEX} است، زیرا
@@{TEX()} { p_4(2) = p_2(2) = p(2) = 2 } {TEX}@@
فرمول (11) برای ((اعداد صحیح)) مثبت {TEX()} {k} {TEX}و {TEX()} {n} {TEX}که در رابطه{TEX()} {1<k<n} {TEX} صدق می‌کنند معتبر است. برای تشکیل جدولی از مقادیر{TEX()} { p_k(n) } {TEX}به مشاهداتی اضافی احتیاج داریم. ابتدا به ازای {TEX()} { k = 1 } {TEX} توجه می‌کنیم که:
(12)@@ به ازای تمام مقادیر {TEX()} { p_1(n) = 1 \qquad , n \ge 1} {TEX}@@
زیرا تنها یک افراز {TEX()} {n} {TEX}وجود دارد که جمع‌وندی بزرگتر از 1 ندارد. بعلاوه، افرازی برای {TEX()} {n} {TEX}وجود ندارد که جمع‌وندی بزرگتر از {TEX()} {n} {TEX}داشته باشد، بنابراین
(13) اگر{TEX()} {p_k(n)=p_n(n) \ , \ k\ge n} {TEX}
در حالت{TEX()} { n = 1} {TEX} ، رابطه بالا نتیجه می‌دهد که
@@{TEX()} {1 = p_1(1) = p_2(1) = p_3(1) = \cdots } {TEX}@@
همچنین تنها یک افراز برای {TEX()} {n} {TEX}وجود دارد که دارای جمع‌وند {TEX()} {n} {TEX}است و بنابراین
(14)@@ {TEX()} { p_n(n) = 1 + p_{n - 1}(n) } {TEX} @@
با استفاده از این نتایج، تشکیل جدول مقادیر{TEX()} { p_k(n) } {TEX}مطلب ساده‌ای است. برای شروع، به دلیل فرمول‌های (12) و (13) می‌توان یک ها را در اولین سطر افقی و اولین ستون عمودی قرار داد. آن‌گاه شاید برای ادامه عمل، بهترین راه این باشد که با استفاده از فرمول‌های (11) ، (13) و (14) ، مقادیر {TEX()} { p_2(n) } {TEX} به ازای
{TEX()} {n=2,3,4,\cdots} {TEX} ، سپس {TEX()} { p_3(n)} {TEX} به ازای{TEX()} {n=2,3,4,\cdots } {TEX} و سپس {TEX()} { p_4(n)} {TEX} به ازای {TEX()} {n=2,3,4,\cdots } {TEX} ، و غیره را در جدول قرار دهیم.
::{picture=img/daneshnameh_up/e/ee/com0043g.jpg}::
---
! پیوند های خارجی
[http://Olympiad.roshd.ir/computer/content/pdf/0034.pdf]
---
!همچنین ببینید
*((توزیع اشیا))
*((ترکیب ))
#@^