یادداشت‌های فرکتالی
گام‌های کوچک در دل ساختارهای بزرگ ریاضی

مجموع توان‌ها با یک نگاه ترکیبیاتی

می‌خواهیم دوباره به مجموع

1k+2k+⋯+nk1^k + 2^k + \cdots + n^k

نگاه کنیم — این بار با یک ایده‌ی ترکیبیاتی.

ایده‌ی مرکزی

در بسیاری از اثبات‌های ترکیبیاتی، مسیر کار این است:

یک مجموعه پیدا کن
که تعداد اعضایش برابر با کمیتی باشد که می‌خواهی حساب کنی.
سپس همان مجموعه را به روشی دیگر بشمار.

به‌جای محاسبه‌ی مستقیم، می‌کوشیم چیزی را بشماریم.

یک مجموعه برای شمردن

مجموعه‌ی زیر را در نظر بگیرید:

S={(x,y,z)∣x,y,z∈{1,2,…,n+1},  x>y,  x>z}.S = \{(x,y,z)\mid x,y,z \in \{1,2,\dots,n+1\},\; x>y,\; x>z\}.

یعنی مجموعه‌ی تمام سه‌تایی‌های مرتب
که هر مؤلفه‌ی آن عددی بین 11 تا n+1n+1 است
و مؤلفه‌ی اول از هر دو مؤلفه‌ی دیگر بزرگ‌تر است.

به بیان ساده‌تر:

  • xx بزرگ‌ترین عضو سه‌تایی است،
  • و yy و zz می‌توانند هر عددی کوچک‌تر از xx باشند.

شمارش اول: تثبیتِ مؤلفه‌ی اول

بیایید مجموعه‌ی SS را با تثبیتِ مقدار xx بشماریم.

فرض کنید xx برابر عددی مشخص باشد. اگر x=mx=m باشد، چه انتخاب‌هایی برای yy و zz داریم؟

از آن‌جا که باید y<mوz<m,y < m \quad \text{و} \quad z < m, هر یک از yy و zz می‌توانند یکی از اعداد

{1,2,…,m−1}\{1,2,\dots,m-1\}

باشند.

برای yy، تعداد انتخاب‌ها برابر m−1m-1 است.
برای zz هم همین‌طور.

پس برای هر مقدار ثابتِ mm، تعداد سه‌تایی‌ها برابر است با:

(m−1)2.(m-1)^2.

حالا کافی است این را برای همه‌ی مقادیر ممکنِ xx جمع کنیم.

چون xx می‌تواند یکی از اعداد 11 تا n+1n+1 باشد، داریم:

∣S∣=∑m=1n+1(m−1)2.|S| = \sum_{m=1}^{n+1} (m-1)^2.

و با تغییر شاخص:

∣S∣=∑k=0nk2=∑k=1nk2.|S| = \sum_{k=0}^{n} k^2 = \sum_{k=1}^{n} k^2.

پس:

تعداد عناصر SS دقیقاً برابر مجموعِ مربع‌ها از ۱ تا nn است.

شمارش دوم: دو حالت برای yy و zz

حالا همان مجموعه‌ی SS را یک جور دیگر می‌شماریم.

در هر عضو SS داریم x>yx>y و x>zx>z. پس تنها رابطه‌ای که بین yy و zz ممکن است رخ دهد این است که:

  • یا yy و zz با هم متفاوت‌اند،
  • یا yy و zz برابرند.

پس SS را به دو بخشِ جدا تقسیم می‌کنیم و هر کدام را جدا می‌شماریم.

حالت اول: y≠zy \ne z

اگر yy و zz متفاوت باشند، آنگاه سه عدد x,y,zx,y,z همگی متفاوت‌اند (چون xx از هر دو بزرگ‌تر است و نمی‌تواند با آن‌ها برابر باشد).

