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

learn more… | top users | synonyms

8
votes
3answers
631 views

Number of permutations where n ≠ position n

I am trying to figure out how many permutations exist in a set where none of the numbers equal their own position in the set; for example, 3,1,5,2,4 is an acceptable permutation where 3,1,2,4,5 is not ...
11
votes
1answer
2k views

6-letter permutations in MISSISSIPPI

How many 6-letter permutations can be formed using only the letters of the word, MISSISSIPPI? I understand the trivial case where there are no repeating letters in the word (for arranging smaller ...
4
votes
2answers
1k views

Counting number of moves on a grid

Imagine a two-dimensional grid consisting of 20 points along the x-axis and 10 points along the y-axis. Suppose the origin (0,0) is in the bottom-left corner and the point (20,10) is the top-right ...
5
votes
2answers
1k views

Derivation of the Partial Derangement (Rencontres numbers) formula

I'm looking for the method by which the partial derangement formula $D_{n,k}$ was derived. I can determine the values for small values of N empirically, but how the general case formula arose still ...
16
votes
5answers
17k views

Combination of smartphones' pattern password

Have you ever seen this interface? Nowadays, it is used for locking smartphones. If you haven't, here is a short video on it. The rules for creating a pattern is as follows. We must use ...
33
votes
3answers
2k views

What is the shortest string that contains all permutations of an alphabet?

What is the shortest string $S$ over an alphabet of size $n$, such that every permutation of the alphabet is a substring of $S$? I thought of this problem while reading a open problem on shortest ...
6
votes
4answers
2k views

Exponential Generating Functions For Derangements

I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this ...
0
votes
1answer
927 views

How many permutations of $N$ number that sum of every two adjacent is at most $M$

Moderator Note: This is a current contest question on codechef.com. This codechef.com contest ended on $17$ June. —Brian M. Scott Given two integers $N$ and $M$, find how many permutations ...
12
votes
4answers
4k views

Why are two permutations conjugate iff they have the same cycle structure?

I have heard that two permutations are conjugate if they have the same cyclic structure. Is there an intuitive way to understand why this is?
6
votes
4answers
2k views

every permutation is either even or odd,but not both

How we can show every permutation is either even or odd,but not both......I can't arrive at a proof for this ..... Can anybody give me the proof... Thanks in advance...
8
votes
1answer
505 views

Can someone explain Cayley's Theorem step by step?

This is from Fraleigh's First Course in Abstract Algebra (page 82, Theorem 8.16) and I keep having hard time understanding its proof. I understand only until they mention the map $\lambda_x (g) = xg$. ...
0
votes
1answer
122 views

Finding the “square root” of a permutation

Suppose $r$ is odd, and ${\rm ord}(\alpha)=r$. ($\alpha,\beta$ are cycles.) Now, $\alpha=(a_1\cdots a_n)$. I need to find $\beta$ that will make $$\alpha = \beta^2$$ How can I show it? What I ...
5
votes
2answers
178 views

Number of bitstrings with $000$ as substring

I have $F_n$ number of bitstrings that have $000$, How would I prove that for $n \ge 4$ , $a_n = a_{n-1} +a_{n-2}+a_{n-3}+ 2^{n-3}$? Now there are many ways to go about this but if I choose starting ...
3
votes
1answer
137 views

Rearrangement of groups such that no two members meet again

Suppose that we are given $n$ groups of $m$ people. We want to rearrange these $nm$ people into the same format of $n$ groups of $m$ with that the catch that any two people who were originally in a ...
23
votes
1answer
478 views

“Efficient version” of Cayley's Theorem in Group Theory

I'm considering finite groups only. Cayley's theorem says the a group $G$ is isomorphic to a subgroup of $S_{|G|}$. I think it's interesting to ask for smaller values of $n$ for which $G$ is a ...
7
votes
5answers
669 views

How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters?

How many arrangements of $\{a,2b,3c,4d, 5e\}$ have no identical consecutive letters? I find it very tough... Could anyone have some good ways?
6
votes
3answers
592 views

Show group of order $4n + 2$ has a subgroup of index 2.

Let $n$ be a positive integer. Show that any group of order $4n + 2$ has a subgroup of index 2. (Hint: Use left regular representation and Cauchy's Theorem to get an odd permutation.) I can easily ...
8
votes
1answer
1k views

Centralizer of a given element in $S_n$?

It is known that any two disjoint cycles in $S_n$ commutes. Therefore, any $\pi\in S_n$ which is disjoint with $\sigma$ is in the centralizer of $\sigma$: $C_{S_n}(\sigma)$. Also $$ \sigma^i\pi\in ...
12
votes
4answers
11k views

How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other?

I have a homework problem in my textbook that has stumped me so far. There is a similar one to it that has not been assigned and has an answer in the back of the textbook. It reads: How many ways ...
5
votes
1answer
514 views

Why is $S_5$ generated by any combination of a transposition and a 5-cycle?

Why is $S_5$ generated by any combination of a transposition and a 5-cycle? Is this true for any prime $p$ (in this case $p=5$)?
7
votes
1answer
603 views

number of combination in which no two red balls are adjacent.

given x spaces(you can fit 1 ball in 1 space) and unlimited number of identical red and white balls, find the total number of combinations in which no two red balls are adjacent to each other. i ...
3
votes
2answers
567 views

What will be total number of solutions of $a+b+c = n$?

Please tell me how to find the total number of intergral solutions of $$ a+b+c=n $$ I already know that total number of solutions will be $(n+3-1)c(3-1)$. But what will be the case when a varies from ...
1
vote
0answers
274 views

Finding the number of arrangement of N people of different height such that K of them are visible from front

Moderator Note: This is a current contest question on codechef.com. [Initially, I had asked this question in stackoverflow, but someone suggested to post it here, and hence this question is ...
7
votes
2answers
331 views

Bubble sorting question

Consider that we use the bubble-sorting algorithm to sort a string of size $n$. We know then that the maximum number of swaps results when the string is in reverse order- this gives $\frac{n(n-1)}{2}$ ...
6
votes
1answer
607 views

Conjugacy classes in $A_n$.

Suppose $n$ is a non negative integer $\geq 4$ and $\sigma\in S_n$ a permutation. Conjugacy classes in $S_n$ are completley determined by the cycle structure of $\sigma$. If we let the alternating ...
22
votes
2answers
592 views

Can $G≅H$ and $G≇H$ in two different views?

Can $G≅H$ and $G≇H$ in two different views? We have two isomorphic groups $G$ and $H$, so $G≅H$ as groups and suppose that they act on a same finite set, say $\Omega$. Can we see $G≇H$ as permutation ...
14
votes
2answers
642 views

Shortest sequence containing all permutations

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 = ...
8
votes
2answers
724 views

Span of Permutation Matrices

The set $P$ of $n \times n$ permutation matrices spans a subspace of dimension $(n-1)^2+1$ within, say, the $n \times n$ complex matrices. Is there another description of this space? In particular, ...
8
votes
2answers
363 views

Probability of opening all piggy banks

Interesting problem I found, and can't solve it since the morning: We have $n$ keys and $n$ piggy banks. Each key fits only one piggy bank. We randomly put exactly one key in each piggy bank. Then ...
4
votes
1answer
565 views

Proving that $A_n$ is the only proper nontrivial normal subgroup of $S_n$, $n\geq 5$

There is a famous Theorem telling that: For $n≥5$, $A_n$ is the only proper nontrivial normal subgroup of $S_n$. For the proof, we firstly start with assuming a subgroup of $S_n$ which ...
4
votes
3answers
1k views

Combination problem with constraints

You have four containers and one pitcher of water that holds 100L. Each container has different capacities with maximums of, say...70L, 45L, 33L and 11L levels respectively. What is the formula that ...
9
votes
2answers
3k views

Given 5 children and 8 adults, how many ways can they be seated so that there are no two children sitting next to each other. [duplicate]

Possible Duplicate: How many ways are there for 8 men and 5 women to stand in a line so that no two women stand next to each other? Given 5 children and 8 adults, how many different ways ...
4
votes
2answers
70 views

Probability that two random permutations of an $n$-set commute?

From this MathOverflow question: It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. -- Benjamin ...
8
votes
4answers
348 views

Unique Groups for Game Tournament

I am trying to put together a Munchkin game tournament where I am assuming I will have 16 people coming to my tournament. As part of that, I want to have as many games as possible where people are not ...
6
votes
1answer
455 views

Number of $(0,1)-$matrices with exactly two $1$'s in each row and column

Consider a matrix $A$ of size $n\times n$. I want to fill it with one and zero such that there are exactly two entries one in each row and each column, and the other entries are zero. In how many ...
2
votes
0answers
178 views

Is it possible to find sum of this series?

I am trying to find the sum of the following series asked by my friend. $$n\cdot\left(\bigl\lfloor\tfrac{n}{2}\bigr\rfloor+ \bigl\lfloor\tfrac{n}{3}\bigr\rfloor+ \bigl\lfloor\tfrac{n}{4}\bigr\rfloor+ ...
2
votes
3answers
229 views

Let $\alpha=(1234)(5876)$ and $\beta=(1537)(2648)$ belong to $S_8$.

Let $\alpha=(1234)(5876)$ and $\beta=(1537)(2648)$ belong to $S_8$. Determine whether there exists a subgroup of $S_8$ that contains $\alpha$ and $\beta$ and is isomorphic to $D_4$.
2
votes
2answers
685 views

Irreducibility of the standard representation of $S_n$.

The permutation representation of $S_n$ is $\mathbb C^n$ with elements of $S_n$ permuting the basis vectors $\{e_1, e_2, \ldots, e_n\}$. It has a trivial subrepresentation spanned by the vector $v = ...
2
votes
2answers
893 views

Combinatorics-number of permutations of $m$ A's and at most $n$ B's [duplicate]

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.
1
vote
1answer
92 views

Permutation proofs

I have just started going though "An Introduction to the theory of groups" by J.J Rotman. I have questions above the following two exercises: " The identity function $1_X$ on a the set $X$ is a ...
1
vote
0answers
195 views

Modular arithematic Equation

We have an equation: $a^x+b^x+c^x \equiv m \pmod n $ also given $a,b,c < y $ what are the total number of solutions of this equation?
1
vote
1answer
185 views

Solving conjugacy equations in dihedral groups.

For all integers $m$ such that $0≤m<n$ find $a,b,c\in D_n$ such that $a(rR^m ) a^{-1}=R^2$ $b(rR^m ) b^{-1}=r$ $c(rR^m ) c^{-1}=rR$ $D_n$ is dihedral group of an $n$-gon represented by ...
1
vote
1answer
49 views

Number of ways of getting valid change

A movie theater charges $50$ Rupees for a ticket. The cashier starts out with no change, and each change customer pays with a Rupees $50$ note or Rupees $100$ note (& gets change). Clearly, the ...
4
votes
1answer
276 views

Finding a permutation, and number of, from powers of the permutation

Sorry for the vagueness of the title, I couldn't think of a better way to put it. I just wanted to run a couple of simple questions past SE to check my reasoning is correct etc. Find a permutation ...
4
votes
3answers
792 views

Composition of permutation to generate all permutations

Looking at permutations I came up with the following question: Can you find a permutation S of a set of n elements such that by composing this permutation n! times you will describe all the possible ...
3
votes
1answer
144 views

Distributing $n$ different things among $r$ persons

How can $10$ different pencils be distributed among $3$ students? MY TRY $1$ total ways $= 3^{10}$ MY TRY $2$ $10 \times 9 \times 8 =720$ Which one is correct? If both are wrong what is correct ...
3
votes
1answer
84 views

Primitive Permutation Group with Subdegree 3

This is exercise 8B.7 in Isaacs's Finite Group Theory. Let $G$ be a primitive permutation group on $\Omega$, and let $H$ be the stabilizer of $\alpha\in\Omega$. Suppose $H$ has an orbit of size $3$ ...
2
votes
2answers
2k views

How do I determine the possible number of combinations of two ordered sets?

I'm not quite sure what the mathematical term for what I'm asking is, so let me just describe what I'm trying to figure out. Let's say that I have two ordered sets of numbers {1, 2} and {3, 4}. I'm ...
1
vote
5answers
106 views

Order of Permutation : If $\tau \in S_n$ has order $m$, then $\sigma \tau\sigma^{-1}$ has also order $m$.

I dont understand the following very simple statement: If $\tau \in S_n$ has order $m$, then $\sigma \tau\sigma^{-1}$ has also order $m$. The proof is: Suppose $\tau$ has order $m$. $(\sigma \tau ...
1
vote
6answers
800 views

Why is the number of possible subsequences $2^n$?

If anyone here is familiar with the Lowest Common Subsequence problem, they probably know that the number of posibble subsequences in a sequence is $2^n$; $n$ being the length of the sequence. ...