Permutations Definition and 292 Threads

I'm looking at a card shuffle. And in shuffle would be the permutation (1, 2, 3, ..., n, n+1, n+2, n+3, ...2n) to (2, 4, 6, ..., 2n 1, 3, 5, ...2n-1) I know that it would take 52 perfect shuffles to get the deck of cards back in the original order. I think that I'm supposed to show this using...

What's the difference between these two: 1) The number of permutations of n distinct objects taken r at a time is \frac{n!}{(n-r)!} and 2) The number of combinations of n distinct objects taken r at a time is \frac{n!}{r!(n-r)!} ?

Homework Statement Not really a problem, just my understanding. What is the difference between them? I know the formulae are different. They seem to be the same thing, that is, n objects taken r at a time. Any help in clarifying this would be appreciated.

This seems like it should be easy, but my combinatorics is (are?) a little rusty. I want to know how many permutations of a given length leave at least one element unchanged, and how many leave exactly one unchanged. Started wondering about it when picking names out of a hat for a secret...

Hi, Was wondering if anyone could explain to me what an adjacent transposition is (in relation to permutations, cycles etc). I know what a transposition is, eg the product of transpositions for (34785) would be (35)(38)(37)(34). I don't know what an adjacent transposition is though...

Homework Statement x^2 = sigma. The permutation sigma = (1 2 6 7 5 3 4), a cycle of length seven. Determine x! The Attempt at a Solution I have tried a few times but my attempts are totally wrong. I don't know where to start! :S I found a similar problem in the textbook. They...

hi, I had a question regarding the rc4 stream cipher. I understand it is a bunch of permutations to the initial Array that goes from 0 to 255 with respect to the key. However is there such a key such that after the permutation S is still the same? (ie still goes from 0 to 255)? Any help...

Homework Statement Let A, B be permutations and A = (1 3 5 10)(3 15 8)(4 14 11 7 12 9) and B = (1 14)(2 9 15 13 4)(3 10)(5 12 7)(8 11) Find AB. Homework Equations The Attempt at a Solution I am struggling with finding the product of this permutations and can't quite get the...

Homework Statement Here are two problems that i am striving with: 1. Let \theta be the s-cycle (123...s). (i) what is the smallest positive integer m such that \theta^h=\theta^k when h\equiv k(mod m)? NOte: This is not actually a homework problem, but since the other one that...

What is the expected number of fixed points in permutations? I got 1 as answer.

Homework Statement How many contestants have on one chess tournament, if every person have played only one game with all of the other contestants separately, and there are 210 games played. This problem should not be solved by variations, permutations or combinations. This problem should...

Homework Statement The letters of the word POSSESSES are written on 9 cards, one on each card. The cards are shuffled and four of them are selected and arranged in a straight line. Homework Equations (a) how many possible selections are there of 4 letters? (b"how many arrangements are...

an "infinite" amount of permutations, Look at how the sum of the alternating harmonic series can be changed by rearranging the terms: http://mathworld.wolfram.com/RiemannSeriesTheorem.html But doesn't this involve a non-finite amount of permutations? If this counts as a rearrangement then...

Homework Statement Consider the group D4 (rigid motions of a square) as a subgroup of S4 by using permutations of vertices. Identify all the even permutations and show that they form a subgroup of D4. The Attempt at a Solution I think I have the permutations of correct. They are...

When proving that A_n with n \geq 5 is simple, we require the following lemma: If N is a normal subgroup of A_n with n \geq 5 and N contains a 3-cycle, then N = A_n. The proof is actually given for us in the lecture notes, however he utilizes a formula that I'm not sure how he derived: Let f...

:cry: I can't solve it, please helpppp! problem :- there are 8 points in a plane (non collinear) find the maximum number of triangles formed out of these points such that no 2 triangles have more than one common vertex.

In theory I'm done this question, but would like to get it checked. 22) How many permutations of the letters ABCDEFGH contain c) the strings BA and FGH? Answer: 5 objects: BA, C, D, E, FGH. Total: 5! = 120 This is following the example in the book. However, the example only has...

Homework Statement Suppose that a basketball league has 32 teams, split into two conferences of 16 teams each. Each conference is split into three divisions. Suppose that the North Central Division has five teams. Each of the teams in the North Central Division plays four games agains each of...

I don't have any example of this in my notes: I have the permutation p1 = (1 5)(2 4 6 3) and the permutation p2 = (1 3 7 4)(2)(5 8 6) and I have to find p2 * p1 i THINK you take it in the form p1 then p2, like: (1 5)(2 4 6 3)(1 3 7 4)(2)(5 8 6) = ... But them I'm stuck. I...

Permutations (last question of sheet, yay!) 1. Homework Statement [/b] \eta:= (1 2 ... n-1 n) (n n-1 ... 2 1) \inS_{n} for any n\inN n.b That should be 2 lines all in one large bracket btw a.) Determine its sign. b.) Let n \geq1. Let <a1,...,as> \inSn be a cycle and let...