پس کافی است سه عددِ متفاوت از مجموعه‌ی 1,2,…,n+1{1,2,\dots,n+1} انتخاب کنیم و سپس بزرگ‌ترینشان را به‌عنوان xx قرار دهیم.

برای انتخابِ سه عددِ متفاوت، تعداد انتخاب‌ها برابر است با:

(n+13).\binom{n+1}{3}.

اما برای هر انتخابِ سه‌تاییِ بدون ترتیب a,b,c{a,b,c}، دقیقاً دو عضو در SS می‌سازد:

  • بزرگ‌ترین عدد نقشِ xx را دارد،
  • دو عددِ کوچک‌تر می‌توانند به دو ترتیب ممکن جای yy و zz را بگیرند.

پس تعداد اعضای SS در این حالت برابر است با:

2(n+13).2\binom{n+1}{3}.

حالت دوم: y=zy = z

اگر y=zy=z باشد، آن‌گاه یک زوج (x,y)(x,y) داریم که باید x>yx>y باشد.

برای شمردن این حالت، کافی است دو عددِ متفاوت از 1,2,…,n+1{1,2,\dots,n+1} انتخاب کنیم. عدد بزرگ‌تر می‌شود xx و عدد کوچک‌تر می‌شود y=zy=z.

تعداد انتخاب دو عددِ متفاوت برابر است با:

(n+12).\binom{n+1}{2}.

پس تعداد اعضای SS در این حالت برابر است با:

(n+12).\binom{n+1}{2}.

نتیجه‌ی شمارش دوم

با جمع کردن دو حالت داریم:

∣S∣=2(n+13)+(n+12).|S| = 2\binom{n+1}{3} + \binom{n+1}{2}.

اما از شمارش اول داشتیم:

∣S∣=∑k=1nk2.|S| = \sum_{k=1}^{n} k^2.

پس نتیجه می‌گیریم:

∑k=1nk2=2(n+13)+(n+12).\sum_{k=1}^{n} k^2 = 2\binom{n+1}{3} + \binom{n+1}{2}.

(و اگر این عبارت را ساده کنیم، همان فرمول معروفِ n(n+1)(2n+1)6\frac{n(n+1)(2n+1)}{6} به‌دست می‌آید.)

جمع‌بندی

در این یادداشت، به‌جای محاسبه‌ی مستقیم مجموعِ مربع‌ها،

یک مجموعه ساختیم، آن را به دو روش متفاوت شمردیم، و از برابریِ این دو شمارش، فرمول را به‌دست آوردیم.

مسئله حل شد — اما مهم‌تر از جواب، الگویی بود که دیدیم:

یک کمیت را می‌توان با «طراحی یک مجموعه»
و «شمارش دوگانه» به‌دست آورد.

اکنون طبیعی است که بپرسیم:

آیا می‌توان همین ایده را برای مجموعِ مکعب‌ها هم به‌کار برد؟

گام بعد: مجموعِ مکعب‌ها

حالا می‌خواهیم با همان ایده، مجموعِ مکعب‌ها را حساب کنیم:

13+23+⋯+n3.1^3 + 2^3 + \cdots + n^3.

مثل قبل، به‌جای محاسبه‌ی مستقیم، یک مجموعه طراحی می‌کنیم که تعداد اعضایش دقیقاً همین مقدار باشد.

طراحی مجموعه

این بار، یک مجموعه‌ی چهارتایی در نظر می‌گیریم:

T={(w,x,y,z)∣w,x,y,z∈{1,2,…,n+1},  w>x,  w>y,  w>z}.T = \{(w,x,y,z)\mid w,x,y,z \in \{1,2,\dots,n+1\},\; w>x,\; w>y,\; w>z\}.

یعنی مجموعه‌ی تمام چهارتایی‌های مرتب از 1,2,…,n+1{1,2,\dots,n+1} که مؤلفه‌ی اول از هر سه مؤلفه‌ی دیگر بزرگ‌تر است.

