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
2
votes
1answer
132 views

Looking for “average” of two permutations

I am a computer programmer and I am building a search engine for a client. Right now I am puzzling myself about the order in which I should return search results. There are two obvious orderings: ...
5
votes
2answers
9k views

Product of Non-Disjoint Cycles

I am trying to learn how to find the product of non-disjoint cycles, as you may have guessed from the title. I have the basic idea, but I do not understand it entirely. I am trying to find $(1352)(...
0
votes
1answer
2k views

Generate number for 49/6 lottery

I want to generate all possible combination of six number from 49 balls. We can say 49/6 lottery numbers also. http://en.wikipedia.org/wiki/Lotto_6/49 When we calculate the possible combination of (...
4
votes
4answers
823 views

How to read permutation symbols like $(123)$?

I'd be grateful for some help reading permutation symbols such as $(123)$. Does it mean, when applied to a target sequence such as $(x y z w)$, "replace the element in the first slot of the target ...
1
vote
2answers
79 views

approximate the probability of fixed length string segments match

say, i have got 3x'a', 5x'b', 2x'c',4x'd', as char collection. 2 strings are formed, each consists of all the chars given. eg. string A = 'aaabbbbbccdddd' B='abcdabcdabbbdd' so both strings have ...
1
vote
1answer
904 views

Permutation Problem with a Variable

13P5 = 1287(xPx) I simplify the above to: 13!/8! = 1287(x!) The expression on the left simplifies to 154,440. I divide both sides by 1287 to get: 120=x! At this point I'm stumped. Thanks in ...
0
votes
2answers
1k views

Combinations problem with conditional combination

I'm very bad at maths and I've a situation where I need to find number of combinations for a real world situation. I've 50 files and set of permissions can be given to users on those files such as ...
0
votes
0answers
76 views

Basic Sample Spaces and Events Question [duplicate]

Possible Duplicate: Why is the number of possible subsequences 2^n? I'm brushing up on my probability skills and the text asks the following question: For the sample space {A, B, C, D}, ...
0
votes
1answer
967 views

Permutations or Combinations with less objects than spots

Permutations mean: take n objects and put them in to k spots, order matters ($abc \neq acb$) Combinations mean: take n objects and put them in to k spots, order doesn't matter ($abc = acb$) But what ...
3
votes
1answer
240 views

Finding all results of a permutation group on a set

Given a finite group $G < Sym(\Omega)$; $\Omega$ finite, and $X \subset \Omega$, I can define a by the function $H(g) = \{x^g \| x \in X\}$ for each $g \in G$. Of course, each $H$ has the same ...
4
votes
1answer
69 views

Stricter permutation patterns

A lot of work has been done on patterns in permutations, where a permutation is said to match a given pattern if it contains a subsequence of elements ordered according to the pattern (e.g., $\pi=(2\ ...
16
votes
2answers
1k 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 = ...
45
votes
4answers
23k 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?
2
votes
2answers
124 views

Avoidance of two permutations

Let $1 \leq m \leq n, \sigma \in S_n, \pi \in S_m$. The permutation $\sigma$ avoids $\pi$ if no subset $\{j_1 < \cdots < j_m\} \subseteq \{1,\cdots,n\}$ exists, so that for all $1 \leq i < l \...
2
votes
3answers
746 views

Number of digits in a series of numbers

I have a list of the numbers from 1 to 1000. How can I find the number of 0's, 1's, 2's, and 9's that are used? The answers are 192, 301, 300, 300 respectively, but I'm interested in the process ...
3
votes
3answers
6k views

Permutation/Combinations in bit Strings

I have a bit string with 10 letters, which can be {a, b, c}. How many bit strings can be made that have exactly 3 a's, or exactly 4 b's? I thought that it would be C(7,2) + C(6,2), but that's wrong (...
1
vote
2answers
1k views

Order normalizer permutation

I would like to know how is possible to calculate the order of the normalizer of $H=\langle s\rangle$ in $S_n$ where $s$ is an assigned permutation of $S_n$. I know that finding the order of the ...
9
votes
4answers
688 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 ...
0
votes
2answers
657 views

Proof of Permutations

With repetition allowed, You multiply the r number of times for total n objects n * n * n ... When the repetion is not allowed then you take away an object ...
2
votes
1answer
548 views

Combination or Permutation?

I read this puzzle as below. You have 40 boxes, all placed in a row at exact intervals of 1 meter. You also have 9 balls(all same type). You wish to place all the balls in the boxes, no ...
0
votes
1answer
641 views

Mathematical permutation drawing/visualization tool

I'm writing software and need to document an existing mathematical permutation in our code. I thought the folks here would know where I can find a drawing/visualization tool to draw a permutation ...
2
votes
2answers
711 views

Simple Combination Formula

Sorry for this simple question: I'm looking for the formula to calculate all the possible combinations from a set of $n$ numbers, where you can select $r$ numbers at once where $r$ can be $0, 1, \...
6
votes
2answers
206 views

Why are the periods of these permutations often 1560?

I ran across a math puzzle that went like this: Consider the list $1,9,9,3, \cdots$ where the next entry is equal to the sum mod 10 of the prior 4. So the list begins $1,9,9,3,2,3,7,\cdots$. Will ...
1
vote
1answer
296 views

How many permutations are there if you have n+1 items, where the extra item can be repeated?

This is a little different than the normal case of permutations with repetition. Basically, let's say we have $n$ numbered balls, and there are $n$ spots. However, we can leave a spot empty if we want....
8
votes
2answers
176 views

On doubly graceful permutations

A permutation $\sigma\in\mathfrak S_n$ is graceful if $$\{|\sigma(i+1)-\sigma(i)| \text{ with } 1\leq i\leq n\}=\{1,2,\ldots,n-1\}$$ (terminology coming from a more general definition in graph theory)....
3
votes
1answer
890 views

Sorting a deck of cards with Bogosort

Suppose you have a standard deck of 52 cards which you would like to sort in a particular order. The notorious algorithm Bogosort works like this: Shuffle the deck Check if the deck is sorted. If it'...
0
votes
1answer
565 views

Connected and Disconnected Permutations

Martin Klazar's paper Irreducible and connected permutations (pdf) states: We call a permutation $\pi$ of $[n] = \{1, 2, \ldots, n\}$ disconnected iff there is an interval $I \subset [n]$, $2 \...
2
votes
1answer
192 views

What is the name of this special type of n-tuple?

Consider the set, $S$, of $n$-tuples defined inductively as follows: $(1, 2, \ldots, n) \in S$ if $(x_1, x_2, \ldots, x_i, x_{i+1}, \ldots, x_n) \in S$, then $(x_{i+1}, \ldots, x_{n}, x_1, x_2, \...
4
votes
3answers
4k 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 ...
2
votes
0answers
672 views

Anti-prime sequence

I have permutation from $x$ to $y$. And how to make sequence which $d$ summed numbers from this sequence ISN'T a prime number. if we have sequence $x_1,x_2,x_3,x_4,x_5 \dots y$ than $d$ means : $x_1+...
7
votes
3answers
222 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, ...
3
votes
1answer
278 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
297 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 $\pi_{...
0
votes
1answer
5k 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 for ...
6
votes
1answer
202 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
2k 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 ...
5
votes
1answer
3k 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 ...
38
votes
6answers
63k 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 four ...
4
votes
2answers
16k 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 ...
7
votes
5answers
1k 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.. ...
1
vote
0answers
785 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, ...
5
votes
2answers
2k 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 ...
3
votes
1answer
441 views

Cyclic permutations without consecutive integers?

I am trying to find the number of cyclic permutations ,$A(n)$, of $\{1,2,3,...,n\}$ without any two consecutive integers together. The second part of the problem is to prove that $A(n+1)+A(n)=D(n)$ [...
7
votes
1answer
1k 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
10k 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.
3
votes
2answers
722 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: $1.$ How many numbers can be made? $2.$ sum of all the even numbers? $3.$ sum of all the odd numbers? $...
2
votes
1answer
251 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
811 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 ...
42
votes
3answers
58k views

Multiplication in Permutation Groups Written in Cyclic Notation

I didn't find any good explanation how to perform multiplication on permutation group written in cyclic notation. For example, if $$ a=(1\,3\,5\,2),\quad b=(2\,5\,6),\quad c=(1\,6\,3\,4), $$ then ...
4
votes
1answer
157 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 $$ ...