المپدیا

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

ابزار کاربر

ابزار سایت


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

سیگما

گاهی به عباراتی مانند $1 + 2 + ... + 100$ می‌رسیم که به صورت جمع تعدادی زیادی جمله‌ی مربوط به هم است. در ریاضیات نمادی به نام سیگما ($\sum$) برای ساده‌نویسی چنین عباراتی وجود دارد. در این صفحه با این نماد آشنا می‌شوید.


تعریف

فرض کنید دنباله‌ای به صورت $a_1, a_2, ..., a_n$ داریم. مجموع اعضای این دنباله ($a_1 + a_2 + ... + a_n$) را در نظر بگیرید. این جمع را می‌توان با نماد $\sum$ به صور زیر، ساده‌نویسی کرد: $$a_1 + a_2 + ... + a_n = \sum_{i=1}^{n}a_i$$

هم‌چنین اگر بخواهیم مجموع اعضای دنباله از عضو $s$-ام تا عضو $t$-ام ($a_s + a_{s+1} + ... + a_t$) را ساده‌نویسی کنیم، به صورت زیر از نماد $\sum$ استفاده می‌کنیم: $$a_s + a_{s+1} + ... + a_t = \sum_{i=s}^{t}a_i$$

در ساده‌نویسی‌های بالا، $i$، متغیر سیگماست. متغیر سیگما می‌تواند حروف دیگر نیز باشد. حتی می‌توانیم چند متغیر سیگما داشته باشیم که در ادامه خواهید دید.

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

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

  1. $$1+2+...+100$$
  2. $$f(1)+f(3)+...+f(2n-1)$$
  3. $$a_1 + 2a_2 + ... + na_n$$
  4. $$2+4+...+2n$$
  5. $$1+4+...+10000$$
  6. $$1 \times 1! + 2 \times 2! + ... + n \times n!$$
  7. $$1-\frac{1}{3}+\frac{1}{5}-...+\frac{1}{99}$$

پاسخ

  1. $$\sum_{r=1}^{100}r$$
  2. $$\sum_{i=1}^{n}f(2i-1)$$
  3. $$\sum_{k=1}^{n}ka_k$$
  4. $$\sum_{i=1}^{n}2i$$
  5. $$\sum_{i=1}^{100}i^2$$
  6. $$\sum_{i=1}^{n}i \times i!$$
  7. $$\sum_{i=1}^{50}(-1)^{i+1}\frac{1}{2i-1}$$

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

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

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

خواص سیگما

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

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

مجموع‌های نامتناهی

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

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

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

  1. $$\frac{1}{1} - \frac{1}{2} + \frac{1}{4} - ...$$
  2. $$...+a_{-2}x^{-2}+a_{-1}x^{-1}+a_0x^0 + a_1x^1 + a_2x^2 + ...$$

پاسخ

  1. $$\sum_{i=0}^{\infty}(-1)^{i}\frac{1}{2^i}$$
  2. $$\sum_{i=-\infty}^{\infty}a_ix^i$$

چند مثال

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

راهنمایی

ابتدا ثابت کنید: $$\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$$

پاسخ

ابتدا ثابت می‌کنیم: $$\frac{1}{k(k+1)}=\frac{1}{k}-\frac{1}{k+1}$$ داریم: $$\frac{1}{k} - \frac{1}{k+1} = \frac{k+1-k}{k(k+1)}=\frac{1}{k(k+1)}$$ حال حکم اصلی را با استفاده از قاعده‌ی ادغام، ثابت می‌کنیم: $$\sum_{i=1}^{n}\frac{1}{i(i+1)}$$ $$=\sum_{i=1}^{n}(\frac{1}{i}-\frac{1}{i+1})$$ $$=1 - \frac{1}{n+1}$$

مثال: عدد طبیعی $n$ را در نظر بگیرید. به ازای هر مقسوم‌علیه $n$ مانند $d$ مقدار $d!$ را حساب کرده و این فاکتوریل‌ها را با هم جمع می‌کنیم. به عدد حاصل، $f(n)$ می‌گوییم. برای مثال، $$f(4)=1!+2!+4!=27$$ مقدار $f(n)$ را با سیگما نشان دهید.

راهنمایی

برای تعیین حدود متغیر سیگما، از نماد شمردن یا عاد کردن (|) استفاده کنید. هر گاه، $a$ یک مقسوم‌علیه از $b$ باشد، گوییم $a$، $b$ را عاد می‌کند و با $a|b$ نشان می‌دهیم.

