Let $S = (\pi(1), \pi(2),\cdots,\pi(n))$ be a permutation of $\{1,2,\cdots,n\}$ such that $S$ does not contain the pattern $\pi(i)&lt;\pi(j)&lt;\pi(k)$ for any $i&lt;j&lt;k$.   For example, the permutation $(1,4,3,2,5)$ is not allowed since it contains $1,\cdots,2,5$ in that order.   How do we count the number of such permutations (of $n$ numbers)?   I know how to count permutations that forbid the pattern $\pi(k)&lt;\pi(i)&lt;\pi(j)$ for any $i&lt;j&lt;k$, namely they are counted by the Catalan Number $C_n$. But the $\pi(i)&lt;\pi(j)&lt;\pi(k)$ pattern doesn't seem to yield to such a method. Any help would be appreciated, Thanks!
123441
There are $k$ penguins, $k\ge 3$. They are all different heights. How many ways are there to order the penguins in a line, left to right, so that we cannot find any three that are arranged tallest to shortest (in left to right order)? The penguin triples do not have have to be adjacent.  This problem is courtesy of someone I know only as "DaMancha."
53476
Given $n$ objects with values $\{x_1,x_2,x_3,\dots,x_n\},$ and $m$ pairs $a_k = \{x_i,x_j\}$. Let $\{p_1,p_2,p_3,\dots,p_n\}$ be a permutation of objects. The question is to find number of permutations of objects such that none of the pairs $\{p_i,p_{i+1}\} \in a_k\ \forall i \in (1,n-1)$.  I tried to use inclusion-exclusion principle, first I took all the objects without any constraint. Then I picked number a pair $a_k$ and removed it from the total answer using inclusion-exclusion. But I was not able to solve it.  I don't assume the solution has a compact form, so I expect a procedure rather than an answer.
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.
13928
I'm studying cycle decomposition in group theory. The exercises on my book keep saying things like:   Find a permutation $\sigma$ such that $\sigma (123) \sigma^{-1} = (456)$ Prove that there is no permutation $\sigma$ such that $\sigma (1 2) \sigma^{-1} = (123)$ Show that $\pi(x_1 x_2 \cdots x_n)\pi^{-1} = (\pi(x_1)\cdots \pi(x_n))$   Why this  $\sigma \pi \sigma^{-1}$ appears every time in this book? Is this important for something? Could somebody give me a clear picture of how we arrive at this? Also, would be nice to know how to prove the third one, if somebody could help me.
120301
Given an integer $n$, define $s(n)$ to be the length of the shortest sequence $S = (a_1, \cdots a_{s(n)})$ such that every permutation of $\{1,\cdots,n\}$ is a subsequence of $S$.  If $n=1$, then $S = (1)$ is the shortest sequence containing all permutations of $\{1\}$, so s(1) = 1.  If $n=2$, then $S = (1, 2, 1)$ contains all permutations of $\{1,2\}$ as a subsequence, so $s(2)=3$.  Is there a general formula for $s(n)$?
71077
There are 11 letters in the word.   M - 1 I - 4 S - 4 P - 2  so the number of different permutations is $\dfrac{11!}{1! 4 !4!2!}$  Is this correct solution?
82722
$a_{n,3}$     $$1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,\cdots \cdots $$   $a_{n,5}$     $$1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,\cdots \cdots $$   $a_{n,7}$     $$1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,\cdots \cdots $$   $$\vdots $$  $a_{n,2k+1}$     $$1,\cdots \cdots\cdots \cdots,1,\cdots \cdots\cdots \cdots,\overbrace{1,\cdots \cdots\cdots \cdots}^{2k+1},1,\cdots \cdots\cdots \cdots,1,\cdots \cdots$$   I found  $$a_{n,k}= \left \lfloor \left | \cos\frac{\pi (n-1)}{2k+1} \right | \right \rfloor$$ but this term include abs and floorfucntion.  I mean i want the General Term without abs and floorfucntion.(plus sum)  Any hints will be appreciated, thank you.
5705
I've seen  post about the $n^{\textrm{th}}$ permutation of a set but that is not what I need. If you have a bit string (ones and zeros only) there are  to quickly permute the NEXT lexicographically ordered bit permutation. For example take $$000111 \rightarrow 001011 \rightarrow 001101\rightarrow\cdots$$ etc. If the string is long then there are going to be approximately one Bajillion of these things. And I want to know how to compute the $n^{\textrm{th}}$ guy without doing the exhaust.  Backgound: This is for a parallel computing job where I need to farm out the search space of elements of a set.  Foreground: I own a copy of Knuth's 4th volume of "The Art of Computer Programming" and I think the answer is in there but I can't seem to find it. (It's like 900 pages).  I'm posting here in the hopes that someone has knowledge of this (obviously). Even if you can point me to a source, say the part in Knuth's book where he describes this problem I would be most grateful.
79254
I have to figure out a way to count how many sequences are there s.t:   My alphabet is $1$ up to $49$. Each number that is chosen, is chosen only once. The sequence is $6$ digits long. The sequence is in increasing order.  e.g that is a valid sequence: $(1, 2, 40, 42, 43, 49)$  and this is not: $(1, 2, 40, 25, 25, 12)$   I know that for the first 3 rules the answer is: $\binom{49}{6}\cdot 6!$  How do I deal with the fourth?
87152
I am trying to find the smallest positive integer $n$ such that $S_n$ contains an element of order 60. I know that every permutation in $S_n$ can be expressed as the product of disjoint cycles, and I also know that the order of a permutation is the least common multiple of the lengths of the cycles in its disjoint cycle product.   So, suppose $\sigma \in S_n$ such that $|\sigma|=60$. Then $60=lcm \left\{|c_1|, \ldots , |c_m|  \right\}$, where $c_i$ is one of the cycles in the disjoint cycle product of $\sigma$. The prime factorization of 60 is $2^2\cdot 3 \cdot 5$, but the least common multiple of 2, 3, and 5 is 30, so that doesn't help. However, the least common multiple of 3, 4, and 5 is 60. I just don't know where to go from here.  Also, what is meant by a "disjoint cycle pattern"? Thanks for your help!!
63191
Prove the following in $S_n$:  Let $\alpha = (a_1,a_2,\ldots,a_s)$ be a cycle and let $\pi$ be a permutation in $S_n$. Then $\pi\alpha\pi^{-1}$ is the cycle $(\pi(a_1),\ldots,\pi(a_s)).$     I'm not sure where to even start.
81042
let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people  determine $A_1, A_2, A_3$  So I have  $A_1 = 1$ way $A_2 = 4$ way $A_3 = 12$ way  But I am not sure if this is right... Can anyone confirm?  edit:  My way of getting this is  $A_1 = 1 $ because {P1} only has 1 way to sort  $A_2 = 4$ because {P1,P2} = {P1,P2},{P2,P1},{P1P2},{P2P1}  etc.
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!
74986
Let $\sigma \in S_n \;$ then $\; \sum_{i=1}^n|\sigma(i)-i|\;$ is an even number. I tried to show the statement for cyclic permutations first. However, I am not getting anywhere. The statement is trivial for transposition $(k,l)$. That´s all what I have found out so far. Can someone give me a hint why the statement is in fact true for any cyclic permutation ?
100390
Let $X(n)$ denote number of all permutations of $\left\{1,\ldots,n \right\}$ that have only cycles of even length. Let $Y(n)$ denote number of all permutations of the same set that have only cycles of odd length. Count $X(2n)-Y(2n)$.   I don't know even how to start. I counted this sum for $n=1,2,3$ and it seems that it is always equal to $0$, but it doesn't help with calculating it in general.
18228
Let $X=\{1,2,3,\dots,n\}$ where $n\in N$. Show that the number or $r$ combinations of $X$ which contain no consecutive integers is given by   $\binom{n-r+1}{r}$ where $0\le r\le n-r+1$.  I am unable to think of any possible way to prove it.  Please explain the proof and comment on the technique used to help me with problems in the future.   Thanks in Advance!  Thanks for pointing the typing faults!
113768
The number of words that can be made by permuting the letters of MATHEMATICS is   $1) 5040$  $2) 11!$  $3) 8!$  $4) 4989600$  First of all I do not understand the statement of the problem, I would like if some one tell me with an example.