Questions tagged [permutations]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
19 views

Number of 3 colorings on grid with constraints [duplicate]

I am trying to figure out a way to do the following: Given a $3 \times n$ grid, ($n \geq 2$) choose coloring by using $3$ colors (say, RGB), such that any given column cannot have all grids of same ...
-3
votes
0answers
77 views

Twelve sided polygon cut into triangles [on hold]

In how many ways a 12 sided polygon cut into triangles by connecting vertices with non crossing line segments.
5
votes
1answer
74 views

How many ways are there to arrange 4 letters from “combinatorics”?

How many ways are there to arrange 4 letters from “combinatorics”? So I’m studying about combinatorics and permutations. And I stuck with this question. So I just doing my own step but I want to make ...
0
votes
0answers
17 views

Permutations using PIE or recursion

I can sense that this problem can be either done by principle of inclusion exclusion or by recurrence relation but I am not able to form a path to get to the answer. May be I am doing something wrong. ...
2
votes
2answers
51 views

>Determine subgroup $\langle (12),(13)(24)\rangle $ of group $ S_{4}$

Determine subgroup $\langle (12),(13)(24)\rangle $ of group $ S_{4}$. Using the definition of generator of group, I believe I am supposed to find all permutations that can be written as multiple of $...
1
vote
1answer
32 views

Permutations of pairs vs pairs

I want to create a league for table football where there is two people vs two people. There would be a match for every combination of pair vs every combination of pair. So, given the following players:...
1
vote
2answers
25 views

How many ways can the cars be arranged if there are at least two cars of a particular brand in a row?

I have the following exercise. Assume you have 5 cars of brand A, 6 cars of brand B and 5 cars of brand M. Each car is considered unique i.e no repetitions. How many ways can I arrange the cars ...
-1
votes
1answer
34 views

If permutation p=(148)(25)(396)(7) how to find p^123? [on hold]

If permutation p=(148)(25)(396)(7) how to find p^123 ?
5
votes
1answer
86 views

Derangement formula for repeated permutation

