For questions related to permutations, which can be viewed as re-ordering a collection of objects.

learn more… | top users | synonyms (1)

0
votes
2answers
5k views

How many bit strings of length 10 contains…

I have a problem on my home work for applied discrete math How many bit strings of length 10 contain A) exactly 4 1s the answer in the book is 210 I solve it $$C(10,4) = \frac{10!}{4!(10-4)!} = ...
2
votes
0answers
59 views

Why does $\operatorname{SL}_2(3)$ only yield even permutations?

$\newcommand{\pa}[1]{\left(#1\right)} \newcommand{\pamat}[1]{\left(\begin{array}{cc} #1 \end{array}\right)}$ In an exercise lesson for Algebra 3, we were proven that the special linear groups over ...
2
votes
2answers
80 views

Probability of Boys and Girls in Row

Ten male friends and six female friends line up next to the bus stop in a row. Everyone just positions themselves at random. What is the probability that no two females are sitting next to each other? ...
2
votes
0answers
23 views

If $g=(n-j,\dots,n)$ and $\sigma\in S_{n-1}$, why are the inversions of $g\sigma$ the union of the inversions of $\sigma$ and $g$?

I can't see why a claim I'm reading is true. If $\sigma\in S_n$, let $R(\sigma)=\{(i,j):i<j,\ \sigma(i)>\sigma(j)\}$, i.e., $R(\sigma)$ is the set of inversions of $\sigma$. The set ...
0
votes
2answers
76 views

Number of combinations for N elements with M states

I have $N$ elements: $$e_1, e_2, e_3, e_4, ..., e_N$$ and each of them has $M$ possible states: $$e_i:\, e_{i1}, e_{i2}, ..., e_{iM}$$ I need to find the total number of combinations of these $N$ ...
0
votes
1answer
80 views

Probability of an event if the sample space has identical elements

Suppose we have a box, with only one small hole. Suppose 10 distinct black balls and 20 distinct white balls are put in the box. Now, in a random draw of 1 ball, the probability that the ball drawn is ...
4
votes
4answers
162 views

Is there any neat way to show $\phi$ is a homomorphism?

In Michael Artin's Algebra (chapter 2, page 50, example 2.5.13) the author illustrates a homomorphism from $S_4$ (all permutations of indices $(1,2,3,4)$) to $S_3$ (all permutations of indices ...
14
votes
3answers
205 views

Rearrangements that never change the value of a sum

Which bijections $f:\{1,2,3,\ldots\}\to\{1,2,3,\ldots\}$ have the property that for every sequence $\{a_n\}_{n=1}^\infty$, $$ \lim_{n\to\infty} \sum_{k=1}^n a_k = \lim_{n\to\infty} \sum_{k=1}^n ...
7
votes
2answers
114 views

$S_6$ contains two subgroups that are isomorphic to $S_5$ but are not conjugate to each other

This is a problem from Ph.D. Qualifying Exams. Show that the symmetric group $S_6$ contains two subgroups that are isomorphic to $S_5$ but are not conjugate to each other. Here is my method. $S_5$ ...
0
votes
1answer
25 views

Conjugation of permutation group $S_n$

I want to find the conjugacy classes of the permutation group $S_n$ To start with I think I have to prove that $\pi(\sigma_1\dots \sigma_m)\pi^{-1} = (\pi(\sigma_1)\dots \pi(\sigma_m))$. Where $\pi$ ...
1
vote
3answers
123 views

How to find a permutation $\sigma$ given the permutation $\sigma^2$?

How to solve the equation: $\sigma ^2 =\left({\begin{array}{*{20}c}1 & 2 & 3 & 4 & 5\\ 1 & 4 & 2 & 3 & 5\end{array}}\right)\ $ where $\sigma \in S_5$. Is there a ...
0
votes
1answer
26 views

number of combinations/permutations

if I have $n$ drawers and in each drawer I can only have 1 pen or 1 pencil for example if i have $3$ drawers the possible ...
0
votes
2answers
283 views

Probability of picking up one ball of each color

A box contains 6 red, 4 white and 5 black balls. A person draws 4 balls from the box at random. Let P be the probability that among the balls drawn there is at least one ball of each color. Find 455 * ...
0
votes
1answer
40 views

Possible number of sequences such that $x_{i} = 1$ or $ 2$ and $\sum_1^n x_{i} = 10$

How many finite sequences are there such that $x_{i} = 1$ or $ 2$ and $\sum_1^n x_{i} = 10$ $?$ Now I did it this way: number of $1$'s $\ $:$\ $ $0$ ,$2$ ,$4$ ,$6$ , $8$ , $10$ ...
2
votes
1answer
27 views

Permutations of {1, 2 .. 30} where $a_n - a_n-m$ is divisible by m from {2, 3, 5}

There are $N$ permutations $(a_1,a_2,\dots,a_{30})$ of $1,2,\dots,30$ such that for $m\in\{2,3,5\}$, $m$ divides $a_{n+m}-a_n$ for all integers $n$ with $1\leq n <n+m\leq 30$. Find $N$. I really ...
-1
votes
2answers
95 views

How many structurally different latin squares of order 5 do exist?

I know the number of latin squares order 5 which start with 1 2 3 4 5 in the 1st row or column, that is 1344, but the greater part of that number consists of structural duplicates of each other. So, I ...
1
vote
1answer
78 views

If $g$ is a permutation, then what does $g(12)$ mean?

In Martin Lieback's book 'A Concise Introduction to Pure Mathematics', he posts an exercise(page 177,Q5): Prove that exactly half of the $n!$ permutations in $S_n$ are even. (Hint: Show that ...
3
votes
2answers
89 views

Permutation count of AABBC

Given a string: $AABBC=A^2B^2C^1$ I am trying to find the Total Permutations (this may be incorrect): $\dfrac{5!}{2!\cdot2!}=30$ My question is how would I find the partial sums (perhaps the ...
1
vote
3answers
544 views

How many two letter words can be formed from 26 English letters?

There are 26 English letters(a-z). From layman approach, How can one calculate the possible two letter words from these 26 English letters?
5
votes
3answers
69 views

Elements of $S_n$ which can not be product of $\leq n-2$ transpositions

It is well known that every element of $S_n$ can be written as a product of at most $n-1$ transpositions. This theorem is proved in all the books which discuss the permutation groups. But, I find that ...
4
votes
2answers
62 views

How to conceptualize “dividing out” a number (e.g. in permutations, Bayes' Theorem)?

I'm trying to achieve a better conception of what it means to "divide out" a variable/number, because I'm currently have a lot of trouble justifying to myself why it actually works the way it does in ...
0
votes
2answers
52 views

Find the number of seven digit whole numbers in which only 2 and 3 are present as digits if no two 2's are consecutive in any number?

Find the number of seven digit whole numbers in which only $2$ and $3$ are present as digits if no two $2$'s are consecutive in any number? My Approach: We can make numbers and see like: ...
0
votes
2answers
198 views

How many permutations of the word TOMORROW can be made if the O's can't be together?

I'm trying to answer this question. This is my attempt of solution: First we distiguish the O's and R's, then we have the word: $TO_1MO_2R_1R_2O_3W$. We have $8!-7!\cdot3!-6!\cdot 3!$ different ...
3
votes
3answers
45 views

Combinatorics Question - Permutations and Supersets

I had a question that seems pretty straightforward, but I can't seem to wrap my mind around it. Let's say I have a bunch of elements in a set. {A, B, C, D, E}. How many permutations are there of ...
1
vote
1answer
268 views

Permutation of numbers from multiple sets [May contain duplicate numbers among other sets], resulting in Non-Duplicate Set

We have 3 Data Sets. From each set we will be selecting few numbers. 3 from Set 1, 2 from Set 2, 3 from Set 3. Totally, we will get 8 Numbers from 3 Sets. The resulting sets shouldn't contain any ...
0
votes
3answers
57 views

Why is it true that $(a_1 \ a_2 \dots a_r) = (a_1 \ a_r)(a_1 \ a_{r-1})\dots(a_1 \ a_3)(a_1 \ a_2)$?

In the theory of permutation, a $r$-cycle $(a_1 a_2...a_r)$ is defined in the following way: Start from $a_i$, a permutation function $f$ sends $a_i$ to $a_{i+1}$. When $i=r, a_i \text{ will be ...
2
votes
2answers
64 views

If $G = S_5$ and $H = \{g \in G \mid g^{5} = e\}$ how could I determine and prove whether or not $H$ is a subgroup of $G$?

I think that the this group contains the 5 element cycles and the identity e but overall I'm not sure how to prove that the product of the 2 members of H is also a 5 cycle or e.
0
votes
2answers
41 views

Number of permutations of an integer

If $n$ is an integer, how many permutations are less than, equal to and greater than $n$? For example if $n=24335$, $43325\gt n$, $23345\lt n$, etc...
1
vote
1answer
57 views

Two special sets of field elements

Let $F = GF(2^n)$. Let $P(x), Q(x) \in F[x]$ be such that $P(x)$ is a permutation, while $Q(x)$ is not a permutation. For $\lambda \in F^*$ define the function $g_\lambda(x) = Tr(\lambda Q(x))$. Let ...
0
votes
2answers
36 views

Permutational Question

When I use the equation $P = \frac{n!}{(n - r)!}$ with n = 3 and r = 2, I get 6 permutations. Though, how do I get the amount of permutations without cross-duplicates(e.g A/B and B/A)?
1
vote
0answers
117 views

Any hint on : Every $A_{n}$ elemnt is $n$-cycles product.

[Added explanation] I found this exercise as follows in Hungerford : Abstract algebra (3rd edition) page 236, exercise number 40. Stated as follows : C.40. Prove that every element of $A_{n}$ is ...
2
votes
2answers
57 views

Permutations: Interpreting Image Notation

I have a problem in interpreting permutation. I think the definition and my interpretation of it don't match each other. Let $\sigma=(1\ 2\ 4\ 3)$, and $\tau=(1\ 3\ 2\ 4)$ in one-line notation. I ...
2
votes
1answer
133 views

NP combination puzzle (Klotski)

I've written a C++ program to solve sliding puzzles games such as UnblockMe and Car Parking. I'm quite happy about it, since it solves various schemes in less than a second. Recently I fed the game ...
1
vote
0answers
31 views

How many permutations cover alternating/reverse alternating permutations?

Given integers $1$ through $2n$, let $S$ be set of ordering of integers that respect even alternating or reverse alternating permutations (https://en.wikipedia.org/wiki/Alternating_permutation) up to ...
2
votes
1answer
38 views

Where do I use that $G$ is a permuation group?

This is about question $4.1.7$ from Dummit and Foote, and also related to my previous question. The question is (summarised a bit): Let $G$ be a transitive permutation group on a finite set $A$. ...
0
votes
1answer
48 views

Compose $(1243)$ and $(5)$

Checking my work. In either direction: $(1243)[1] = 2$ and $(5)[2] = 2$, so far we have $(1, 2,\ldots$ $(1243)[2] = 4$ and $(5)[4] = 4$, so far we have $(1, 2, 4,\ldots$ $(1243)[4] = 3$ and ...
0
votes
0answers
70 views

Finding permutation matrix

Let $P_{\pi}$ denote a permutation matrix associated to the permutation $\pi:\{1,...,n\}\rightarrow \{1,...,n\}$ and $\sigma$ denote the cyclic permutation $(1 2 ...n)$. If T is the $n\times n$ lower ...
0
votes
1answer
38 views

How many permutations $(a_i)_{i=1}^{30}$ of $\{1,\dots,30\}$ satisfy $m$ divides $a_{n+m}-a_n$ when $m \in \{2,3,5\}$ and $1 \le n<n+m \le 30$?

Define a permutation $(a_1,a_2,\dots,a_{30})$ of $\{1,2,\ldots,30\}$ as good if for all $m \in \{2,3,5\}$, we have that $m$ divides $a_{n+m}-a_n$ for all integers $n$ satisfying $1 \leq n < n+m ...
4
votes
3answers
128 views

Why Composition and Dihedral Group have reverse order of operation?

NOTE - I didn't receive any answer in here and I think because my first post is not clear, so I entirely made another example: $K={\{id,r^2,r^4,s,r^2s,r^4s}\}$ is a proper subgroup of the dihedral ...
1
vote
1answer
84 views

Intuitively and Mathematically Understanding the Order of Actions in Permutation GP vs in Dihereal GP

I define $r$ to be one rotation clockwise, and s to be reflection on the 'horizontal' line (see the figure). So I can make these bijections: (in clockwise order) $$\begin{align*} 1,2,3,4,5,6 ...
0
votes
0answers
108 views

Permutation equivalence classes with kendall-tau distance

Consider a set $A=\{a_1,...,a_m\}\subset \{1,...,n\}$ for which $a_i<a_{i+1}$ for all $i = 1,\ldots,m-1$. Take any two distinct permutations $\sigma, \tau$ of $\{1,...,n\}$ such that $ ...
0
votes
1answer
43 views

Permutation and signature matrices “almost commute”

Let $\mathcal{P}$ be the set of all permutation matrices of order $n$ and $\mathcal{S}$ the set of all signature matrices of order $n$. Furthermore, let $$\mathcal{P}\mathcal{S} = \{PS \mid ...
4
votes
1answer
74 views

Characterisation of the squares of the symmetric group

I found out that for $n\le 4$ we have $S_n^2=A_n$ with $G^2$ defined by $$G^2:=\{g^2 \mid g\in G\}$$ for any group $G$. Surely we have $S_n^2\subseteq A_n$ for all $n\in\mathbb N$. Is there a ...
12
votes
2answers
304 views

Show that there is always a way to achieve det(A) > 0

a) Assume that $(a_1, ..., a_9)$ are different positive numbers. Let us make a $3 \times 3$ matrix $A_s$ by placing them arbitrarily into $9$ positions available. Show that there is always a way to ...
2
votes
1answer
92 views

Proving a certain lemma about subgroups of $A_n$

In proving $A_n$ is simple for $n\neq4$, my teacher established the cases 1, 2, 3 as obvious, then proved the case 5, and proceded by induction on the rest. In the midst of that induction, he stated ...
3
votes
2answers
409 views

How to arrange 15 women and 15 men so no two females are seated next to each other?

To a certain conference, each firm can send two employee representatives, on the condition that one of them is a male and the other a female. If 15 firms were represented in this conference, what is ...
2
votes
4answers
111 views

When will Andrea arrive before Bert?

The question was as follows- on any given day, Andrea is equally likely to clock in at work any time from 8:50am to 9:06am. Similarly, Bert is equally likely to to clock in at work at any time ...
1
vote
4answers
80 views

Prove that the 4-group V is normal subgroup of $S_4$ by using isomorphism theorem

Prove that the 4-group V is normal subgroup of $S_4$ First, by using the multiplication table, I am able to prove that 4-group V is subgroup of $S_4$. But I face problem in proving that $\forall ...
1
vote
0answers
47 views

Simple string permutations question

How many sequences of 5 letters are there in which exactly two are vowels? My approach There are $5^2$ different permutations for 2 vowels and $\binom{5}{2}$ ways allocate them. There are $21^3$ ...
1
vote
2answers
54 views

Basic Password permutation question

I'm reading the problem from this stanford material (http://infolab.stanford.edu/~ullman/focs/ch04.pdf). Can you please help me understand this? Question: At Real Security, Inc., computer passwords ...