المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:پای

پای

گاهی به عباراتی مانند $1 \times 3 \times ... \times 101$ می‌رسیم که به صورت ضرب تعدادی زیادی جمله‌ی مربوط به هم است. در ریاضیات نمادی به نام پای ($\prod$) برای ساده‌نویسی چنین عباراتی وجود دارد. در این صفحه با این نماد آشنا می‌شوید.


تعریف

فرض کنید دنباله‌ای به صورت $a_1, a_2, ..., a_n$ داریم. ضرب اعضای این دنباله ($a_1 \times a_2 \times ... \times a_n$) را در نظر بگیرید. این ضرب را می‌توان با نماد پای ($\prod$) به صورت زیر، ساده‌نویسی کرد: $$\prod_{i=1}^{n}a_i$$ هم‌چنین اگر بخواهیم ضرب اعضای دنباله از عضو $s$-ام تا عضو $t$-ام ($a_s \times a_{s+1} \times ... \times a_t$) را ساده‌نویسی کنیم، به صورت زیر از نماد $\prod$ استفاده می‌کنیم: $$a_s \times a_{s+1} \times ... \times a_t = \prod_{i=s}^{t}a_i$$ در ساده‌نویسی‌های بالا، $i$، متغیر پای است. متغیر پای می‌تواند حروف دیگر نیز باشد. حتی می‌توانیم چند متغیر پای داشته باشیم که در ادامه خواهید دید.

در ساده‌نویسی‌های بالا، به ازای $i$-های مختلف، ضرب تعدادی از جمله‌های دنباله را ساده‌نویسی کرده‌ایم. حدود $i$ نیز در بالا و پایین پای مشخص می‌شود. ساده‌نویسی‌های بالا، مرسوم‌ترین روش‌های ساده‌نویسی با نماد $\prod$ هستند که در آن، حدود $i$ از یک عدد (در پایین پای) تا یک عدد دیگر (در بالای پای) است. روش‌های زیاد دیگری نیز برای ساده‌نویسی با پای وجود دارد که در ادامه خواهید دید.

مثال: عبارات زیر را با پای ساده‌نویسی کنید:

  1. $$1 \times 2 \times ... \times 100$$
  2. $$f(1) \times f(3) \times ... \times f(2n-1)$$
  3. $$a_1 \times 2a_2 \times ... \times na_n$$
  4. $$2 \times 4 \times ... \times 2n$$
  5. $$1 \times 4 \times ... \times 10000$$
  6. $$n^{e^0} \times n^{e^1} \times ... \times n^{e^n}$$
  7. $$(1-\frac{1}{4}) \times (1 - \frac{1}{9}) \times ... \times (1 - \frac{1}{n^2})$$

پاسخ

  1. $$\prod_{i=1}^{100}i$$
  2. $$\prod_{i=1}^{n}f(2i-1)$$
  3. $$\prod_{i=1}^{n}ia_{i}$$
  4. $$\prod_{i=1}^{n}2i$$
  5. $$\prod_{i=1}^{100}i^2$$
  6. $$\prod_{i=0}^{n}n^{e^i}$$
  7. $$\prod_{i=2}^{n}(1 - \frac{1}{i^2})$$

روش‌های دیگر ساده‌نویسی با پای

تمام ساده‌نویسی با $\prod$، به صورتی که گفته شد، نیست. روش‌های دیگری نیز وجود دارد. در زیر، برخی از آن‌ها را می‌بینید:

  • گاهی نیازی نیست حدود متغیر پای را مشخص کنیم؛ یعنی پایین و بالای $\prod$ چیزی نمی‌نویسیم. این به معنای آن است که به ازای تمام حالت‌های متغیر پای، عبارت جلوی پای را حساب کرده و ضرب می‌کنیم. برای مثال، اگر دنباله‌ای مانند $a_1, a_2, ..., a_n$ داشته باشیم، عبارت $$\prod a_i$$ به معنای ضرب تمام اعضای دنباله است.
  • گاهی حدود متغیر را به روشی دیگر، مشخص می‌کنیم. برای مثال، برای ساده‌سازی عبارت $f(0) \times f(1) \times ... \times f(100)$ می‌توان از عبارت $$\prod_{0 \le k \le 100} f(k)$$ استفاده کرد. به عنوان مثالی دیگر، عبارت زیر به معنای آن است که به ازای تمام عضوهای مجموعه‌ی $S$ مانند $x$، مقدار $2^x$ را حساب می‌کنیم و این مقادیر را با هم ضرب می‌کنیم: $$\prod_{x \in S} 2^x$$
  • گاهی چند متغیر پای داریم. برای مثال، برای ساده‌سازی عبارت $$f(1, 1) \times f(1, 2) \times ... \times f(1, 10) \times f(2, 1) \times f(2, 2) \times ... \times f(2, 10) \times f(10, 1) \times f(10, 2) \times ... \times f(10, 10)$$ از عبارت $$\prod_{1 \le x, y \le 10}f(x, y)$$ استفاده می‌کنیم.
  • می‌توان پای‌های تو در تو استفاده کرد. مثلن عبارت $$f(1, 1) \times f(1, 2) \times ... \times f(1, 10) \times f(2, 1) \times f(2, 2) \times ... \times f(2, 10) \times f(10, 1) \times f(10, 2) \times ... \times f(10, 10)$$ را می‌توان با عبارت $$\prod_{i=1}^{10}\sum_{j=1}^{10}f(i, j)$$ ساده‌سازی کرد. عبارت ساده‌شده‌ی بالا به آن معناست که به ازای هر $i$ از ۱ تا ۱۰، عبارت $\prod_{j=1}^{10}f(i, j)$ حساب شود و این مقادیر با هم ضرب شوند.