Randomly permute (1,...,n). What is the probability that exactly i points are fixed? I think it should be \binom{n}{i}\frac{(n-i-1)!}{n!} Is it right? If so, is the expected number of fixed points (I know it's 1): \sum_{i=0}^{n}i\binom{n}{i}\frac{(n-i-1)!}{n!} But it doesn't sum to 1, I think

For fixed n\in\mathbb{N}, how many permutations X\in S_n there exists, so that X(t)=t at least for some t\in\{1,2,3,\ldots,n\}? Is the solution to this well known? I couldn't solve it by the most direct approach that seemed to be the only apparent way. This is how far I got: Question 1: How...

I have been asked to show that in Sn the cycle (1,2,...n) only commutes with its powers. I know that cycles commute when they are disjoint and that every permutation can be written as a product of disjoint cycles but how do i show that this cycle and its powers are disjoint? PLz help...

Homework Statement Show that for every subgroup H of S(n) [the symmetric group on n letters] for n>=2 either all the permutations in H are even or exactly half of them are even. Homework Equations The Attempt at a Solution I didn't really know how to do this but i thought maybe...

need help on this? well guys i was doing some problems with series and i cam up with this problem, i think it belongs to combinatorics but i'll post it here. How is defined the permutations, combinations and variatons of negative numbers. For example if you were required to find the...

Homework Statement How many 3 digit numbers can be constructed from digits 1, 2, 3, 4, 5, 6, and 7 if each digit may be used once only and the number is odd? 2. The attempt at a solution What number do they speak of? The resulting 3 digit number? How do I approach this equation?

Hi, I was answering what I thought was an easy problem and I got it wrong, but not sure why. Please give me an insight. Problem: 12 juniors are ordered (in a line) for a drill. What's the probability (assuming all arrangments are random) of Dave standing next to Beth? My reasoning...

I need to find: 1. let n be a natural number compute the number of permutations s:{1,...,3n}->{1,...,3n} on 3n terms that satisfies s(n)<s(2n)<s(3n). 2. compute the number of permutations s:{1,...,n}->{1,..,n} that satisfy: for every i,j in 1,..,n |s(k)-s(j)|<=|k-j| for the first question i...

Homework Statement A deck of cards is shuffled and then divided into two halves of 26 cards each. A card is drawn from one of the halves; it turns out to be an ace. The ace is then placed in the 2nd half –deck. The half is then shuffled and a card is drawn from it. Compute the probability...

Homework Statement http://img512.imageshack.us/img512/9990/untitledsm9.png Homework Equations The permutation & combinations equation? I don't quite know how to type them out in here, but there's the calculator :smile: The Attempt at a Solution Since the maximum number of...

Prove that P(n,r) / n = P(n-1,r-1) I know that it is right but I have having a hard time coming up with a step by step solution. Is P(n-1,r-1) the same as (n-1)!

Hi all, I have a question, which I would have thought has been resolved already since a few centuries, but I can't find anything on it. I'm looking for the following quantity: the number of permutations with repetition of a set of cardinality k, drawn from a set with n elements, of which there...

Hey, Can anyone help me to understand einstein notation and permutations? I have a book, but it's not very clear. I really don't understand how you can write A_ij = e_ijk a_k out as a matrix? To start with I understand that a matrix can be represented as A_ij where i is the row and j is the...

I might be a bit thick in this but i just can't figure out how to answers this exam question: Calculate p to the power of 100, writing your answer in functional notation p is the permutation(n=10): (3,5,7,6,2,9,1,10,8,4). It should say 1-10 on the top but i don't know how to draw matrices...

Homework Statement 7 people around a table, how many ways of seating if A does not want to be next to B? Homework Equations (n-1)! The Attempt at a Solution Well I know the number of ways to get 7 people around a table is 6! but not sure how to solve it if A does not want to be...

Consider S_N = \left\{ {\left. {\sigma :\left\{ {1, \ldots ,N} \right\} \to \left\{ {1, \ldots ,N} \right\}} \right|\sigma {\text{ is a bijection}}} \right\} i.e., the set of all permutations on 'N' values. Define \Delta \left( {x_1 , \ldots ,x_N } \right) = \prod\limits_{i < j} {\left(...

Is the probability for a particular event, out of a set of events, equal to the total [normalized?] probability for all permutations of events from the set, including the particular event? Say you have a 2 x 2 square with cells numbered 1 to 4. I am asking if the probability for square 1, p(1)...

Well, in 5 years of PF'ing and watching over this forum, I am finally posting my first homework question. :-p I'm taking a graduate course in Algebra, and it's been 11 years since I took the undergraduate version. So, I'm going back and doing all the homework exercises in my undergrad book...

I'm currently going through a text about groups, and I'm having problems with composing permutations written in cycle notation, i.e. there are lots of examples and I'm expected to be able to calculate them pretty 'fast', so, is there a way to 'read out' the composition of two permutations direct...

Brain Teaser! This algorithm lists all permutations of {1,2 ...n} in increasing lexicographic order. Input: n Output: All permutations of {1,2...n} in increasing lexicographic order. 1. permutation(n){ 2. for i = 1 to n 3. Si = i 4. println(S1...Sn)// print the first...

Homework Statement There are 6 males and 4 females awaiting to see a teller at a bank. Only 4 people can be served at one time. 1) How many ways can four of the people be picked and served one at a time, if they must include two(2) men and two(2) women? 2) If indeed the four people...

Homework Statement choose x = (x1, x2, x3, x4) in R^4. It has 24 rearrangements like (x2, x1, x3, x4) and (x4, x3, x1, x2). Those 24 vectors including x itself span a subspace S. Find specific vectors x so that dimS is 0, 1, 3, 4 The Attempt at a Solution So, i thought of it this way: 24...

Hi, I have to find the total number of permutations of four letters that can be selected form the word "ARRANGEMENT". Clearly we have 7 different letters so the amount of 4 letter permutations with no repeats is: 7!/3!=840 now for each two letter can form a four letter permutaion...

I am a little confused at how to solve the following problem: In how many ways can five distinct Martians, ten distinct Vesuvians, and eight distinct Jovians wait in line if no two Martians stand together? What is throwing me off is the addition of another group - if it was just Martians...

Does anyone know of any algorithms that will list all permutations of a given multiset? :redface:

Homework Statement Find the sum of all the four digit numbers that can be formed with the digits 0,1,2,3 Homework Equations The Attempt at a Solution The total number of numbers possible is 3*4*4*4=192. Since the lowest number we can form is 1000, and the highest is 3333, the...

Okay so I did a homework problem that was the following: [b]How many permutations of 5 letters abcde that start with a, b, or c and end with c, d or e.[b/] To calculate the number of permutations of abcde that start with a, b or c and end with c, d or e, we can use the Addition Rule to split...

Hello everyone. The book has this problem: (h) You are arranging six of your friends Alice, Bob, Charles, Diana, Francine, and George, in a row so that you can take their picture. (i). Alice and Bob have had a fight and refuse to stand next to each other. How many ways are there to...

[B][/B I have a question here. Please can someone solve this. The question is: There are 7 students of whom 2 are Americans, 2 are Russians and 3 Indians. hey have to stand in a line so that the two Americans are always together and the three Indians are always together. In how many ways...

Here is the problem: A sequence of letters of the form abcba is an example of a palindrome of five letters. a. If a letter may appear more than twice, how many palindromes of five letters are there? of six letters? b. Repeat part a under the condition that no letter appears more than...