i am having some trouble trying to understand this simple formula:  $\frac{n!}{\left(n-r!\right)r!}$   Even though i am able to solve exercises easily using this formula i can't understand it. How was this formula derived? Is it possible to understand the formula or is it just the result of some certain mathematical work?  The part that i don't understant is how does diving the possible combinations by the redundancies result in the possible number of arragements of something ignoring order.
122842
I perfectly understand the permutations formula i.e. if you have $n$ things how many ways can you rearrange it if taken $k$ at a time (or if you have $k$ slots)? So you draw the following tree. And the formula comes out naturally. $$^nP_k = \frac{n!}{(n-k)!}$$  I get that it is including all of the duplicates, too. And to get rid of them we use the combinations formula: $$^nC_k = \frac{n!}{k!(n-k)!}$$ Can somebody explain why we have to divide by the &quot;number of ways to re-arrange the slots&quot; to get rid of the duplicates? I understand that it works and the division is used to scale a number down but I am not getting that &quot;aha moment&quot; of why we do it. Can somebody explain it?
121952
My question is this : how many distinct two digit numbers can be produced from numbers $4, 3, 3, 1$? When applying the formula $$\frac{4!}{(4-2)!2!}$$ you come up with $6$, yet when doing the problem manually, I come up with $7$ numbers, namely $41, 43, 14, 13, 33, 31, 34$. Can anybody explain this discrepancy?  Thanks.
33275
Can someone reverse this formula? Sorry if it's too basic, I'm an old guy and my math is rusty :-D  $s =\frac{n(n+1)}{2}$  If it ain't clear, by reverse I mean obtaining the value of n by providing s  Thanks
30867
I know that the formula for counting the number of ways in which $n$ indistinguishable balls can be distributed into $k$ distinguishable boxes is $$\binom{n + k -1}{n}$$  but I am having a hard time understanding why this formula counts that. I mean, suppose we have $4$ boxes and $3$ balls, then the problem is equivalent to count the permutations of  5 vertical lines with 3 circles except that two lines have to be fixed (the first and last lines). I would appreciate if someone could help me to relate and translate this way of thinking the problem to the formula with this. Thanks in advance.
10799
The simple inequality that $\left(\frac{n}{k}\right)^k \leq \binom{n}{k}$ has a number of different proofs. But is there a particularly intuitive, short and elegant proof that uses the natural interpretation of binomial coefficients, for example. I would ideally like a proof which is also accessible to students with very limited prerequisite knowledge.  Here is the best proof that I have seen which is less intuitive than I was hoping for.  First we first prove that $$\frac{n-i}{k-i} \geq \frac{n}{k}$$  for $i&lt;k\leq n$.  This follows from  $$0\leq (n-k)i = k(n-i) - n(k-i) =  k(k-i)\left(\frac{n-i}{k-i}-\frac{n}{k}\right),$$ and $k(k-i)&gt; 0$, so $(n-i)/(k-i) \geq n/k.$  Now we multiply the over $i\in\{1,\ldots,k-1\}$ to obtain  $$\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots 1} \geq \frac{n^k}{k^k},$$ or equivalently $\binom{n}{k}\geq (n/k)^k$.
2521
Let's have 2 numbers, N and K, where K divides N. The number of K-combinations from a given set S of N elements is a well known formula. Let's concatenate N/K groups (resulting in N elements) such as the resulting set is N. How many possibilities are there, i.e. what's the formula?  For instance:    N=4, K=2, C(4, 2) = 6 {1,2},{1,3},{1,4},{2,3},{2,4},{3,4}   The 3 possibilities are:     {1,2},{3,4}   {1,3},{2,4}   {1,4},{2,3}   I generated these combinations and I think the number goes like this:  (4, 2): 3 (6, 3): 10 (6, 2): 15 (10, 5): 126 (9, 3): 280 (10, 2): 945 (14, 7): 1716 (12, 4): 5775 (15, 5): 126126 (15, 3): 1401400   Apparently, the result always divides with (N-1).
57035
If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below:  $$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$  What if I want to go the other way around though?  That is, I know I want to have $X$ possible combinations, and I want to find all the various pairs of $n$ and $k$ that will give me that number of combinations.  For example, if the number of combinations I want is $3$, I want a formula/method to find that all the pairs that will result in that number of combinations are $(3,1)$ and $(3,2)$  I know I could test all the possible pairs, but this would be impractical for large numbers.  But perhaps there's no easier way of doing this then the brute force approach?
15451
Regarding the formula for binomial coefficients:  $$\binom{n}{k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$$  the professor described the formula as first choosing the $k$ objects from a group of $n$, where order matters, and then dividing by $k!$ to adjust for overcounting.  I understand the reasoning behind the numerator but don't understand why dividing by $k!$ is what's needed to adjust for overcounting. Can someone please help me understand how one arrives at $k!$? Thanks.
66635
Let $r$ be an integer greater than $2$.  Is there a simple way of showing that $2^r$ divides  $\left(\begin{array}{c}  {2}^{r-2} \\ k \end{array}\right) 2^{2k}$  but it does not divide $\left(\begin{array}{c} 2^{r-l} \\ k \end{array}\right) 2^{2k}$ for $l&gt;2$ and for all $k$ greater than $0$ and less or equal than $2^{r-2}$?  Equivalently, is there a simple way of showing that the element $5$ has order $2^{r-2}$ in the group of units of the ring $\mathbb{Z}_{2^r}$?  The two questions are connected by writing $5 = 4 + 1$ and using the binomial expansion formula to study the order of $5$.
33587
Prove that $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}  $  Thanks in advance, my professor asked us to this a couple weeks ago, but I was enable to get to the right answer.   Good luck!  Here is what I got up to;  $\frac{(n+1)!}{(n-r)!(r+1)!} = \frac{(n)!}{(r)!(n-r)!} + \frac{(n)!}{(r+1)!(n-r-1)!}    $
114797
Question is to Evaluate :  $$\frac{1}{3}+\frac{1}{4}\frac{1}{2!}+\frac{1}{5}\frac{1}{3!}+\dots$$  what all i could do is :  $$\frac{1}{3}+\frac{1}{4}\frac{1}{2!}+\frac{1}{5}\frac{1}{3!}+\dots=\sum_{n=1}^{\infty} \frac{1}{(n+2)n!}=\sum_{n=1}^{\infty} \frac{n+1}{(n+2)!}=\sum_{n=1}^{\infty} \frac{n}{(n+2)!}+\sum_{n=1}^{\infty} \frac{1}{(n+2)!}$$  I have $$\sum_{n=1}^{\infty} \frac{1}{(n+2)!}=\sum_{n=0}^{\infty} \frac{1}{n!}-1-\frac{1}{2}=e-\frac{3}{2}$$  Now, I am not able to see what $$\sum_{n=1}^{\infty} \frac{n}{(n+2)!}$$ would be.  I would be thankful if some one can help me to clear this.  Thank you.
2022
I am trying to prove a formula (for ways of distributing $n$ identical balls among $r$ persons when each person may get any number of balls) ${n+r-1}\choose{r-1}$. But I am not able to prove it. I may be doing something wrong but I am not able to figure out what exactly?  This is what I am doing.  I put $n$ identical balls in a line. Now there are $(n+1)$ spaces/gaps between these $n$ identical things including (left to the leftmost ball and the next to the rightmost ball). So now basically I just need to select any $(r-1)$ gaps from these $(n+1)$ gaps and I will be able to create $r$ groups.   So, my answer is ${n+1}\choose{r-1}$.  But the actual answer to this is ${n+r-1}\choose{r-1}$ as per   I want to know what am I doing wrong? Thanks!
50174
Let $a,b,c\in\mathbb{R}^*_+$, $abc=1$.  How can i show that $\left(a-1+\frac{1}b\right)\left(b-1+\frac{1}c\right)\left(c-1+\frac{1}a\right)\leq1$ ?  I got $\left(ab-b+1\right)\left(bc-c+1\right)\left(ca-a+1\right)\leq abc=1$, but i can't go any further ...  If i expand it :   $2-ab-\frac{b}a-c-ac-\frac{a}c-b+2a+\frac{2}a-bc-\frac{c}b-a+2b+\frac{2}b+2c+\frac{2}c-4$  Which gives using $c=\frac{1}{ab}$ :   $5ab-\frac{b}a-\frac{1}{ab}-a^2b+\frac{1}a+b+\frac{1}b-2$
120175
I want to justificate following equation:  $$\sum_{k=0}^n \frac{(-1)^k}{k!(n-k)!}\frac{1}{2k+1} = \frac{2^n}{(2n+1)!!}$$  I calculated the both sides for $n$ from 1 to 10 and it was true. How the mathematical induction can be applied to this equation? Or is there other way to justificate it?
25198
For each $n$ consider the expression $$\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$  I am trying to prove by induction that this is an integer for all $n$.  In the base case $n=1$, it ends up being $1$.   I am trying to prove the induction step:   if $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$ is an integer, then so is $\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right]$.   I have tried expanding it, but didn't get anywhere.
20091
Video states that a corollary of the Rational Root Theorem is that $\left(\frac{a}{b}\right)^n != 2$ for integers $a,b,n$, where $n \gt 1$.  I'm simply looking for a proof by contradiction of this.  I started of by assuming $\left(\frac{a}{b}\right)^n = 2$, but couldn't arrive at a contradiction.  (I'm probably very close).  Any ideas?  I got to: $n(\log a - \log b) = \log 2 = 0.30102..$
3540
I don't know what to do with this. Nothing works. I hope somebody can help me to find a decision $$n!\leq {\left(\frac{n+1}{2}\right)}^{n}$$