به زبان ساده:

  • ww بزرگ‌ترین عضو چهارتایی است،
  • و x,y,zx,y,z هر سه باید عددی کوچک‌تر از ww باشند.

شمارش اول: تثبیتِ مؤلفه‌ی اول

مثل قبل، مقدار ww را ثابت می‌کنیم.

اگر w=mw=m باشد، هر یک از x,y,zx,y,z می‌تواند یکی از اعداد

{1,2,…,m−1}\{1,2,\dots,m-1\}

باشد؛ یعنی برای هر کدام m−1m-1 انتخاب داریم.

پس تعداد چهارتایی‌ها برای w=mw=m برابر است با:

(m−1)3.(m-1)^3.

اکنون برای همه‌ی مقدارهای ممکنِ ww جمع می‌زنیم:

∣T∣=∑m=1n+1(m−1)3=∑k=0nk3=∑k=1nk3.|T| = \sum_{m=1}^{n+1} (m-1)^3 = \sum_{k=0}^{n} k^3 = \sum_{k=1}^{n} k^3.

پس:

تعداد اعضای TT دقیقاً برابر مجموعِ مکعب‌ها از ۱ تا nn است.

حالا مثل قبل، سراغ شمارش دوم می‌رویم: این بار باید حالت‌بندیِ مناسب‌تری برای رابطه‌ی بین x,y,zx,y,z پیدا کنیم.

شمارش دوم: حالت‌بندیِ رابطه‌ی بین x,y,zx,y,z

حالا TT را یک جور دیگر می‌شماریم. سه حالت داریم:

حالت ۱: x,y,zx,y,z هر سه متفاوت‌اند

در این حالت چهار عدد w,x,y,zw,x,y,z همگی متفاوت‌اند و ww بزرگ‌ترینِ آن‌هاست.

پس ۴ عددِ متفاوت از 1,2,…,n+1{1,2,\dots,n+1} انتخاب می‌کنیم؛ بزرگ‌ترینشان را ww می‌گیریم و سه عددِ باقی‌مانده می‌توانند به 3!3! حالت جای x,y,zx,y,z بنشینند.

پس تعداد این حالت:

(n+14) 3!.\binom{n+1}{4}\,3!.

حالت ۲: دقیقاً دو تا برابرند

اینجا سه مقدارِ متمایز داریم: یکی برای ww و دو مقدار برای x,y,zx,y,z (یکی از آن‌ها تکرار می‌شود).

ابتدا ۳ عددِ متمایز از 1,2,…,n+1{1,2,\dots,n+1} انتخاب می‌کنیم؛ بزرگ‌ترینشان را به ww می‌دهیم.

دو عددِ باقی‌مانده را a<ba < b فرض کنید. اکنون باید تصمیم بگیریم:

  • کدام دو تا برابر باشند و کدام تنها باشد: 33 حالت (عضو تنها می‌تواند xx یا yy یا zz باشد)،
  • و این‌که مقدارِ تنها کدام‌یک از aa و bb باشد: 22 حالت.

پس تعداد این حالت:

(n+13)⋅3⋅2.\binom{n+1}{3}\cdot 3 \cdot 2.

حالت ۳: x=y=zx=y=z

فقط کافی است دو عددِ متفاوت از 1,2,…,n+1{1,2,\dots,n+1} انتخاب کنیم؛ بزرگ‌تر ww می‌شود و کوچک‌تر مقدار مشترک x=y=zx=y=z.

پس تعداد این حالت:

(n+12).\binom{n+1}{2}.

نتیجه‌ی شمارش دوم

پس داریم:

∣T∣=(n+14) 3!+(n+13) 3⋅2+(n+12).|T| = \binom{n+1}{4}\,3! + \binom{n+1}{3}\,3\cdot 2 + \binom{n+1}{2}.

اما از شمارش اول:

∣T∣=∑k=1nk3.|T|=\sum_{k=1}^{n} k^3.

پس:

