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

learn more… | top users | synonyms

5
votes
3answers
149 views

What are good ways to score an ordering?

For context, a friend hosts a pub trivia night and would like to know a good way to score ranking questions. For example, put these five movies from the 70's in order of release: Jaws, Star Wars, ...
2
votes
1answer
153 views

Proving a recursive definition about decreases in permutations

Definition A permutation $\pi = a_1 a_2 \cdots a_n \in S_n \; \; i \in \{1,\cdots,(n-1)\}$ is called a decrease if $a_i > a_{i+1}$. For $k \geq 1$, let $A(n,k)$ be the number of permutations of ...
1
vote
1answer
195 views

The cycle structure of the permutation $a \mapsto ma \bmod{n}$

Given an odd $n$, and an $m$ such that $(n,m)=1$, i would like to know what is the cycle structure of the permutation $\pi_{n,m} (a)=ma\bmod{n}$. Specifically, how do i know if $\pi_{n,m}$ and ...
0
votes
1answer
1k views

Combinations and Permutations Question

I am sitting my A level exams (MEI) and I was looking through the S1 past papers and I encountered this question in the January 2010 paper: Three prizes, one for English, one for French and one ...
6
votes
1answer
163 views

The parity of the permutation $a \mapsto ma \bmod{n}$

I am working on a unique kind of permutations, and would like to know if there is a quick way to know what is the parity of each of them. Given an integer $n$, I can take any integer $m$ for which ...
2
votes
2answers
668 views

Puzzle, Permutation and Combination problem?

I have a puzzle here: There are five colored balls: 2 green, 2 blue and 1 yellow Rule 1: All balls of the same color must be adjacent to each other. I wrote a program to find all the ...
4
votes
1answer
717 views

Number of permutations with a given partition of cycle sizes

Part of my overly complicated attempt at the Google CodeJam GoroSort problem involved computing the number of permutations with a given partition of cycle sizes. Or equivalently, the probability of a ...
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 ...
3
votes
2answers
4k views

How many permutations of a word do not contain consecutive vowels?

The word is "ENGINEERING". The number of ways that the consonants can be ordered is 6! / 3!2! The number of ways that the vowels can be ordered is 5! / 3!2! But how would I determine how many ways ...
6
votes
5answers
629 views

Permutations Problem

i'm having a bit of an issue with solving a permutations problem Find the number of ways in which 4 boys and 4 girls can be seated in a row of 8 seats if they sit alternately. Okay, well.. Simple ...
1
vote
0answers
317 views

Find number of Heads and Tails in Possible Permutations

In my discrete math book we keep coming back to using a coin flip. When doing random variables and expected value they use the coin flip again to figure out how many heads on 3 coin flips. However, ...
4
votes
2answers
1k views

6 Women and 5 Men number of positions problem I don't understand

I have my discrete math final coming up on monday and am trying to figure out how to do a few problems. The one I am having the most problem with is just very confusing because I don't know how to go ...
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 ...
0
votes
2answers
837 views

How many plates can be made?

How many vehicle license plates can be made if the licenses contains 2 letters of the English alphabet followed by a three digit number. If repetitions are allowed. If repetitions are not allowed.
2
votes
2answers
280 views

Sum of Digits divided by 5 and 9?

Using the digits $0,1,2,3,4,5,6,7,8,9$, If five digit numbers is made without the repetition: How many numbers can be made? sum of all the even numbers? sum of all the odd numbers? How many numbers ...
2
votes
1answer
137 views

Problem in Permutation and Combination

In how many way n identical things can be distributed among r different persons where each person may get any number of things. My book gives following ans: (n+r-1)C(r-1) but I am not able to ...
2
votes
1answer
272 views

Permutation/Combination of x,y and z moves

First of all, I am not quite sure but I think the problem asks for a permutation/combination of 13 elements over the {x, y, z} set. Here is the problem: How many ways are there for a spaceship to ...
4
votes
1answer
132 views

A bounded infinite cycle as a product of bounded involutions

Let $\sigma$ be a permutation of $\mathbf Q.$ We call $\sigma$ bounded (the term might be somewhat misleading, but however it is used in a couple of papers) if there is a real number $M$ such that $$ ...
2
votes
4answers
169 views

Is this a kind of Permutation?

I'm trying to design an algorithm to generate something that I don't know how exactly to call! Ok, I'm not a mathematician, I'm studying computer science and thought this would be a great moment to ...
2
votes
1answer
167 views

The setwise stabiliser of a finite set is maximal in Sym(N)

0 So I'm reading a paper which assumes the following statement but I would like to be able to prove it. Let $S=Sym(\mathbb{N})$ denote the symmetric group on the set of natural numbers. If ...
0
votes
4answers
291 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 ...
4
votes
1answer
416 views

Permutation Inversion Questions (3)

Working my way through a combinatorics text and I'm hung up on a couple of questions: 1.) Let $p=p_1 p_2\cdots p_n$ be a permutation. An inversion of $p$ is a pair of entries $(p_i,p_j)$ so that ...
7
votes
1answer
100 views

Upper bound of the number of local swaps

Let $\pi$ be an arbitrary permutation of the set $\lbrace 1,\ldots,n,n+1,\ldots,2n \rbrace$ for some $n \in \mathbb{N}$. We call a swap local if you swap two neighboring positions in $\pi$, i.e. if ...
2
votes
1answer
111 views

Relabelling a permutation

I'm trying to understand the proof of lemma 3.2 of this article by Keith Conrad on proofs of the simplicity of $A_n$. There is a step I don't follow. When he says "Relabelling, we may write ...
1
vote
6answers
825 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. ...
2
votes
2answers
180 views

Sylow $5$-subgroup in $S_{16}$

Find two different $5$-Sylow subgroups in $S_{16}$. Hint: use group multiplication. Any hints?
1
vote
1answer
189 views

Conjugacy class of a permutation from its matrix representation

Apologies if this is too basic, but given a permutation matrix $M$, is there any parameter or formula based on $M$ that gives the disjoint cycle decomposition, or at least the conjugacy class, of the ...
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
487 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
444 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
783 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
356 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
188 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
607 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
930 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
201 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
653 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
647 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
281 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
315 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 ...