خواص پای

پای، خواصی دارد که برخی از آن‌ها در زیر آمده است. توجه کنید که نیازی نیست این خواص را حفظ کنید؛ زیرا اکثر این خواص بدیهی هستند و هنگام ساده‌نویسی و کار با پای، به راحتی به ذهن می‌رسند. این خواص صرفن جهت آشنایی در زیر نوشته شده‌اند:

  • از آن جایی که $$f(s) \times f(s+1) \times ... \times f(b) \ \ \times \ \ f(b+1)\times f(b+2)\times ... \times f(t)=f(s)\times f(s+1)\times ...\times f(t)$$ پس $$\prod_{i=s}^{b}f(i) \times \prod_{i=b+1}^{t}f(i)=\prod_{i=s}^{t}f(i)$$
  • فرض کنید $c$، یک عدد ثابت باشد. از آن‌جایی که $$\big(c \times f(s)\big) \times \big(c \times f(s + 1)\big) \times ... \times \big(c \times f(t)\big) = c^{t-s+1} \times \big(f(s) + f(s+1) \times ... \times f(t) \big)$$ پس $$\prod_{i=s}^{t}\big(c \times f(i)\big) = c^{t-s+1} \prod_{i=s}^{t} f(i)$$ در واقع می‌توان ضریب ثابت را از پای بیرون کشید.
  • از آن جایی که $$f(s)\times f(s+1)\times ... \times f(t)\ \ + \ \ g(s) \times g(s+1) \times ... \times g(t)= \big(f(s)\times g(s)\big) \times \big(f(s+1)\times g(s+1)\big) \times ... \times \big(f(t)\times g(t)\big)$$ پس $$\prod_{i=s}^{t}f(i) \times \prod_{i=s}^{t}g(i)=\prod_{i=s}^{t}\big(f(i) \times g(i)\big)$$ در واقع گاهی به روش بالا می‌توان دو پای را ادغام کرد.
  • از آن‌ جایی که $$\frac{f(s+1)}{f(s)} \times \frac{f(s+2)}{f(s+1)} \times ... \times \frac{f(t+1)}{f(t)} = \frac{f(t+1)}{f(s)}$$ پس $$\prod_{i=s}^{t}\frac{f(i+1)}{f(i)} = \frac{f(t+1)}{f(s)}$$ به این قاعده، قاعده‌ی ادغام می‌گویند.
  • می‌توان متغیر پای را مقداری انتقال داد. در واقع: $$\prod_{i=s}^{t}f(i)=\prod_{i=s+p}^{t+p}f(i-p)$$
  • در پای‌های تو در تو، گاهی می‌توان جای دو پای را عوض کرد. در واقع: $$\prod_{x}\prod_{y}a_{x,y}=\prod_{y}\prod_{x}a_{x, y}$$

ضرب‌های نامتناهی

در تمام مثال‌ها و روش‌های ذکر شده، سیگما را برای ساده‌سازی تعداد متناهی جمله به کار بردیم. گاهی می‌توان سیگما را برای ساده‌سازی تعداد نامتناهی جمله نیز به کار برد.

فرض کنید دنباله‌ای مانند $a_1, a_2, ...$ داریم. عبارت $a_1 \times a_2 \times ...$ را می‌توان با $$\prod_{i=1}^{\infty}a_i$$ ساده‌نویسی کرد. همانند ضرب‌های متناهی، روش‌های ساده‌نویسی با پای و خواص پای را می‌توان برای ضرب‌های نامتناهی نیز به کار برد.

