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

learn more… | top users | synonyms

0
votes
1answer
208 views

Permutation group proofs

1) Let $p$ be an odd prime, $n$ an integer such that $n \geq 3p$ and $a$ a $2p$-cycle in $S_n$. Let $b$ be a $p$-cycle in $S_n$ and assume that $a$ and $b$ are disjoint. Suppose $K$ is a subgroup of ...
12
votes
2answers
490 views

How many $n\times m$ binary matrices are there, up to row and column permutations?

I'm interested in the number of binary matrices of a given size that are distinct with regard to row and column permutations. If $\sim$ is the equivalence relation on $n\times m$ binary matrices such ...
2
votes
3answers
446 views

Arrangement of six triangles in a hexagon

You have six triangles. Two are red, two are blue, and two are green. How many truly different hexagons can you make by combining these triangles? I have two possible approachtes to solving this ...
3
votes
1answer
115 views

Equation on permutations

In a group of permutations of $n$ elements, there are two permutations $P_1$ and $P_2$ such that $P_2=P_1^e$. $P_1$ and $P_2$ have the same order $o$: $P_1^o = P_2^o$. How can I find $e$? $n$, $P_1, ...
5
votes
3answers
785 views

expected number of shuffles to sort the cards

Initially the deck is randomly ordered. The aim is to sort the deck in order. Now in each turn the deck is shuffled randomly. If any of the initial or last cards are in sorted order then they are kept ...
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 ...
3
votes
0answers
357 views

Multinomial Coefficients ! [closed]

I have come across a paper that has suggested a formula for "NUMBER OF MULTINOMIAL COEFFICIENTS NOT DIVISIBLE BY A PRIME"; but I don't understand the notation.Please help. The formula is: $ G(n,l,p)= ...
3
votes
2answers
189 views

A subset of permutations on the set S such that the elements that are within T, a subset of S, are not exchanged with elements outside of T

Sorry about the title, I have no idea how to describe these types of problems. Problem statement: $A(S)$ is the set of 1-1 mappings of $S$ onto itself. Let $S \supset T$ and consider the subset ...
5
votes
2answers
111 views

Do bounded permutations of N leave an initial segment invariant?

Let $p$ be a permutation of $\mathbb{N}$. We say that $p$ is bounded if there exists $k$ so that $|p(i)-i| \le k$ for all $i$. If $p$ is bounded, must there exist $M>0$ such that $p(\{1,2,\ldots, ...
5
votes
1answer
613 views

Using one stack to find number of permutations

Suppose I have a stack and I want to find the permutations of numbers 1,2,3,...n. I can push and pop. e.g. if n=2: push,pop,push,pop 1,2 and push,push,pop,pop 2,1 if n=4 I can only get 14 from the ...
2
votes
0answers
291 views

how many ways to construct a number

I am thinking about following problem, but am not able to find answer. In how many ways can a number be formed only using 3 digits (0, 1, 2) given following constraints with K and D:- 1) Each digit ...
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 ...
3
votes
1answer
205 views

Complexity of counting the number of Good-perfect matching in bipartite graph

Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$. Definition1: ...
6
votes
1answer
940 views

Permutation with Duplicates

I could swear I had a formula for this years ago in school, but I'm having trouble tracking it down. The problem: I have 3 red balls and 3 black balls in a basket. I draw them out one at a time. How ...
3
votes
2answers
2k views

Can someone explain the algorithm for composition of cycles?

Let $\sigma=(1\ 3),\ \tau=(2\ 4\ 5),\ \pi=(2\ 3\ 4) \in S_{5}$. Find $\pi\circ\tau\circ\sigma$. I know the solution is $(1\ 4\ 5\ 3)$. What i'm doing now is writing the permutations in the ...
5
votes
1answer
202 views

Permutation Identity and Sum

Show that $\displaystyle 1+ \sum\limits_{k=1}^{n} k \cdot k! = (n+1)!$ RHS: This is the number of permutations of an $n+1$ element set. We can rewrite this as $n!(n+1)$. LHS: It seems that the $k ...
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 ...
11
votes
5answers
657 views

Probability that a random permutation has no fixed point among the first $k$ elements

Is it true that $\frac1{n!} \int_0^\infty x^{n-k} (x-1)^k e^{-x}\,dx \approx e^{-k/n}$ when $k$ and $n$ are large integers with $k \le n$? This quantity is the probability that a random permutation ...
8
votes
3answers
659 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 ...
6
votes
2answers
282 views

Number of terms in a monomial symmetric polynomial

Is there a closed form expression for the number of terms in a monomial symmetric polynomial in a given number of variables for a particular partition of exponents, in terms of which/how many ...
3
votes
1answer
407 views

Determine sign of a permutation, calculate number of elements in the subgroup of permutations with sign = 1

Question: (a) Determine sign$(\tau)$ for $$\left( \begin{array}{ccccccc} 1&2&3&4&5&6&7 \\ 2&3&5&7&1&6&4 \end{array} \right )$$. (b) Let $A_{n} = ...
3
votes
2answers
229 views

Is the set of permutations in $S_{36}$ that move at most 4 elements a subgroup of $S_{36}$?

I am truly lost as to what this problem is asking. I did post this on another forum and received what my have been wonderful advice. However, even after multiple hours and many "Google" searches I ...
5
votes
2answers
317 views

Array of numbers, how many solutions/ways?

Let's say, we have an array/matrix $n \times m$ and we need to find, how many ways can we fill this array with numbers from $\{ 1, \ldots , m\cdot n \}$, but: 1) every number can be used only 1 time ...
12
votes
4answers
12k 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 ...
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 ...
1
vote
2answers
216 views

Simple Combination/Permutation Question

Ok, so this might not be a permutation or combination but I'm curious as to what the answer is. Question: There are 3 groups and 5 Objects in each group. How many combinations are there if your ...
2
votes
1answer
166 views

Issue with permutation problem

The question is: Given a licence plate that can have either 2 or 3 letters followed by either 2 or 3 numbers, how many different license plates can be printed. My math is as such $(26^2 + ...
7
votes
2answers
691 views

Permutations of a set that keep at least one integer fixed

what is the number of permutations of a set say {1, 2, 3, 4, 5} that keep at least one integer fixed ?
3
votes
1answer
255 views

There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?

There is a 5 by 5 matrix of points on a plane. How many triangles can be formed using points on this matrix?
4
votes
1answer
1k views

Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.
1
vote
1answer
321 views

Permutations and Combination rearrangement

I approached this exam question the wrong way apparently, help please? Consider the word "mathematics". In how many ways can you rearrange all the letters so that the vowels are paired and ...
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 ...
2
votes
1answer
213 views

When does an orthomorphism of the cyclic group exist?

I thought I would post (as a puzzle) one of my favourite results in combinatorics. I actually use variants of this result in research quite often. It's not impossible that someone will post an ...
1
vote
1answer
53 views

Possible variations in a bilateral symmetric system

Can someone shed a light on how to solve something like this? I've been looking for permutations but so far I found it very confusing. As I'm not at home atm, I can't reach for my math books either ...
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...
2
votes
2answers
242 views

Help me out on permutation and combination

I have to get all combinations of a six digit number where each digit is unique. Its clear that this combination will not have a 0 at the start as it will not be a valid six digit number. Help me on ...
11
votes
2answers
444 views

What do all the $k$-cycles in $S_n$ generate?

Why don't $3$-cycles generate the symmetric group? was asked earlier today. The proof is essentially that $3$-cycles are even permutations, and products of even permutations are even. So: do the ...