I need general formula for repeated permutation: For any n numbers, $$ n={1,2,3,...} $$ Derangement formula: $$ D_n =!n=(n-1)(!(n-1)+!(n-2)),$$ Here the numbes are distinct from one another (no ...
1
vote
2answers
24 views

Sign of a Particular Permutation

Let $n,k\in\mathbb{N}$ be such that $k<n$. Define the permutation $\sigma\colon\{1,\ldots,n+1\}\to\{1,\ldots,n+1\}$ as \begin{align*} \sigma(j)=&~\begin{cases} j+k+1, & j\le n-k \\ j+k-n, &...
2
votes
1answer
28 views

How to compute the stabilizer subgroup of a partition with GAP?

A partition $P$ of a set $S$ is a set of disjoint subsets of $S$ whose union is $S$. Let $G$ be a subgroup of the symmetric group $S_n$. Define the stabilizer subgroup of $G$ for a partition $P$ of $\{...
1
vote
0answers
47 views

Determining structure of group based on its permutation representation.

I am preparing for an algebra prelim at my university, and I came across this question which I cannot finish. Suppose that a finite group $G$ acts transitively on a set $S=\{ a_1,a_2,a_3,a_4,a_5\}$ ...
0
votes
5answers
64 views

How many different arrangements are possible such that there are no consecutive A's, B's or C's?

Suppose we have 7 different items: (A1)(A2) (B1)(B2) (C1)(C2)(C3) How many different arrangements are possible such that there are no consecutive A's, B's or C's? e.g. (A1)(B1)(C3)(A2)(C2)(B2)(C1) ...
0
votes
1answer
47 views

Ways to pick out and arrange letters to make MISSISSIPPI

From Mathematical Puzzles by Geoffrey Mott-Smith: If a box of anagram letters contains nine M's, twenty-eight I's, twenty-four S's and eight P's, in how many ways can you pick out and arrange letters ...
0
votes
1answer
35 views

Lining up students—combinatorics

There are $8$ boys and $6$ girls. In how many ways can they line up so that the front and end of the line are occupied by boys? Someone told me that the answer is $3832012800$. Am I missing something?...
3
votes
2answers
45 views

How to find the number of times at least two ones are adjacent out of all possible permutations of $\{0, 0, 0, 0, 1, 1, 1, 1\}$

My question is this. How do I find the amount of times at least two ones are adjacent when the sample of characters is $$\{0, 0, 0, 0, 1, 1, 1, 1\}$$ My instinct is to sum the amount of ...
3
votes
2answers
33 views

How many ways I can arrange 5 unique blue books, 5 unique red books and 5 unique green books so that 2 blue books are always together?

how many ways can i arrange 5 unique blue books, 5 unique red books and 5 unique green books so that at least 2 blue books are always together? I thought I had a better grasp of combinatorics, but ...
2
votes
0answers
35 views

Permutations Polynomials over Rings and Finite Fields

If $f(x) = \sum_{i=0}^d a_i x^i \in \mathbb{Z}_{2^n}[x]$ is a polynomial with coefficients $a_i \in \mathbb{Z}_{2^n}$, then it is known due to Rivest that $f(x) \mod 2^n$ permutes the elements of $\...
2
votes
1answer
70 views

Combinatorial proof of $D_n= nD_{n-1}+(-1)^n$

Consider a finite set $S_n$ with $n\ge 2$ elements and denote by $D_n$ the number of derangements of $S_n$. How to prove by a direct combinatorial proof that $$D_n= nD_{n-1}+(-1)^n ?$$ I know a ...
0
votes
0answers
56 views

Every permutation can be written as a product of transpositions

I'm confused with how a textbook presents their proof on how every permutation in a permutation group can be represented as a product of transpositions. They said the following: "Let $\alpha \in S_n$ ...
0
votes
4answers
69 views

Find the coefficient of $x^6$ in $(2+2x+2x^2+2x^3+2x^4+x^5)^5$

Find the coefficient of $x^6$ in $(2+2x+2x^2+2x^3+2x^4+x^5)^5$ I did this with a change of variables: $a = 2$ $b = 2x$ $ c = 2x^2$ $ d = 2x^3$ $e = 2x^4$ $f = x^5$ And then I found out the ...
0
votes
1answer
67 views

Find the number of ordered triples (a,b,c) of positive integers such that $30a + 50b + 70c \le 343.$

Find the number of ordered triples $(a,b,c)$ of positive integers such that $30a + 50b + 70c \le 343.$ My confusion is that while solving the question a, b,c can be zero or not
0
votes
1answer
20 views

concrete example: 4 permutations span a permutation group - can I find a base of size 3?

I'm interested in permutations on 4x4 Sudokus i.e. ways of rearranging the numbers so that the solution is still "the same". For instance if you mirror a Sudoku horizontally the solution remains ...
1
vote
1answer
27 views

Existence of even permutation which maps first $m$ elements to given $m$ distinct elements

Let $m\leq n−2$. Given any $m$ distinct elements $i_1,...,i_m$ from $\{1,...,n\}$, show that there exists a $σ ∈ A_n$ such that $$\sigma(j) = i_j,\ \ \ \forall j\in \{1,...,m\}$$ What I could do I ...
2
votes
3answers
39 views

Ways to sit 5 kids in 12 chairs lined up in a row such that none of them are next to each other

How many ways are there to sit 5 kids in 12 chairs lined up in a row such that none of them are next to each other? My first thought was to sit the kids with an empty chair next to them: $x_1|x_2|...
1
vote
2answers
40 views

Prove that a permutation of size N can or cannot be of order M

An example of this would be a permutation of size 32. Can this be of order 62? I assume not because the only way to achieve this would be to have the permutation be made up out of a part with order 2 ...
4
votes
4answers
144 views

How to find number of words made using letters of word 'EQUATION' if order of vowels do not change

Find number of words made using letters of word 'EQUATION' if order of vowels do not change. My attempt:- since we do not have to change the order of the vowels hence, _E_U_A_I_O_ we ...
1
vote
0answers
45 views

minimal overgroups of a permutation group [closed]

Given a group $G < S_N$ is there an "efficient" way to identify (or construct) the "minimal" permutation groups $H_i \leq S_N$ such that $G < H_i$? $H_i$'s are minimal in the sense that there $\...
0
votes
1answer
27 views

Symmetry in a sequence of linear orders

I would like to know if the following conjecture is correct and/or already known. Do you have any ideas for a demonstration or counter-example? Thank you. Let $X$ be a finite set and $(P_i)_{i\in N}$ ...
0
votes
1answer
61 views

universe sized cube and visualising really large numbers

Lets say you have each Planck length in the observable universe represent a googolxgoogolxgoogol Rubik's cube, and create a cube with a total volume of 4.6 x 10^185 of these cubes, each move on any ...
0
votes
0answers
46 views

Maximum number of steps needed to solve a n-digit Pico, Bagel and Fermi Game

Bagel Pico Fermi is a mathematical number guessing game. Skip this if you know about this game. In this game, one person writes down a 3 digit number with all different digits and can be started ...
4
votes
2answers
116 views

Permutations on $[2^k]$ And the Existance of Permutation Polynomials

Fix $k \geq 2$ and let $[n]$ denote the set $\{0, 1, \ldots, n-1\}$. A polynomial $p(x) = \sum_{i=0}^d a_i x^i$ with integer coefficients in $[2^k]$ is a permutation polynomial modulo $2^k$ if $p(x) \...
2
votes
0answers
197 views

Can all 3 vector products $\left(\sum_i v_i u_i w_i\right)$ define linear subspace modulo permutation of coordinates?

To determine a set of $n$ numbers modulo permutation, we can use permutation invariants e.g. some symmetric polynomials like $(\sum_i(x_i)^k)_{k=1..n}$. The big question is how to generalize it to ...
1
vote
0answers
36 views

Is a group or a groupoid formed when rearranging a string containing grammar variables?

Consider a finite string $s$ over an alphabet $\Sigma_s$. For example $s = aaaaaaa = a^7, \Sigma = \{a\}$ or $s = ababacababacabc, \Sigma = \{a,b,c\}$. Now what if some of the (disjointly repeated) ...
1
vote
1answer
94 views

6 gentlemen and 3 ladies are to be seated in such a way that every gentleman has a lady by his side.

Find the number of ways in which 6 gentlemen and 3 ladies can be seated around a table so that every gentleman may have a lady by his side. Consider, GLGGLGGLG (G-> Gentleman L-> Lady) 1)The ...
2
votes
2answers
42 views

10 people to be seated in 2 tables with 4 and 6 chairs respectively.

A person invites 10 guests at a dinner party and place them so that 4 are on one round table and 6 on the other round table. Find the number of arrangements. My attempt In first table with 4 seats,...
0
votes
1answer
27 views

What is the formula needed to find possbile permutations in this specefic situation?

I need to find the possible permutations (hope that is the right terminology) given a set of items N where order is important and I'm looking for permutations with M number of consecutive items from N ...
0
votes
1answer
80 views

Enumerate rational numbers in ascending order [duplicate]

Rational numbers are in 1-1 correspondence with natural numbers. For example, let's consider enumeration mentioned in wikipedia: https://en.wikipedia.org/wiki/Rational_number#Properties (https://en....
0
votes
0answers
24 views

Number of permutations with a Spearman's distance below a threshold

Let $[n] = \{1, . . . , n\}$ be a universe of elements. Let $S_n$ be the set of permutations on $[n]$ and for $\pi\in S_n$, let $\pi (i)$ denote the rank of the element $i$. The Spearman’s footrule ...
3
votes
1answer
38 views

$7$ nouns, $5$ verbs and $2$ adjectives are written on blackboard.

$7$ nouns, $5$ verbs, and $2$ adjectives are written on a blackboard. We can form a sentence by choosing $1$ from each available set in any order. Without caring it makes sense or not, what is the ...
1
vote
1answer
28 views

'Twenty persons , of which two are brothers, are to be seated around a circular … ' from Permutation and combination

Question Twenty persons , of which two are brothers, are to be seated around a circular table. Find the number of arrangements in which at least three person between the brothers. My ...
0
votes
0answers
21 views

Circular permutations such that everyone's nearest neighbours are the same

Suppose we want to find the number of ways to make $n$ people sit in a circle. All the arrangements in which everyone has the same nearest neighbours count as the same arrangement. The total number ...
0
votes
1answer
22 views

Why cannot we use $P(n+r-1 , r)$ to calculate permutations when repetition is allowed?

I know we can simply get permutations when repetition is allowed using $$n^r$$ But why cannot we use the normal permutation formula: $P (n, r) $ (repetition is not allowed) but with A little tweak: $$...
1
vote
1answer
17 views

cycle type of product of permutations.

Let $\sigma$ and $\tau$ be two permutations in $S_n$ with partitions $\lambda$ and $\mu$ as their cycle type. What is the cycle type of the product $\sigma \tau$ in terms of $\lambda$ and $\mu$? ...
1
vote
1answer
71 views

Find the centralizer of $(123)$ in $S_6$.

Find the centralizer of $(123)$ in $S_6$. Is there any software to calculate $C_{(123)}$ where $C_{(123)}$ denotes centralizer of $(123)$ in $S_6$. Can anyone say how to write the code to find ...
0
votes
2answers
52 views

Finding permutations using the general theorem on inclusion & exclusion

Count the number of permutations $x_1, x_2, ..., x_{2n}$ of the integers $1$ to $2n$ such that $$x_i + x_{(i+1)} ≠ 2n + 1 \quad \text{for all $i = 1, 2, ..., 2n-1$.}$$ I know I need to use the PIE, ...
5
votes
1answer
57 views

block structure of a subgroup

Let $H \leq S_N$ be a transitive permutation group. A system of blocks $\Sigma = \{\Delta\}$ for $H$ is a partition of $[N]$ such that either $\Delta^h = \Delta$ or $\Delta \cap \Delta^h = \emptyset$. ...
0
votes
1answer
30 views

In what ways the letters of the word “PUZZLE” can be arranged to form the different new words so that the vowels always come together?

I tried this way: Taking 'UE' together and remaining 'PZZL'. So, as 'Z' is repeating, I divide it by $2!$. My answer: $(5!/2!)\cdot 2! = 120$. Is it right? And why do we divide by its factorial if ...
1
vote
2answers
37 views

Letter arrangements of “AAABBC” with length two

"AAABBC" has 3 repetitions of "A" and two repetitions of "B". So total number of arrangements of it with length 2 will be: AA,AB,AC,BA,BB,BC,CA,CB Using permutation we need to do something like: ${...
3
votes
1answer
54 views

Is there an exchange lemma for permutation groups?

I have a set $P$ of permutations of size $s := |P|$. By repeated application of those permutations I can generate $m$ permutations(or reach $m$ states?) that constitute the set $M$. I am unable to ...