پاسخ

$$f(n)=\sum_{d|n} d!$$

مثال: فرض کنید $n$ یک عدد طبیعی به صورت $2^k$ باشد. ثابت کنید: $$1 + \frac{k}{2} \le \sum_{i=1}^{n}\frac{1}{i} \le k+1$$ سپس ثابت کنید: $$\sum_{i=1}^{\infty}\frac{1}{i} = \infty$$

پاسخ

$$H=\sum_{i=1}^{n}\frac{1}{i}=\frac{1}{1}+\frac{1}{2}+...+\frac{1}{n}$$ داریم: $$ \begin{array}{cc} 1 = \frac{1}{1} \le \frac{1}{1} \le \frac{1}{1} = 1\\ \frac{1}{2} = \frac{1}{2} \le \frac{1}{2} \le \frac{1}{1} = 1\\ \frac{1}{2}=\frac{1}{4} + \frac{1}{4} \le \frac{1}{3}+\frac{1}{4} \le \frac{1}{2} + \frac{1}{2} = 1\\ \frac{1}{2}=\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} \le \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} \le \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} = 1\\ ... \\ \frac{1}{2}=\underbrace{\frac{1}{2^{k}} + \frac{1}{2^{k}} + ... \frac{1}{2^{k}}}_{\text{تا } 2^{k-1}} \le \frac{1}{2^{k-1}+1} + \frac{1}{2^{k-1}+2} + ... + \frac{1}{2^k} \le \underbrace{\frac{1}{2^{k-1}} + \frac{1}{2^{k-1}} + ... \frac{1}{2^{k-1}}}_{\text{تا } 2^{k-1}} = 1 \end{array} $$ با جمع کردن نابرابری‌های بالا داریم: $$1 + \frac{k}{2} \le H \le k+1$$ و حکم ثابت می‌شود.

از همین روش، قسمت دوم مسئله را اثبات می‌کنیم: $$\sum_{i=1}^{\infty}\frac{1}{i} \ge (\frac{1}{1}) + (\frac{1}{2}) + (\frac{1}{4} + \frac{1}{4}) + (\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}) + ...$$ $$=1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + ... = \infty$$


یک پله بالاتر

خواص دیگری از سیگما

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

  • فرض کنید دو مجموعه‌ی $A$ و $B$ داریم که به ازای هر عضو $A$ مانند $x$، یک عضو از $B$ مانند $\sigma(x)$ متناظر شده باشد و این تناظر، یک به یک باشد. در این صورت: $$\sum_{y \in B} f(y) = \sum_{x \in A} f\big(\sigma(x)\big)$$
  • فرض کنید $f$ تابعی ناکاهشی (صعودی) و $g$ تابعی ناافزایشی (نزولی) باشد. با گرفتن مستطیل‌هایی با یک ضلع واحد، برای تقریب زدن انتگرال، داریم: $$\int_{a-1}^{b} f(s) ds \le \sum_{i=a}^{b}f(i) \le \int_{a}^{b+1}f(s) ds$$ و $$\int_{a}^{b+1} g(s) ds \le \sum_{i=a}^{b}g(i) \le \int_{a-1}^{b}g(s) ds$$

دنباله‌ی هارمونیک

دنباله‌ی $\frac{1}{1}, \frac{1}{2}, \frac{1}{3}, ...$ را در نظر بگیرید. به این سری، سری هارمونیک می‌گویند. مجموع اعداد این سری در مثال‌ها بررسی شد و به دست آمد که مجموع اعداد سری هارمونیک، تا عضو $n$-ام از $\theta(lg(n))$ و مجموع تمام اعضا، برابر $\infty$ است.

این سری کاربردهای بسیاری دارد. برای مثال در تحلیل پیچیدگی زمانی الگوریتم غربال اراتستن از این سری استفاده می‌شود.


منابع و مراجع


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

نظرات

حمید ضرابی‌زاده, 2016/10/30 23:36

kjh

حمید ضرابی‌زاده, 2016/10/30 23:34

حمید ضرابی‌زاده, 2016/10/30 23:34

sjsj

امیرحسین, 2016/02/10 00:52

سیگما یک عملی هست که جمع انجام میشه،یک علامت دیگه هم هست که کار سیگما رو انجام میده ولی به جای جمع ضرب میکنه،اسم اون علامت چیه؟

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

ابزار صفحه