I'm self studying discrete math from a books which states the formula for No of ways of selecting r objects from n distinct objects, allowing repeated selections as  $C(n+r-1, r)$. I couldn't understand completely how they derived this formula. Could someone please explain this to me?  Kindly also do give some examples to help me understand how to use this formula.  The book is elements of discrete mathematics by KC liu and DP mohapatra
121514
The formula for computing a k-combination with repetitions from n elements is: $$\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}$$  I would like if someone can give me a simple basic proof that a beginner can understand easily.
109886
I have to give a combinatorial proof of  $$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$  I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have algorithms to solve most problems. Usually I won't just "see" solutions unless I have a thorough enough understanding of a theory. This is also the case here. I know what the symbols mean, but I don't see what I should count and how to obtain the identity.  I think the right-hand side counts $n$-element subsets of a $(2n-1)$-element set with one element chosen to be "special". I think I should find a partition of the set of such subsets into $n$ parts so that the left-hand side is the sum of the cardinalities of the parts. Is there $n$ of anything on the right-hand side? Well, there are $n$ choices for the "special" elements, but only after I've chosen the $n$-element subset. Otherwise I can choose the "special element" in $2n-1$ ways.  This is a homework problem so I probably shouldn't ask for a full solution. But I would like to have some guidelines for approaching such problems, perhaps based on this example.
94802
I'm trying to find a way to calculate a problems such as this: if you have $n$ objects and $k$ indistinguishable boxes, how do you put in $n$ objects such that each box has no more than $C$, where $C \le k$.  For example, I have $6$ objects that need to be placed in $4$ boxes, where no box can have more than $4$ objects in it. I tried $\displaystyle\binom{n+k-1} {k-1}$. I got $84$ ways. But that is too big. When I do it by hand, I get $74$.   Would like actual explanation.
104161
I came across this formula in a list:  The number of ways of distributing $n$ identical objects among $r$ groups such that each group can have $0$ or more $(\le n)$ objects  I know that standard way of doing this is to solve the problem of distributing n identical objects and $(r-1)$ partitions among themselves which can be done in $C(n+r-1,r-1)$ ways.   But I am unable to prove to myself why it is not $(r+1)^n$.  Because each of the n objects has r+1 choices, either group1, group2,... group r or none at all.
116996
What is the number of ways we can choose three letters from $\{A,B,...,Z\}$ if repetition is allowed?      This is not a permutation.  Is there any formula to solve this kind of problems?
50733
The question I am stuck on is 'how many ways can I choose $n$ balls from $3n$ balls, with $n$ indistinguishable black balls, $n$ indistinguishable white balls, and $n$ distinguishable coloured balls.'   I have been thinking about this problem for some time but can't get very far, I am used to questions about just distinguishable or indistinguishable objects, but I am not familiar with a problem involving both.  I think that there are $n+2$ 'colours' where within the colours all the balls are indistinguishable, but I don't really know where to go from there so any hints would be much appreciated.
27796
I read many articles on the derivation of the derangement formula but I can't understand them clearly. At first I read . I understand the recursive derivation of derangement. But I am interested in understanding the inclusion-exclusion based formula for derangements.
68990
Sample $k$ times with order from $n$ distinct numbers with replacement where $k\ge n$. Here "with order" means the sample is treated like a sequence rather than a set, so results like "1,3,3" and "3,1,3" are different.  The question is what is the probability that every number is sampled at least once? My answer is $1-\frac{{\sum\limits_{i = 1}^n {C_n^i\times i! \times {{(n - i)}^k}} }}{{{n^k}}}$ where $C_n^i$ denotes $n$ chooses $i$.  ${C_n^i\times i! \times {{(n - i)}^k}}$ means first choose $i$ ($i=1,2,...,n-1$) of numbers not to appear in the sample, and then we sample from the remaining $n-i$ numbers for $k$ times.   My question is, is there more elegant solution where the numerator can be directly computed? i.e. can we directly calculate the number of possible sample sequences in which every number has at least one occurrence? Thank you!    PS: my attempt was $C_k^n\times n!\times n^{n-k}$, meaning that we first choose $n$ positions in the sequence of length $k$ to place $n$ numbers, and then permute the $n$ numbers. This is to ensure every number to appear once. The remaining $n-k$ are sampled from the $n$ numbers without restriction.   However, I later found this seems not correct, and it counts the same sequence multiple times.  PS2: as pointed out in the comments, my first answer "1- ..." is not correct either.
97505
Help finding a combinatorial proof of $k {n \choose k } = n {n - 1 \choose k -1}$  I have expanded it this far:  $$\frac{k \cdot n!}{k!(n-k)!} = \frac{n \cdot (n-1)!}{(k-1)!(n-k)!} $$  but then I am stuck from where to go from there.
87966
Let $x_1, \ldots ,x_n$ be distinct points in $\Bbb{R}^d$. Prove that there is a permutation $\sigma$ of $[n]$ such that the $\angle x_{\sigma(i−1)}x_{\sigma(i)}x_{\sigma(i+1)} &lt; \pi/2$ for any $i = 2,\ldots, n−1$.  So I have got this question, and I am not able to understand what &quot;a permutation $\sigma$ of $[n]$&quot; mean? Can someone explain to me this question and provide some hints to approach it? P.S. I have edited out some parts as it was a bit irrelevant.
31652
Problem:  If a set $A$ has $n$ elements in it, how many reflexive relations can be defined on it?  My solution  Is the answer  summation of (n^2 - n)C(i)  for i=0 to n^2 -n  $$\sum_{i=0}^{n^2-n} C(n^2-n,i) = \sum_{i=0}^{n^2-n} \binom{n^2-n}i$$  How? well if i make a matrix $n\times n$  now the diagonal elements have to be selected,out of remaining $n^2-n$ any number of elements can be selected.
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.
41538
What is the number of ways to select ten distinct letters from the alphabet $\{a, b, c, \ldots, z\}$, if no two consecutive letters can be selected?   There are a couple of formulas that I could use, but I am not sure how to use them.     The number of combinations of a given length that use elements from a given set, allowing repetition and with no missing elements in other words, each element of the given set occurs at least once in each combination: $\binom{k-1}{n-1}$ where where $n$ is the number of elements in the given set and $k$ is the length of the combination.   OR     The number of combinations of a given length that use elements from a given set, allowing repetition: $\binom{n+k-1}{n-1}=\binom{n+k-1}{k}$ where $n$ is number of elements in the given set and $k$ is the length of the combination.   Please help me understand what I should do and how to go about solving this question?
43812
Let's say I have numbers each taken in a set $A$ of $n$ consecutive naturals, I ask myself : how can I found what are all the unique multisets, which could be created with $k$ elements of this set $A$?  For example I've got $A=[1,2,\dots,499]$. If I wanted to create unique multiset of 3 elements, I would search all the multisets $\{a,b,c\}$ such as $a\leq b\leq c$ and then have all the unique multisets. As such for each elements $a$ there is $499-(a-1)=500-a$ possibilities for $b$ and $500-b$ possibilities for $c$. Unfortunately I'm stumped here and can't find the number of possible combination, as I didn't do any maths for years. I know that I should have some kind of product, but I don't know how to find the product anymore.  So first, I would like to know if I am right in my original assumption, or if I am looking in the wrong direction. Second I would like to approach that as if I were doing an homework, as I would like to understand the logic behind it: What would be the formula to give the numbers of multisets of $k$ elements from a set $A$ of $n$ consecutive naturals?  P.S. I'm totally new to math.SE, as such, I'm not sure I tagged the post appropriately.
12882
Assume that there are an arbitrarily large number of copies of ten diﬀerent discrete math books (which we will call titles) for cmsc250. Each student must choose one title as the course text book. Assume that the ﬁve hundred students taking the course are indistiguishable.  How many diﬀerent ways can the students choose titles, if Epp must be chosen by at most twenty students?   I understand that this is a stars and bars problem where the formula would be ${n+r-1}\choose{r-1}$, but whats throwing me off is the "at most" parameter of the problem. My answer is ${480+9-1}\choose{9-1}$ My reasoning was that we now have one less "bar", and that should be shown by lowering $r$ by 1  Am I approaching this the right way?
40845
I wrote the two methods below to automatically select N distinct colors. It works by defining a piecewise linear function on the RGB cube. The benefit of this is you can also get a progressive scale if that's what you want, but when N gets large the colors can start to look similar. I can also imagine evenly subdividing the RGB cube into a lattice and then drawing points. Does anyone know any other methods? I'm ruling out defining a list and then just cycling through it. I should also say I don't generally care if they clash or don't look nice, they just have to be visually distinct.  public static List&lt;Color&gt; pick(int num) {     List&lt;Color&gt; colors = new ArrayList&lt;Color&gt;();     if (num &lt; 2)         return colors;     float dx = 1.0f / (float) (num - 1);     for (int i = 0; i &lt; num; i++) {         colors.add(get(i * dx));     }     return colors; }  public static Color get(float x) {     float r = 0.0f;     float g = 0.0f;     float b = 1.0f;     if (x &gt;= 0.0f &amp;&amp; x &lt; 0.2f) {         x = x / 0.2f;         r = 0.0f;         g = x;         b = 1.0f;     } else if (x &gt;= 0.2f &amp;&amp; x &lt; 0.4f) {         x = (x - 0.2f) / 0.2f;         r = 0.0f;         g = 1.0f;         b = 1.0f - x;     } else if (x &gt;= 0.4f &amp;&amp; x &lt; 0.6f) {         x = (x - 0.4f) / 0.2f;         r = x;         g = 1.0f;         b = 0.0f;     } else if (x &gt;= 0.6f &amp;&amp; x &lt; 0.8f) {         x = (x - 0.6f) / 0.2f;         r = 1.0f;         g = 1.0f - x;         b = 0.0f;     } else if (x &gt;= 0.8f &amp;&amp; x &lt;= 1.0f) {         x = (x - 0.8f) / 0.2f;         r = 1.0f;         g = 0.0f;         b = x;     }     return new Color(r, g, b); }
10211
Could somebody explain to me where these two formulas come from as applications of the binomial theorem?  $$\sum_{k=0}^n {n \choose k}(-1)^kk^r=0$$ for non-negative integers $r\lt n$. And $$\sum_{k=0}^n {n \choose k}(-1)^kk^n=(-1)^nn!$$