∑k=1nk3=(n+14) 3!+(n+13) 3⋅2+(n+12).\sum_{k=1}^{n} k^3 = \binom{n+1}{4}\,3! + \binom{n+1}{3}\,3\cdot 2 + \binom{n+1}{2}.

و اگر این عبارت را ساده کنیم، دقیقاً می‌شود:

∑k=1nk3=(n(n+1)2)2.\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2.

تعمیم ایده: برای توان‌های بالاتر چه می‌شود؟

آن‌چه در دو مثالِ توانِ دو و سه انجام دادیم، یک الگوی مشترک داشت:

  • یک عددِ mrm^r را به‌صورت «تعداد انتخاب‌های یک rr-تایی» دیدیم،
  • سپس مجموعِ 1r+2r+⋯+nr1^r+2^r+\cdots+n^r را به‌صورت شمارشِ یک مجموعه‌ی بزرگ‌تر بازنویسی کردیم،
  • و بعد همان مجموعه را با یک طبقه‌بندی دیگر شمردیم.

برای توانِ سه، مجموعه‌ی ما این بود:

T={(w,x,y,z)∣w,x,y,z∈{1,…,n+1},  w>x,  w>y,  w>z},T=\{(w,x,y,z)\mid w,x,y,z\in\{1,\dots,n+1\},\; w>x,\;w>y,\;w>z\},

و کلِ ایده این بود که:

  • با تثبیتِ ww، تعداد انتخاب‌های (x,y,z)(x,y,z) برابر (w−1)3(w-1)^3 می‌شد،
  • و جمع روی همه‌ی wwها همان ∑k3\sum k^3 را می‌ساخت.

همین ساختار برای هر توانِ kk هم جواب می‌دهد.

نسخه‌ی کلی

برای عدد طبیعی kk، مجموعه‌ی زیر را در نظر بگیرید:

Tk={(w,a1,…,ak)∣w,a1,…,ak∈{1,…,n+1},  w>a1,…,w>ak}.T_k=\{(w,a_1,\dots,a_k)\mid w,a_1,\dots,a_k\in\{1,\dots,n+1\},\; w>a_1,\dots,w>a_k\}.

یعنی (k+1)(k+1)-تایی‌های مرتب که مؤلفه‌ی اول از همه‌ی مؤلفه‌های دیگر بزرگ‌تر است.

شمارش اول (همان قدمِ ثابت)

اگر w=mw=m باشد، هر یک از aia_iها می‌تواند یکی از اعداد 1,…,m−1{1,\dots,m-1} باشد؛ پس برای هر mm، تعداد انتخاب‌ها:

(m−1)k(m-1)^k

است.

بنابراین:

∣Tk∣=∑m=1n+1(m−1)k=∑t=1ntk.|T_k| = \sum_{m=1}^{n+1}(m-1)^k = \sum_{t=1}^{n} t^k.

پس دوباره یک مجموعه پیدا کردیم که اندازه‌اش دقیقاً همان مجموع توان‌هاست.

شمارش دوم (ایده‌ی اصلی)

در شمارش دوم، به‌جای تثبیتِ ww، روی الگوی تکرارها در (a1,…,ak)(a_1,\dots,a_k) تمرکز می‌کنیم:

  • چند مقدارِ متمایز بین aia_iها ظاهر شده؟
  • هر مقدار چند بار تکرار شده؟
  • و جایگاهِ این تکرارها چند جور می‌تواند چیده شود؟

به این ترتیب TkT_k به چند دسته تقسیم می‌شود: دسته‌هایی که هر کدام با «تعداد انتخابِ چند عددِ متمایز» و «تعداد چینش‌های ممکن» شمرده می‌شوند.

این همان چیزی است که در توانِ سه دیدیم: (سه حالت: همه متفاوت، دو تا برابر، همه برابر) و برای kkهای بزرگ‌تر، حالت‌ها فقط بیشتر می‌شوند (الگوهای تکرار متنوع‌تر می‌شوند).