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

learn more… | top users | synonyms (1)

12
votes
0answers
110 views

Covering pairs with permutations

Consider an $n \times n$ matrix $M_n$ with the following properties: Each row is a permutation of $A_n \equiv \{1, 2, ..., n\}$. Every ordered pair $(i,j)$, $i,j \in A_n$, $i \neq j$, appears as a ...
-2
votes
1answer
17 views

For any permutation $ \sigma \in S_n$, $(σ(1) − 1)(σ(2) − 2) . . . (σ(n) − n)$ is even when $n$ is odd [closed]

Let σ be a permutation of ${1, 2, 3, . . . , n}$, n odd. I want to show that $(σ(1) − 1)(σ(2) − 2) . . . (σ(n) − n)$ is even. Thank you.
-2
votes
1answer
18 views

Numbers of words allowing repetition [duplicate]

10 different letters of an alphabet are given. words with 5 letters are formed from these given letters.I have to determine the number of words which have at least one letter repeated. Answer is - ...
0
votes
2answers
29 views

sum of numbers formed by permutations

I have digits 2,3,4,5. I have been asked to find the sum of all 4 digits the numbers that can be formed using these digits without repetition such that all are included in the number. Can someone ...
1
vote
1answer
31 views

I need help answering a few simple math problems related to permutations and probability

Question 1: How many words can you make from the letters Texas if repeats are not allowed? Question 2: How many words can you make from the letters Texas if repeats are allowed? Question 3: What is ...
0
votes
1answer
43 views

Combinatorics problems involving permutations

Let $A= \{ 1,2,3,...,n\}$ a set and $f:A \to A$ a permutation of the set A. We call a number $x \in \{ 2,3,...,n-1 \}$ special if $f(x)>\max \{f(x-1),f(x+1) \}$ or $f(x)<\min \{f(x-1),f(x+1) \}.$...
-1
votes
1answer
22 views

How many possible placements are there for a Battleship puzzle?

I am studying the NP-Completeness of the battleship puzzle; the pencil and paper game found in newspapers and not the more popular 2-player version. I understand why the puzzle is NP-Complete because ...
0
votes
1answer
32 views

Find commuting elements within a permutation group

The question is like this: IF $G=S_5$ and $g=(1\quad 2\quad 3)$, determine the number of elements in $H=\{x\in G:xg=gx\}$. To do the question, first it says $$x(4)=(x(1\quad 2\quad 3))(4)=(1\quad 2\...
1
vote
2answers
21 views

Sign of composition of transpositions

Let $\sigma \in S_n$. Definition: Suppose that $\text{sign}\sigma=(-1)^N$, where $N$ - number of inversions in permutation $\sigma$. Suppose that $\tau_1$ and $\tau_2$ transpositions. How to prove ...
1
vote
1answer
23 views

Sign of permutation. Confusing example

Let $\sigma=(2314)\in S_4$. We have different definitions of sign of permutation. 1) Our $\sigma=(24)(21)(23)$ hence $\text{sgn}\sigma=(-1)^3=-1.$ 2) Our $\sigma$ has two inversions namely $(2,1)$ ...
0
votes
1answer
19 views

Does every partition of n correspond to some permutation of [1,2, … n]?

It is known that every permutation can be decomposed into disjoint cycles. The cycle type gives the length of each cycle. The sum of cycles length is n. I am wondering whether every partition of n ...
1
vote
1answer
38 views

Fourier transformation of a group

At the beginning of the section 4 of Fast Quantum Fourier Transforms for a Class of Non-abelian Groups, it is said that, ... calculating a Fourier transform for a group $G$ is the same as decomposing ...
2
votes
1answer
54 views

what is the smallest non-abelian finite group which has normal, non-abelian subgroups (plural)

I am looking for smallest example of a group $G$ such that: $G$ is a finite, non-abelian group $G$ is not simple $G$ has non-trivial, proper, normal subgroups: $H_1, H_2, \dots $ $H_1, H_2, \dots $ ...
0
votes
0answers
23 views

Cycle structure of the generators of the dihedral group

