ضریب دو جمله ای

مدیران انجمن: parse, javad123javad

ارسال پست
نمایه کاربر
rohamavation

نام: roham hesami radرهام حسامی راد

محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2

عضویت : سه‌شنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴


پست: 3222

سپاس: 5492

جنسیت:

تماس:

ضریب دو جمله ای

پست توسط rohamavation »

ضریب دو جمله ای برای نشان دادن تعداد راه های ممکن برای انتخاب زیرمجموعه ای از اشیاء با تعداد معین از یک مجموعه بزرگتر استفاده میشه . به این دلیل نامیده می شود ضرایب انبساط توان

${\displaystyle {\tbinom {n}{k}}.}$ ضریب عبارت xk در بسط چند جمله‌ای توان دوجمله‌ای (1 + x)n است.
${\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\ times \cdots \times 1}},}$
که با استفاده از نمادگذاری فاکتوریل اینطور نمایش میدم
${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$
و ضریب دو جمله ای$(x+y)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{n-k}y^{k}$من میخوام $\frac{\binom{n}{1}}{1} + \frac{\binom{n}{2}}{2} + \frac{\binom{n}{3}}{3} + \cdots + \frac{\binom{n}{n}}{n} = \sum_{r=1}^{n}\frac{2^r-1}{r}$میدونم $\displaystyle {n-1\choose k} + {n-1\choose k-1} = {n\choose k}$اجازه بدین$\displaystyle S_n = \sum_{r=1}^{n} \frac{1}{r}{\binom{n}{r}}$ و توجه داشته باشین که (با تعریف) $\displaystyle {n-1\choose n} =0.$پس $\begin{aligned} \sum_{r=1}^{n} \frac{1}{r}{\binom{n}{r}} & = \sum_{r=1}^{n} \frac{1}{r}{n-1\choose r} + \sum_{r=1}^{n}\frac{1}{r}{n-1\choose r-1} \\& = \sum_{r=1}^{n-1} \frac{1}{r}{n-1\choose r} + \sum_{r=1}^{n}\frac{r}{r \cdot n}{n\choose r} \\& = \sum_{r=1}^{n-1} \frac{1}{r}{n-1\choose r} + \frac{1}{n}\sum_{r=1}^{n}{n\choose r} \\& = \sum_{r=1}^{n-1} \frac{1}{r}{n-1\choose r} + \frac{2^n-1}{n} \\& = \frac{2^n-1}{n} +S_{n-1}\end{aligned}$کار با این رابطه بازگشتی، با $S_0 = 0$ من دارم$\begin{aligned} S_n & = \frac{2^n-1}{n}+S_{n-1} \\& = \frac{2^{n}-1}{n}+\frac{2^{n-1}-1}{n-1}+S_{n-2} \\& = \frac{2^{n}-1}{n}+\frac{2^{n-1}-1}{n-1} + \cdots + \frac{2^{1}-1}{1} +S_0 \\& = \sum_{r=1}^{n} \frac{2^r-1}{r}\end{aligned}$همچنیتن $\displaystyle \int_{0}^{1}{\frac{(1 + x) ^ {n} - 1}{x}}dx = \sum_{r=1}^{n}\frac{2^r-1}{r}$بینید $\displaystyle (1+x)^n-1 = \sum_{r=1}^{n}x^r \binom{n}{r}$و $\begin{aligned} \sum_{r=1}^{n}\frac{2^r-1}{r} & = \int_{0}^{1}{\frac{(1 + x) ^ {n} - 1}{x}} \, \mathrm dx \\& = \int_{0}^{1}\frac{1}{x} \sum_{r=1}^{n} x^r \binom{n}r \, \mathrm dx \\& = \int_{0}^{1} \sum_{r=1}^{n} x^{r-1} \binom{n}r \, \mathrm dx \\& = \sum_{r=1}^{n} \int_{0}^{1}x^{r-1} \binom{n}r \, \mathrm dx \\& = \sum_{r=1}^{n} \frac{1}{r} \binom{n}r.\end{aligned}$
یه مثال دیگه ${1 - \frac{1}{2} {n \choose 1} + \frac{1}{3} {n \choose 2} + \ldots + (-1)^n \frac{1}{n+1} {n \choose n}}$خوب راحته $\sum_{k=0}^{n}\frac{(-1)^{k}}{k+1}\binom{n}{k}.$سپس هر جمله را در $\frac{n+1}{n+1},$ ضرب کردم و نیجه من
$\sum_{k=0}^{n}\frac{(-1)^{k}}{n+1}\binom{n+1}{k+1}=\frac{1}{n+1}\sum_{k=1}^{n+1}(-1)^{k-1}\binom{n+1}{k}.$با قضیه دو جمله ایbinomial theorem من میام اینطور مینویسم $\frac{1}{n+1}-\frac{1}{n+1}\sum_{k=0}^{n+1}\binom{n+1}{k}(-1)^{k}1^{n+1-k}=\frac{1}{n+1}(1-(1-1)^{n+1})=\frac{1}{n+1}.$یک راه دیگه $\begin{align}
S&=1-\frac 12\binom n1+\frac 13 \binom n2-\cdots+(-1)^n\frac 1{n+1}\binom nn\\
\times (n+1):\hspace{1cm}\\
(n+1)S&=(n+1)-\frac {n+1}2\binom n1+\frac {n+1}3\binom n2-\cdots+(-1)^n\frac {n+1}{n+1}\binom nn\\
&=\binom {n+1}1-\binom {n+1}2+\binom {n+1}3-\cdots +(-1)^n\binom {n+1}{n+1}\\
&=\color{blue}{\binom {n+1}0}\underbrace{\color{blue}{-\binom {n+1}0}+\binom {n+1}1-\binom {n+1}2+\binom {n+1}3-\cdots +(-1)^n\binom {n+1}{n+1}}_{=-\sum_{r=0}^{n+1}\binom {n+1}r(-1)^r=-(1-1)^{n+1}=0}\\
&=1\\
S&=\color{red}{\frac 1{n+1}}
\end{align}$ بزارم اشاره کنم HINT ${1 - \frac{1}{2} {n \choose 1} + \frac{1}{3} {n \choose 2} + \ldots + (-1)^n \frac{1}{n+1} {n \choose n}}.=\sum_{j=0}^{n} \frac{(-1)^j}{j+1} \binom n j$
$\sum_{j=0}^{n} \frac{(-1)^j}{j+1} x^{j+1} \binom n j =\int \sum_{j=0}^{n} (-1)^j x^{j}\binom n j =\int (1-x)^n=- \frac { (1-x)^{n+1}} {n+1}$
با WLOG و اشاره HINT مطالب من براساس قضیه دو جمله‌ای می‌توانم مقدار عدد e یا «عدد اویلر» (Euler’s Number) را پیدا کنم$\large (x+\frac{1}{n})^n=\sum_{k=0}^n{ n \choose k}1^{n-k}(\frac{1}{n})^k=\sum_{k=0}^n{ n \choose k}(\frac{1}{n})^k$خوب چون $1^{n-k}=1$ اونو حذف کردم ین رابطه را زمانی که n به سمت بی‌نهایت میل می‌کنه محاسبه کنم$\large \sum_{k=0}^n \dfrac{n!}{k!(n-k)!}.\dfrac{1}{n^k}$ من در حقیقت به دنبال حد در بی‌نهایت این تابع برحسب n هستم$\large \sum_{k=0}^n \dfrac{n!}{k!(n-k)!}.\dfrac{1}{n^k}$وقتیکه N به سمت بینهایتinfinity میل کنه $n\rightarrow \infty$در نهایت ${\displaystyle e=\sum _{n=0}^{\infty }{\frac {1}{n!}}={\frac {1}{0!}}+{\frac {1}{1!}}+{\frac {1}{2!}}+{\frac {1}{3!}}+{\frac {1}{4!}}+\cdots ,}$
با پایتون یا محاسبه عدد پی $\pi =\sum_{m=1}^{\infty}\frac{(-1)^{s(m)}}{m},$برنامه میدوارم خوشتون بیاد
برنامه خودم را برای محاسبه pi بنویسم. من از پایتون و فقط از اعداد صحیح استفاده کردم (نمی خواستم از اعداد ممیز شناور استفاده کنم) و از الگوریتم Gauss-Legendre استفاده کردم زیرا ساده ترین برای پیاده سازی بود (من در نظر داشتم از الگوریتم Borwein استفاده کنم، اما نمی خواستم سوم را محاسبه کنم. ریشه اعداد، و الگوریتم Chudnovsky کمی پیچیده به نظر می رسید اگرچه شاید من آن را امتحان کنم). می‌خواهم بدانم الگوریتم‌های بالا، در O(n) چقدر کارآمد هستند.$# Calculate next square root approximation of the number.
def calculate_next_square_root(number, square_root):
next_square_root = ((number / square_root) + square_root) / 2
return next_square_root

# Calculate the square root of the number.
def calculate_square_root(number, digits, add):
# Start with 1, followed by (digits + add) zeros.
square_root = 1 * (10 ** (digits + add))
# Calculate next square root approximation of the number.
next_square_root = calculate_next_square_root(number=number, square_root=square_root)
while (next_square_root != square_root):
# Replace square root with next square root.
square_root = next_square_root
# Calculate next square root approximation of the number.
next_square_root = calculate_next_square_root(number=number, square_root=square_root)
return square_root

# Calculate next pi approximation.
def calculate_next_pi(a, b, t, digits, add):
next_pi = ((10 ** (digits + add)) * ((a + b) ** 2)) / (4 * t)
return next_pi

# Calculate pi to 5,000 digits.
digits = 5000
add = 500
a = 10 ** (digits + add)
b = calculate_square_root(number=(10 ** ((digits + add) * 2)) / 2, digits=digits, add=add)
t = (10 ** ((digits + add) * 2)) / 4
p = 1
pi = -1 # pi must be different than next_pi
next_pi = calculate_next_pi(a=a, b=b, t=t, digits=digits, add=add)
n = 0
while (next_pi != pi):
pi = next_pi
next_a = (a + b) / 2
next_b = calculate_square_root(number=a * b, digits=digits, add=add)
next_t = t - (p * ((a - next_a) ** 2))
next_p = 2 * p
a = next_a
b = next_b
t = next_t
p = next_p
next_pi = calculate_next_pi(a=a, b=b, t=t, digits=digits, add=add)
n += 1

# Remove the last 500 digits.
pi /= (10 ** add)

# Print the results.
print pi
print n$برنامه من 52 خط کد (شامل نظرات) می گیره، و من علاقه ای به برنامه هایی ندارم که برای پیاده سازی خطوط زیادی نیاز دارند
تصویر

ارسال پست