مثال: عبارت زیر را با پای ساده‌نویسی کنید:

  1. $$...+e^{-2}x^{-2}+e^{-1}x^{-1}+e^0x^0 + e^1x^1 + e^2x^2 + ...$$

پاسخ

  1. $$\prod_{i=-\infty}^{\infty}e^ix^i$$

چند مثال

مثال: عدد طبیعی $n$ را در نظر بگیرید. به ازای هر مضرب طبیعی از $n$ مانند $m$، مقدار $e^{(\frac{m}{n})^{-m}}$ را حساب کرده و این مقادیر را در هم ضرب می‌کنیم. به عدد حاصل، $f(n)$ می‌گوییم. مقدار $f(n)$ را با پای نشان دهید.

پاسخ

$$\prod_{i=1}^{\infty}{e}^{i^{-(i \times n)}}$$

مثال: ثابت کنید: $$\prod_{i=2}^n (1 - \frac{1}{i^2}) = \frac{n+1}{2n}$$

راهنمایی

ابتدا ثابت کنید: $$1 - \frac{1}{k^2} = \frac{k-1}{k} \times \frac{k+1}{k}$$

پاسخ

ابتدا ثابت می‌کنیم: $$1 - \frac{1}{k^2} = \frac{k-1}{k} \times \frac{k+1}{k}$$ داریم: $$\frac{k-1}{k} \times \frac{k+1}{k} = \frac{k^2 - 1}{k^2} = 1 - \frac{1}{k^2}$$ حال حکم اصلی را ثابت می‌کنیم: $$\prod_{i=2}^n (1 - \frac{1}{i^2})$$ $$ = \frac{1}{2} \times \frac{3}{2} \times \frac{2}{3} \times \frac{4}{3} \times ... \times \frac{n-1}{n} \times \frac{n+1}{n}$$ با ساده کردن داریم: $$\prod_{i=2}^n (1 - \frac{1}{i^2}) = \frac{1}{2} \times \frac{n+1}{n}$$ $$ = \frac{n+1}{2n}$$


یک پله بالاتر

خواص دیگری از پای

پای خواصی دیگر نیز دارد که برخی از آن‌ها در زیر آمده است:

  1. فرض کنید دو مجموعه‌ی $A$ و $B$ داریم که به ازای هر عضو $A$ مانند $x$، یک عضو از $A$ مانند $\sigma(x)$ متناظر شده باشد و این تناظر، یک به یک باشد. در این صورت: $$\prod_{y \in B}f(y) = \prod_{x \in A}f(\sigma(x))$$
  2. از آن جایی که $a^{b+c} = a^b \times a^c$، رابطه‌ی زیر بین سیگما و پای، برقرار است: $$c^{\sum_{i=s}^{t}f(i)} = \prod_{i=s}^{t}c^{f(i)}$$
  3. از آن جایی که $$log(x \times y) = log(x) + log(y)$$ رابطه‌ی زیر بین سیگما و پای برقرار است: $$log_b\Big(\prod_{i=s}^{t} a_i \Big) = \sum_{i=s}^t log_b(a_i)$$ اگر $b$ (پایه‌ی لگاریتم) را به توان دو طرف تساوی بالا برسانیم، ثابت می‌شود که با استفاده از رابطه‌ی زیر یا روابط شبیه به آن، می‌توان هر عبارت ساده‌ نوشته شده با پای را، به عبارتی ساده‌نوشته شده با سیگما تبدیل کرد: $$\prod_{i=s}^{t}f(i) = b^{\sum_{i=s}^{t}log_bf(i)}$$ در عبارات بالا، $b$ می‌تواند اعداد مختلفی باشد و در جاهای مختلف به کار رود. معمولن در عبارات و قضایای ریاضی، از پایه‌ی $e$ و در علوم کامپیوتر و الگوریتم‌ها، از پایه‌ی ۲ استفاده می‌شود. $log_e$ را با نماد $ln$ و $log_2$ را با نماد $lg$ (بخوانید لاگ) نیز نشان می‌دهند. به عنوان مثالی از کاربرد در الگوریتم‌ها، داریم: $$lg(n!) = \sum_{i=1}^{n}lg(i)$$ این رابطه در تحلیل پیچیدگی الگوریتم‌های مرتب‌سازی مبتنی بر مقایسه کاربرد دارد.

منابع و مراجع


خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید:

نظرات

نظر خود را وارد کنید. دستورات ویکی مجاز است:
 

ابزار صفحه