Prove that the number of permutations of $m$ A's and at most $n$ B's equals $\dbinom{m+n+1}{m+1}$.  I'm not sure how to even start this problem.
70000
I have to prove that:     $$\sum_{k=0}^{n} {{m+k} \choose{m}} = { m+n+1 \choose m+1 }$$   I tried to open up the right side with Pascal's definition that: $$ { n \choose k} = {n-1 \choose {k}} + {n-1 \choose {k-1}}$$  Here is what I came up with, and I am sure it is wrong because it does not equal the left side:  $$ {m+n+1 \choose m+1} = {m+n \choose m+1} + {m+n \choose m} = ... ={m+n \choose m+1} + {m+n-1 \choose m} + {m+n-2 \choose m-1} + ... + {m \choose m+1} = \sum_{k=0}^{n} {m+k \choose m+k-n+1 }  $$  Which, again, probably is wrong because it is not equal $\sum_{k=0}^{n} { m+k \choose m}$. Any help is appreciated
99159
I didn't understand the permutation and of course, I got this question wrong.     Compute the inverse of the following permutation:   $$ \begin{pmatrix}  1&amp;2&amp;3&amp;4&amp;5&amp;6\\ 2&amp;5&amp;4&amp;1&amp;6&amp;3 \end{pmatrix} $$   Could you please help me with this question and provide an explanation?  Furthermore, is it possible to compute the direct permutation, not the inverse one? If yes, how?  Thank you in advance!
67163
In $S_n$ with n=10, find a permutation $a$ such that $axa^{-1} = y$ if $x=(1,2)(3,4)$ and $y=(5,6)(3,1)$  I don't know how to start doing this. I read something like I need to get, for this case, $$(a(1),a(2)) \qquad \mbox{ and} \qquad (a(3),a(4))$$ but I am not sure where will I get their equivalents. Also, will those be my permutation $a$? Please help. I have problems very similar to this.
118782
Prove that on average, n-permutations have $H_n$  cycles, where $H_n=1+1/2+1/3+...+1/n$  without mathematical induction.   I think that on average, the number of cycles of length i (1≤i≤n) should be 1/i to prove but, I don't know how to show this. Some books proved this using an indicator function. Do I have to use that?
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
89895
Let $n_1 &lt; n_2 &lt; n_3 &lt; n_4 &lt; n_5$ be positive integers such that $n_1 + n_2 + n_3 + n_4 + n_5 = 20$. Then the number of such distinct arrangements $(n_1, n_2, n_3, n_4, n_5)$ is...... I have no idea how to proceed. Manually, I have done it $$1+2+3+4+10$$ $$1+2+3+5+9$$ $$1+2+3+6+8$$ $$1+2+4+5+8$$ $$1+2+4+6+7$$ $$1+3+4+5+7$$ $$2+3+4+5+6$$ But is there any way I can do it by Permutation and Combination method?
64270
Let n be an odd integer and let f be an [n]-permutation of length n, where [n] is the set of integers 1, 2, 3,...n  Show that the number   x = (1-f(1))*(2-f(2))*...*(n-f(n))   is even using the pigeonhole principle  In this case, I don't understand what this function f is. What is an [n]-permutation of length n? Take f(2) for example. Permutations of [2] would be 1,2 and 2,1. So the way the problem is worded, f(2) must equal 12 or 21. If that's correct, which one? Will this number x still be even regardless of which [n]-permutation f(n) is?
81669
If $m, n$ be positive integers, prove that $\phi(mn)=\phi((m,n))\phi([m,n])$, where $(m,n)=$ gcd of $m, n$ and $[m, n]=$ lcm of $m, n$.   I have no idea to solve this question. Please help me to solve the problem.
115288
To find the number of three letter words that can be formed from the word 'SERIES', with or without meaning and without repetition.   The number of permutations if all letters were distinct  = $^{6}P_3$.    As 'S' and 'E' are repeating, the arrangement in which 'S' are interchanged are the same, so we divide by $2!$ for 'S' and likewise for 'E'.    Number of permutations $= \frac{^{6}P_3}{2!.2!} = 30$   Which isn't the correct answer. I would like to get some help here.
95005
Let $T_n$ be the set of permutations of $\{1,2,\ldots,n\}$ which do not have $i$ immediately followed by $i+1$ for $1\le i\le n-1$; in other words, let \begin{align} T_n=\{\sigma \in S_n: \sigma(i)+1\ne\sigma(i+1) \text{ for all } 1\le i\le n-1\} . \end{align} Let $Q_n$ be the number of elements of $T_n$.    Let $D_n$ be the number of  of $\{1,2,\ldots,n\}$.  It is not hard to show algebraically that $Q_n=D_n+D_{n-1}$, but I am having difficulty coming up with a combinatorial argument to show why this is true.  (I believe there are $D_{n-1}$ elements of $T_n$ that leave $n$ fixed, and $D_n$ elements of $T_n$ that move $n$, but I don't know how to justify this combinatorially.)
40340
Prove that for any positive integers $m$ and $n$ , there exists a set of $n$ consecutive positive integers each of which is divisible by a number of the form $d^m$, where $d$ is some positive integer not equal to $1$.  I don't know how to approach this question.
88833
Today my friend asked me following question:  Consider the set $ A= \{1,2,3,4,5\}$ By using the elements of this set, can you find a permutation that neither has an increasing sequence of length 3, nor has a decreasing sequence of length 3?  for example:   $3,4,2,1,5$ has an increasing sequence of length $3$, namely $3,4,5$   $5,3,1,2,4$ has a decreasing sequence of length $3$, namely $5,3,2$  I feel like I cannot find such a sequence. I guess problem is that this set has 5 elements and therefore I cannot create such a sequence. If it had 4 elements, I would find lots of sequences with that property. (With the same number of elements, length 4 would be OK too.) But how can I prove it to him? Could you please explain to me?  Best Regards
82857
I accidentally found that $9^n\equiv 9\pmod{24} \quad \forall n \in \Bbb N^*$ But don't know how to prove it in an exact way. Please help
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?
123711
How do I prove by a combinatorial argument that ${{n}\choose{k}} {{k}\choose{j}} = {{n}\choose{j}} {{n-j}\choose{k-j}}$
102177
I'm back again So there's another problem that I can't get to prove  If we take 21 numbers randomly from $1, 2, 3, ..., 40$ then between those $21$ numbers we will be able to find two numbers, of which the smaller one will divide the bigger one  I've been reading james hein "discrete structures, logic and computability" but still can't get to think logically myself. I would be very grateful if I could get some directions/tips/hints or anything, thanks in advance
79585
Let $[n]$ denote the set $\{1,2,\ldots,n\}$.  We call a permutation $\sigma:[n]\to[n]$, $(n,k$)-nearly sorted if  $$\forall i\in [n]: |\sigma(i) - i|\le k,$$  i.e., every element is shifted at most $k$ places compared to the identity permutation.     How many $(n,k)$-nearly sorted permutations exist?     For example, 5 $(4,1)$-nearly sorted permutations exist:   (1,2,3,4) (2,1,3,4) (1,2,4,3) (2,1,4,3) (1,3,2,4)     For $(4,2)$, we have $14$ permutations: $$(1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2), (2,1,3,4),$$ $$(2,1,4,3), (2,3,1,4), (2,4,1,3), (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,4,1,2)$$