What is more, partitions of the number $N$ into at most $k$ terms, or partitions of the number $N + k$ into exactly $k$ terms? We consider partitions that differ only in order to be the same. Looks like pretty easy combinatorial problem, but I have no idea that should work here. I tried draw , and build some bijections. As I know, there no any formula for finding number of partitions, so I need some more ideas/hints for this problem
110857
How do I see that the number of partitions of the integer $n$ into at most $r$ positive integers is equal to the number of partitions of $n + r$ into exactly $r$ positive integers?
90324
Show that the number of combinations of $n$ letters out of $3n$ letters of which $n$ are $a$s , $n$ are $b$s and the rest are unequal is $(n+2)2^{n-1}$.   My approach...  The number of ways of distributing $n$ distict object in $k$ distinct box is $\binom{n+k-1}{k-1}$ now when $k=2$ the logic stands as $\binom{n+2-1}{2-1}$=$\binom{n+1}{1}$.  Selection of $j$ distinct letter out of $n$ is $\binom{n}{j}$.  Hence my answer will be $\sum_{j=0}^{n} \binom{j+1}{1}\binom{n}{n-j}$.  Please help me with the answer
119250
Given a set of whole numbers of size $n$, how many unique combinations of these whole numbers are there?   For example, for the set $\{1,2,3\}$ the unique combinations are   $\{1,2,3\}, \{1,2\}, \{1\}, \{2\}, \{3\}, \{2,3\}, \{1,3\}$   The number of combinations for $\{1,2,3\}$ is $7$.  Does this generalize to the number of unique combinations in a set is $2^n-1$ where $n$ is the number of elements in the set?
17496
How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$?  The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at most $M$, is given by the generating function: $$  \binom{M+k}{k}_{x} = \prod_{j=1}^{k}\frac{1-x^{M+k-j+1}}{1-x^j}= \sum_{n=0}^{kM} p_{k}(\leq M,n) x^n $$  For the number of the partitions $p_k(\mathcal{D},n)$ of $n$ into at most $k$ parts there is the recurrence relationship: $$   p_{k}(\mathcal{D},n) = p_{k}(\mathcal{D},n-k) + p_{k-1}(\mathcal{D},n) $$  But what, if I want to count only the partitions with distinct parts and restricted number of parts and restricted part size?  Update: Now I know the generating function for the number of distinct restricted partitions $p_k(\leq M, \mathcal{D},n)$ of $n$ into exactly $k$ distinct parts, all at most $M$ is $$    \prod_{j=1}^{M} (1+xq^{j}) = \sum_{k,n=0}^{\infty}p_k(\leq M, \mathcal{D},n)x^{k}q^{n} $$ and there is also a recurrence relation $$    p_k(\leq M, \mathcal{D},n) =         p_{k-1}(\leq M-1, \mathcal{D},n-k) +         p_k(\leq M-1, \mathcal{D},n-k) $$ How can I prove this? Could you recommend a book, where I could read about this?
54052
I would appreciate if somebody could help me with the following problem  Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$  $$\sum _{k=0}^n (n-2 k)^2 \binom{n}{k}=n\times  2^n$$
24187
Hello everybody! The problem you see above is a combinatorial problem that I could not solve. :(  Since we are to choose distinct numbers from $\{1,2,3 \ldots K\}$, the numbers must be in increasing order because they are all positive. I think that the difficulty of this problem is in the fact that the Special Sequence can be of any length. We can go about choosing say $n$ elements in $\binom{K}{n}$ ways but again how do we control that? Talking about a recursive solution, I think that is the way to go but I can't get how to do that (that is get a recursive formula for that).  Any help in solving this problem would be much appreciated. Thanks.
83255
This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics]  Problem: Let $S$ be a a non-empty subset of $\{1,2,\ldots,2n\}$. It is clear that if $|S|$ is "enough large" then, independently from the choice of $S$, there are for sure some distinct $a,b \in S$ such that $a$ divides $b$.  Then, what is the maximal $k$ such that, for some $S$ with cardinality $k$, if $a,b$ are distinct members of $S$ then $a$ does not divide $b$?  [Ps. I know the solution]
118355
How can you show that $\binom {n}{7}=\sum_{k=7}^n \binom {k-1} {6}$?   This counts the number of subsets from $\{1,2,3,\dots,n\}$ having size $7$. To me, the summation part counts subsets of size $6$. Can someone please tell me how this is done?  P.S. I don't know how to edit in the proper way.
39445
Given n distinct objects, there are $n!$ permutations of the objects and $n!/n$ "circular permutations" of the objects (orientation of the circle matters, but there is no starting point, so $1234$ and $2341$ are the same, but $4321$ is different).  Given $n$ objects of $k$ types (where the objects within each type are indistinguishable), $r_i$ of the $i^{th}$ type, there are   \begin{equation*} \frac{n!}{r_1!r_2!\cdots r_k!} \end{equation*}  permutations.  How many circular permutations are there of such a set?
54510
I think there are $\binom{b+ c - 1}{c-1}$ ways to distribute $b$ balls in $c$ containers. (Please correct me if that's a mistake.) How does this change if I am not allowed to place more than $n$ balls in any given container?  If we call this number $N(b,c,n)$ then I can come up with  $$N(b,c,n) = \sum_{k=0}^n N(b-k, c-1, n)$$  with the base cases  $$N(b,c,n) = \binom{b+ c - 1}{c-1}$$  for $n\geq b$, and  $$N(b,c,n) = 0$$  for $n&lt;b/c$.  Is there some better way of writing this than that recursion relation?
75668
I have trouble coming up with combinatorial proofs. How would you justify this equality?  $$ n\binom {n-1}{k-1} = k \binom nk $$ where $n$ is a positive integer and $k$ is an integer.
15056
I have n objects and k boxes, each box has its own size.  The arrangement of objects in a box doesn't matter. How many combinations are there, respectively the formula?  Say we have 7 objects and 3 boxes with sizes of 2, 3 and 4. The solution is 6, the same result appears (it has to appear) when we place the gaps [(2+3+4)-7=2]  The multinomial coefficient only considers (I think so) the case when a box has to contain a specific number of objects, so the result is wrong:  $$ \frac{7!}{2!\cdot 3!\cdot 4!} = 17.5 \not= \frac{2!}{2!\cdot 3!\cdot 4!} = \frac{1}{144} $$ But what's the correct formula?
110348
Could anyone provide me with a nice proof that the  $\leq$ on partitions of an integer $n$ satisfies the following: if $\lambda, \tau$ are 2 partitions of $n$, then $\lambda \leq \tau \Longleftrightarrow \tau &#39; \leq \lambda &#39;$, where $\lambda&#39;$ is the conjugate partition of $\lambda$ (i.e. the transpose of the set of 'dots' which $\lambda$ represents).   I feel like there must be a nice clever and concise/intuitive proof of this, but all I can come up with is an ugly brute force approach based on the definition of sums of the components $\lambda_i$. Could anyone suggest a particularly nice way to obtain this result? Many thanks.
90529
$S(n, k)$ count the number of ways to partition a set of $n$ elements into $k$ nonempty subsets. What if there were duplicate elements in the set? That is, the set is a ?
46860
Let $M$ be the set $\{1,2,3\}$. How many Equivalence relations $R \subset M \times M$ exists?  My idea is to count the disjoint partitions of M:  $K_1= \{\{1\},\{2\},\{3\}\}\Leftrightarrow\{(1,1),(2,2),(3,3)\}$  $K_2= \{\{1,2\},\{3\}\} \Leftrightarrow\{(1,1),(1,2),(2,1),(2,2),(3,3)\} $  $K_3=  \{\{1,3\},\{2\}\}\Leftrightarrow\{(1,1),(1,3),(3,1),(2,2),(3,3)\}$  $K_4= \{\{1\},\{2,3\}\}\Leftrightarrow\{(1,1),(2,3),(3,2),(2,2),(3,3)\}$  $K_5=\{1,2,3\}\Leftrightarrow K_5=M^2$  So the answer would be $5$. Is this correct? Reflexivity and Symmetry are obvious, but how can i check the right side for Transitivity?
25736
I need some advice as I am struggling with the following combinatorics exercise.  Let $k$ be a given positive integer. Show that any non-negative integer $N$ can be written uniquely in the form $$N=\binom{x_k}{k}+\binom{x_{k-1}}{k-1}+\dots+\binom{x_1}{1},$$ where $0 \leq x_1 &lt; \dots &lt; x_{k-1} &lt; x_k$.  The exercise is accompanied by this advice:  Let $x$ be such that $\binom{x}{k} \leq N &lt; \binom{x+1}{k}$. Then any possible representation has $x_k = x$. Now use induction and the fact that $N-\binom{x}{k} &lt; \binom{x}{k-1}$ to show the existence and uniqueness of the representation.  I am really stuck and thus grateful for the slightest hint on how to solve it.
95326
I'm trying to figure out a combinatorial proof for:  $$\displaystyle \sum_{k \mathop = 0}^n \binom {r+k} k = \binom {r + n + 1} n$$  I've tried the committee counting thing, but that didn't work.