Would the following be correct about generating the dihedral group $D_n$ by permutations? If $n$ is even, the group can be generated as $\langle(2\quad n)(3 \quad n-1) \ldots (\frac{n}{2}-1 \quad \...
0
votes
1answer
23 views

permutations of n objects

Does the number of permutations of $n$ objects, $r$ alike of one kind and $n−r$ alike of another kind, always equal the combinations of n different objects taken $r$ at a time? Explain. I know ...
1
vote
2answers
52 views

Partition of natural number not equal to factorial

I wish to prove the following statement so I can use it as a lemma for a group theory result. To be honest I have not tried much yet, my intuition tells me this is going to be connected to the ...
0
votes
1answer
22 views

Arrangements of crew in two sides of a boat - permutations and combinations

A boat crew consist of 8 men, 3 of whom can row only on one side and 2 only on the other. The number of ways in which the crew can be arranged is This is a problem my math teacher has given to ...
-3
votes
1answer
76 views

Simple Question on Binomial theorems… [closed]

I have tried to solve this question by putting the value of each coefficients but it is really becoming very lengthy.... what i got was this number 10510100501... But how to get this in the required ...
7
votes
2answers
555 views

Number of ways of visiting N places

A tourist wants to visit $N$ cities, each numbered from $1$ to $N$, but he wants to visit them in a weird order. A weird order is such in which no city numbered $i$ is the $i$-th to visit in his ...
2
votes
1answer
21 views

For each of the following restrictions, find the smallest size n for strings over $\{a, b, c\}$ that can be used as codes for $27$ people.

For each of the following restrictions, find the smallest size $n$ for strings over $\{a, b, c\}$ that can be used as codes for $27$ people. a. There are $k$ $a$’s, $l$ $b$’s, and $m$ $c$’s and $k + ...
0
votes
3answers
90 views

How many distinct ways can the number be written as product of $3$ factors?

How many distinct ways can the number $126$ be written as a product of $3$ positive integer factors? I found that the prime factors are $126=2\times3\times3\times7$. But how to get number of ...
3
votes
2answers
46 views

What is probability that out of the first half on N objects, none will be matched with their own label?

The problem: We have N (even) objects ordered $o_1 ... o_N$ , each having their own label. The labels are reassigned to the objects randomly. What is the probability that that neither of the first $N/...
2
votes
1answer
27 views

Understanding derangement.

From the inclusion-exclusion principle we get that out of $N$ objects with one label each, there is a probability of $$\sum_{k=1}^N (-1)^{k+1}\frac{1}{k!}$$ that a random assignment of the $N$ labels ...
3
votes
1answer
35 views

How many straight lines can be made between 10 points such that 4 of them are colinear?

So i know how to get the answer. We just have to find $C(10,2)$ and subtract $C(4,2)$ and add 1. We are basically counting all the points between co-linear points as 1. So the question is why we are ...
0
votes
0answers
23 views

Centralizer of $\sigma\in S_n$ [duplicate]

Let $\sigma\in S_n$ . Describe the centralizer of $\sigma$. Thought: If I conjugate $\sigma$, then $\tau^{-1}\sigma\tau=\sigma.$ This means that $\tau$ is a power of $\sigma,$ and $<\sigma>\...
1
vote
1answer
33 views

How many ways are there to arrange the letters of word $ALGEBRA$ such that the relative order of the vowels and consonants doesn't change?

I did this question this way :- there are 4 consonants in the words (LGBR) and there are 7 letters in the word. $therefore$ number of in which consonants can be arranged in relative order will be $C(...
1
vote
4answers
40 views

How many mixed double pairs can be made from 7 married couples provided that no husband and wife plays in a same set?

So for first man there can be 7 possible partners including his wife, for the next man there will be 6 possible partners and so on, $therefore$ for $7$ men and $7$ women, there will be $7!$ possible ...
4
votes
3answers
78 views

Finding number of functions from a set to itself such that $f(f(x)) = x$

The questions states that $f: A\rightarrow A$ is a function which satisfies $f(f(x)) = x.$ We have to find the number of such functions with $A = \left\{1,2,3,4\right\}$. The given condition clearly ...
0
votes
2answers
38 views

A question of permutations and combinations with six cards and six envelopes.

Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same ...
1
vote
2answers
31 views

How do I calculate the number of unique permutations in a list with repeated elements? [duplicate]

I know that I can get the number of permutations of items in a list without repetition using (n!) How would I calculate the number of unique permutations when a ...
1
vote
2answers
51 views

Counting the number of “distinct” permutations of two sets?

I don't really know how to introduce this question, so I start defining something I needed in order to well understand the problem I met! Let $A$, $B$ two finite sets of distinct elements, with $|A|=|...
1
vote
1answer
33 views

rationale for book's solution of combinatorics question about scheduling ten speakers with restrictions

If A, B, C are among $10$ people speaking at a function in alphabetical order What are total ways of doing so. BOOKS APPROACH: There are $10$ people out of which $3$ need to be taken care of. So ...
0
votes
1answer
33 views

Permutations of 3 digit numbers divisible by 5

I recently had to answer the following permutation question: How many 3 digit numbers can be formed from the digits 2,3,5,6,7,9 which are divisible by 5 and none of the digits are repeated? ...
0
votes
3answers
64 views

In how many ways can we arrange the letters of word BAHAMA such that it starts with H and ends with A?

In how many ways can we arrange the letters of word BAHAMA such that it starts with H and ends with A? I have a doubt in the selection of A at the last position. Please help. Thanks in advance!!
2
votes
2answers
100 views

In how many ways can the letters of word $PERMUTATIONS$ be arranged if there are always 4 letters between P and S?

In how many ways can the letters of word $PERMUTATIONS$ be arranged if there are always $4$ letters between $P$ and $S$? Now there are $12$ blank spaces, which we have to fill by the letters of the ...
-1
votes
1answer
44 views

Combination and Permutation S= {A,B,B,C,C,C,D,D,D,D,E,E,E,E,E}.

S= {A,B,B,C,C,C,D,D,D,D,E,E,E,E,E}. If I choose n element from S, how many possible combination (unordered) and permutation (ordered) are possible (without using decision tree or counting)? What is ...
-1
votes
1answer
37 views

Combinatorics Puzzle (Circular Table) [closed]

Q. Eleven members of a cricket team are numbered 1,2,3..11. In how many ways can they be seated around a circular table so that the numbers of any two adjacent players differ by one or two. (...
2
votes
2answers
74 views

Arrangement of letters in VISITING with no pairs of consecutive Is.

Could someone help me understand a book's solution to the following problem? I am providing my own solution, but I fail to understand theirs. Question: How many ways are there to arrange the ...
1
vote
2answers
71 views

Setting up an inclusion-exclusion question

What is the number of one-to-one functions $f$ from the set $\{1,2,...,n\}$ to the set $\{1,2,...,2n\}$ so that $f(x) \neq x$ and $f(x) \neq 2n - x + 1$ for all $x$? I'm getting that the number of ...
0
votes
0answers
11 views

Number of letters moved by a product of permutations

Let p and q be permutations in the symmetric group on n letters. p and q need not have the same cycle structure. Now compute q * inv(p) -- for inv(p) the inverse of p -- and count the number of ...
2
votes
1answer
13 views

Permutations starting with a specific letter

Ok, this is a homework question and I think I've resolved it but I want to bounce it off you guys. I have a $6$ letter word with no repeated letters. I need to calculate how many $3$ letter words can ...
2
votes
0answers
40 views

Positive integers $<100000$, how many contain exactly one $3$, one $4$ and one $5$

So I use $5$ positions for range $00000$ to $99999$ Choose $3$, choose $4$ and choose $5$ as follows: $5C1 \cdot 4C1 \cdot 3C1$ Remaining $2$ digits have $7$ possible digits as input Ans: $5C1 \...
3
votes
1answer
48 views

Painting a 2x2 Grid

We have a 2x2 grid and 10 different colours. I want to paint such that adjacent grids are painted with different colors. How many ways can i do this? ...
2
votes
2answers
31 views

$5$ chem students, $6$ maths students and $7$ physics students permutation

$5$ chem students, $6$ maths students and $7$ physics students. Find the number of arrangements if a)Chem majors are to occupy the first 5 positions b)Chem majors cannot occupy the first 5 positions ...
1
vote
0answers
11 views

Conway's theorem on the number of orbits on the set of all ordered cycles in a $d$-valent graph

I am trying to understand Conway's theorem on the number of orbits on the set of all ordered cycles in a $d$-valent graph. I quote it from Cycles in graphs and groups by Kantor. Theorem $1$ (...
8
votes
1answer
64 views

Do these two permutations generate $A_n$?

Let $n$ be odd and not a multiple of $3$. Do the cycle $\sigma:=(1, 2, \dots, n)$ and any cycle of length $3$ generate $A_n$?
0
votes
2answers
36 views

Finding the parity of a permutation “exclusively”?

I'm trying to find the parity of permutations such as $(2468)$. What makes it possible to find the "exclusive" parity of such permutation? I.e. that if one tries to express $(2468)$ as a product of ...
0
votes
2answers
28 views

If $\sigma=(a_1 a_2 … a_n)$ and $|\sigma|$ is odd, then what is $\sigma^2$?

I'm trying to understand the way to infer the power of a permutation. If $\sigma=(a_1 a_2 ... a_n)$ is a $k$-cycle and $k=|\sigma|$ is odd, then how can I infer what $\sigma^2$ is?
0
votes
1answer
72 views

Prove $sgn(π) = sgn(π^{-1})$?

I'm pretty sure the inversion count of $π$ should be the opposite of the inversion count of $π^{-1}$. By this I mean if $π$ looks like this: $1 \to 1$, $2\to 2, \ldots, 10 \to 10$ and therefore the ...
0
votes
1answer
37 views

Normal Klein four-subgroup of symmetric group:S4

I've recently found a very interesting web portal about groups. I wanted to know about the normal subgroups of $S_4$ regarded as the rotation group of the cube. I found that one f them is the Normal ...