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

learn more… | top users | synonyms

7
votes
3answers
583 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 ...
15
votes
5answers
12k 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 ...
4
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 ...
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
914 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 ...
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...
0
votes
1answer
112 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
165 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 ...
23
votes
1answer
453 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 ...
6
votes
4answers
624 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?
12
votes
4answers
3k 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?
5
votes
1answer
450 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
345 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$. ...
7
votes
1answer
525 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
477 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
231 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 ...
6
votes
1answer
558 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 ...
3
votes
1answer
128 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 ...
20
votes
2answers
535 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 ...
8
votes
2answers
655 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
333 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
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 ...
12
votes
4answers
9k 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 ...
9
votes
2answers
2k 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 ...
8
votes
4answers
326 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
435 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 ...
3
votes
3answers
510 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 ...
2
votes
0answers
172 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
224 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
876 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
0answers
192 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
144 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
45 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 ...
1
vote
2answers
596 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 = ...
7
votes
2answers
265 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}$ ...
4
votes
1answer
217 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
735 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
83 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
97 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
631 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. ...
0
votes
1answer
106 views

proving bitstrings [duplicate]

1.Let it be $a_n$ the number of bitstrings which contain 000 How would I prove that for $n\ge4$: $$a_n = a_{(n-1)} + a_{(n-2)} + a_{(n-3)} + 2^{n-3}$$
0
votes
1answer
187 views

permutation with cycles

Let $c(n,k)$ be the number of permutations of $[n]$ with $k$ cycles. I am looking for a proof of the following. $c(n,k)=(n-1)c(n-1,k)+c(n-1,k-1)$ for $n,k \geq 1$ and $c(0,0)=1$ The number of ...
0
votes
1answer
641 views

How to find the Circular permutation with Repetition [duplicate]

Possible Duplicate: In how many ways we can put $r$ distinct objects into $n$ baskets? Need some guidance with the following problem : There are 'n' different types of objects which needs ...
0
votes
4answers
267 views

Factorial of 0 - a convenience?

If I am correct in stating that a factorial of a number ( of entities ) is the number of ways in which those entities can be arranged, then my question is as simple as asking - how do you conceive the ...
-1
votes
2answers
73 views

Combinations of the word REMEMBRANCE

4 letters must be chosen from the word REMEMBRANCE How many different selections can be done if there is no M, no R and at least 2 Es? I've seen this question somewhere but i don't remember the ...
8
votes
1answer
988 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 ...