ثابت کردن نسبت فاکتوريل ها در رياضيات گسسته دوازدهم

اثبات رابطه بین فاکتوریل‌ها

برای اثبات رابطه $ n!m!|(n+m)! $، ابتدا مفهوم فاکتوریل را مرور می‌کنیم. فاکتوریل یک عدد طبیعی $k$، که با $k!$ نشان داده می‌شود، برابر است با حاصل‌ضرب همه اعداد طبیعی کوچکتر یا مساوی $k$.

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

• فاکتوریل $n!$ شامل همه اعداد طبیعی از $1$ تا $n$ است.
• فاکتوریل $m!$ شامل همه اعداد طبیعی از $1$ تا $m$ است.
• فاکتوریل $(n+m)!$ شامل همه اعداد طبیعی از $1$ تا $n+m$ است.

برای اینکه نشان دهیم $ n!m! $ $(n+m)!$ را عاد می‌کند، کافی است نشان دهیم که هر عاملی که در $n!$ و $m!$ وجود دارد، در $(n+m)!$ نیز وجود دارد و تعداد آن حداقل به همان اندازه است.

همه عوامل اول موجود در $n!$ و $m!$، در $(n+m)!$ نیز وجود دارند زیرا $(n+m)!$ شامل همه اعداد تا $n+m$ است.

برای اثبات دقیق‌تر، می‌توان تعداد دفعات حضور هر عامل اول $p$ را در فاکتوریل‌ها بررسی کرد. طبق لم لژاندر، تعداد دفعات حضور $p$ در $k!$ برابر است با:
$v(k!)=\sum _{i\ge 1}\left[\frac{k}{p^i}\right]$
که در آن $[x]$ نشان‌دهنده جزء صحیح $x$ است.

برای اینکه $ n!m! $، $(n+m)!$ را عاد کند، باید داشته باشیم:
$v(n!)+v(m!)\le v\left(\right(n+m)!)$
برای هر عامل اول $p$. این رابطه با استفاده از لم لژاندر و خاصیت جزء صحیح قابل اثبات است.

بنابراین، $ n!m!|(n+m)! $ برای هر $n$ و $m$ طبیعی برقرار است.