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

learn more… | top users | synonyms (1)

0
votes
1answer
28 views

Number of possible passwords - Google APAC Test

I am trying to solve this problem - Google apac test - Password Attacker . Problem summary: Using $M$ distinct characters, what is the number of ways of making a password of length $N$, such that ...
0
votes
1answer
18 views

Example of an elementary permutation

Can someone please give an example of an elementary permutation? The book says that every permutation can be written as a composite of elementary permutations. Can someone please give an example? ...
0
votes
0answers
24 views

Count number of trees

Given an array with n elements which is the pre-order traversal of a tree. How many max-heap will have the same pre-order traversal?
3
votes
1answer
58 views

Arrangement of integers in a row such that the sum of every two adjacent numbers is a perfect square.

Inspired by this interesting question and in order to solve an old problem, I have the following question: Can we construct a strictly increasing sequence $(N_i)_{i\in \mathbb{N}}$, such that for ...
0
votes
1answer
37 views

Murder mystery permutation problem

In exploring a hypothetical situation, I ran across this problem and I'm curious to know the answer, but math's not really my forte. You have a pool of 15 people. Between these 15 people there will ...
0
votes
0answers
18 views

Find lexographically minimum permutation with maximum sum

A wavy sequence "a" is a sequence of N integers such that a[0] < a[1] > a[2] < a[3] > a[4] ... and so on. And let say value of this sequence is sum of |a[i] - a[i - 1]| for all 0 < i < N. ...
1
vote
2answers
30 views

How to find the number of strings of length N that can be formed by using the characters A, B, and C only that do not have “ABC” as a substring?

A, B, and C can be used any number of times in the string. This problem appeared in a programming contest which is already over. http://www.codechef.com/problems/CDSW152
1
vote
1answer
20 views

What kind of mathematical approach can you use to find all non-repeated combinations?

At first glance I thought this was a non-repeated combination or permutation, but those use a set length. So, I guessed this might be a partition of a positive integer, but it's not looking like that. ...
4
votes
1answer
31 views

An Example for a Graph with the Quaternion Group as Automorphism Group

I am reading "Graphs of Degree Three with given Abstract Group" (by Robert Frucht) where the author describes (somewhat tedious) algorithms to construct suitable graphs starting from a given group. I ...
2
votes
0answers
14 views

How to calculate total results of combinations of letters

I am programmer and have developed an algorithm to run a processor intensive function on all the permutations of 2 letters (X and O) when we define how many X's and O's there will be. For example, I ...
1
vote
0answers
26 views

Structure of the semidirect product decomposition

I'm looking at a complicated group that involves many semidirect products, and I realized that I have a fundamental confusion about how to use the structure of a semidirect product decomposition of a ...
1
vote
1answer
29 views

Possible permutations of a grid

I hope this is the correct place to post this, as I don’t study maths. But I do need help calculating the possible permutations of a grid based game I’m currently programming. This isn’t to help out ...
0
votes
1answer
32 views

Find Number of combinations possible

There are two letters "X" and "Y".A String of length N needs to be formed using those two letters How many number of combinations that can be possible where N should start with "Y" and no two or more ...
0
votes
0answers
27 views

Number of ways to color N objects in X colors where there is at least one object of each color.

What is the number of way to color $N$ objects in $X$ colors, where there is at least 1 object of each color?
4
votes
1answer
70 views

Combination or Permutation

I am searching for the number of possible isomers of a compound. However, my understanding of mathematics is quite limited in the field of combination and permutation. I have searched through many ...
1
vote
0answers
13 views

Generating uniform permutations by a particular method

Let $A$ be a uniformly random permutation of the numbers $\{1,2,\cdots,n\}$. I want to generate a uniformly random permutation from $A$ on the numbers $\{1,2,\cdots,n,n+1,\cdots,n+m\}$. In other ...
1
vote
1answer
38 views

How many cycles of length $k$ in $S_n$?

In the symmetrical group $S_n$, how many cycles of length $k$ can we form? After some research I am tempted to say $\frac{n!}k$ but I am not sure.
1
vote
2answers
22 views

Dependent permutations, a question.

I cant seem to find anything on the internet on this subject , and the professor did not explain it too well, in short the following is unclear to me how is $$(1 3 4)(236)=(24136)$$and ...
2
votes
1answer
21 views

Symmetries of the regular hexagon

Q- Let G be the group of the symmetries of the regular hexagon. List the elements of G (there are 12 of them), then write the table of G. So for the listing the elements of G, they want it like this: ...
1
vote
0answers
26 views

Integrating a permutation of a combinatorics-type function

I would like to integrate a permutation of a function. Namely I have the following: $\sum_{\sigma, \sigma'\in S_{n+1}}\int_{-A}^A dz_1dz_2 ... dz_{n+1} ...
0
votes
0answers
28 views

Ball-of-wacks combinations

The six-color version of the ball-of-wacks consists of thirty rhomboidal pieces, which can be combined to form a rhombic triacontahedron. There are six colors, each with five pieces. One challenge ...
2
votes
2answers
30 views

Illegal permutations give a nonzero answer

I am told that a random variable can take a value of $+1$ or $-1$. I am given the total number of times the random variable is counted, $N$, and the sum of the random variables, $n$, and asked to find ...
3
votes
1answer
39 views

List the elements of the cyclic subgroup of $S_6$

List the elements of the cyclic subgroup of $S_6$ generated by: \begin{smallmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 2 & 3 & 4 & 1 & 6 & 5 \end{smallmatrix} ...
1
vote
1answer
33 views

How many three digit number can be formed?

Question: (a) How many three-digit numbers can be formed from the digits 0, 1, 2, 3, 4, 5, and 6 if each digit can be used only once? (b) How many of these are odd numbers? (c) How many are greater ...
1
vote
0answers
21 views

Birkhof representation of a stochastic matrix

From Birkhof Theorem, it is known that every doubly stochastic matrix can be written as a convex combination of permutation matrices although this representation might not be unique. I have the ...
0
votes
1answer
27 views

no of possible ways [duplicate]

we have to build a houses on $m$ plots, such that no two consecutive plots exist on which it is allowed to build house calculate the number of possible ways of assigning free plots to buildings ...
1
vote
1answer
30 views

The order of a $k$-cycle in $S_n$ is $k$.

Here's what I have right now: The order of a $k$-cycle in $S_n$ is $k$. Proof. Let $\sigma$ represent the $k$-cycle $$\sigma=(x_1 \ x_2 \ \cdots \ x_k)$$with distinct elements $x_i$. Note that the ...
2
votes
1answer
20 views

How to solve this statistics problem? [on hold]

Can you find the sum of all numbers that can be formed with the digits $2, 3, 4$ and $5$ taken all at a time? (So its like you sum up the number from 1st digit to 4th digit) I'm learning now about ...
0
votes
2answers
22 views

Permutation's decomposition into transpositions

Transposition is a cycle with 2 elements. Any permutation can be decomposed into a product of transpositions. For example, for permutation $\begin{pmatrix} 1 & 2 & 3 & 4\\ 2 & 3 ...
2
votes
1answer
42 views

Maximize $a_1^{a_2^{\ldots^{a_n}}}$, where $(a_1,a_2,\ldots,a_n)$ is a permutation of $(b_1,b_2,\ldots,b_n)$

You are given a tuple of integers $B=(b_1,b_2,\ldots,b_n)$. Find $(a_1,a_2,\ldots,a_n)$ - a permutation of $(b_1,b_2,\ldots,b_n)$ - that maximizes $a_1^{a_2^{\ldots^{a_n}}}$. For example - If ...
0
votes
0answers
41 views

Permutations Without Repetitions

Given the set [A,B,C,D] how many distinct ways can I order all four of the members of the set? I see distinct, as a unique set, therefore [A,B,C,D] and [D,C,B,A] ...
0
votes
1answer
30 views

How to calculate combinations of multiple variables which can assume multiple values

I have 3 variables (A,B,C); each variable can assume 3 different values (1,2,3) . I want to calculate ho many combinations there are which follow this rule: let's fix A1, then cycle on all the others ...
3
votes
3answers
233 views

How many ways to reach a given tennis-score?

Let's say a tennis player wins a set with a game score of 6-3. In how many different ways can we reach this score? Assuming H means the home-player won the game and A means the away-player won the ...
4
votes
2answers
70 views

Number of Words with two letters $a$ and $b$.

Given $N$ and $M$, find the number of $N$ letter words consisting of only $a$ or $b$, where $b$ must not be consecutive for more than or equal to $M$ times. Example: if $N=3$ and $M=2$, then all the ...
0
votes
1answer
21 views

Combinations - Permutations

Find the number of ways in which 5 books can be distributed between three people A,B and C, if the books are a)indistinguishable, b)all different. a) $\displaystyle \frac{5!}{3!(5-3)!} = 10$ b)$ ...
3
votes
1answer
200 views

Counting elements in cartesian power with plurality + pattern constraints

Problem: I have an alphabet with n=8 letters (say $X=\{A, B, C, D, E, F, G, H\}$). I'm looking for words with m=24 letters, with three constraints: letter $A$ is the relative majority (like in ...
-1
votes
1answer
26 views

symmetric group acting on torus

Let $S_k$ be symmetric group of order $k$. Let $T^k=S^1\times\cdots \times S^1$. Then $T^k$ is a Lie group. For each $\sigma\in S_k$, let $\sigma$ act on $T^k$ from right in the way $$ ...
4
votes
2answers
55 views

If there is a bijection $f: X\rightarrow Y$, prove that there exists an isomorphism $\phi :S_X\rightarrow S_Y$

If there is a bijection $f: X\rightarrow Y$, prove that there exists an isomorphism $\phi :S_X\rightarrow S_Y$. Here $S_X$ denotes the group of all permutations of $X$, i.e., the bijections $X\to ...
0
votes
1answer
28 views

Permutations and Counting problem?

Postal codes in Canada have six characters with alternating letters and digits in the form L#L#L#. How many postal codes do not have one letter repeated three times? What I did is ...
0
votes
0answers
20 views

Sampling with/without order

Our professor have presented this simple example in the lecture. You have $P_n$ processors and $M_k$ memory where $k>n$. If two or more requests goes to same memory then the request will be ...
0
votes
1answer
35 views

Sides of a triangle [closed]

The sides of a triangle are $a,b,c$ and $a\leq b\leq c$ If $c$ is given, show that number of different triangles is $(c+1)^2/4$ or $c(c+2)/4$ according to $c$ is odd or even. Also given a,b,c are ...
2
votes
0answers
35 views

The $8$-Puzzle and $2$-Cycles

I have been studying the $8$-puzzle and have thus far managed to wrap my head around the following information: The following illustrates the solved position of the $8$-puzzle, where $9$ is the empty ...
0
votes
1answer
49 views

Prove that this number is an integer

Prove that the number $${4155 \cdot4156 \cdot\ldots \cdot4251 \over 2 \cdot3 \cdot\ldots \cdot 97}$$ is an integer. How might I prove this?
0
votes
1answer
42 views

Adding numbers in a consecutive series

I have the series: 1, 13, 133, 1333 ... Currently I have distributed it down to: 1 + (10 * 2) + (100 * 2) ... Can anyone point me in the right direction? Sorry, I forgot to mention, I'm looking for ...
0
votes
1answer
33 views

How many permutations of letters ABCDEFG contain the strings ABC and CDE

For this problem, I understand how to find something like how many strings contain the string BA and GF. I just look at the set of letters like this: {BA, GF, C, D, E} and since I have 5 distinct ...
0
votes
2answers
14 views

Counting permutations of a set that doesn't fix elements

I want to know how to count the number of permutations of a finite set that doesn't fix elements, i.e., the cardinality of the set $H=\{f\in S_n: f(i)\not = i\ \mbox{for}\ 1\leq i \leq n\}$, where ...
0
votes
1answer
25 views

Odd and Even Permutations and their parities

So the question is: Let Alpha and Beta belong to Sn. Prove that BetaAlphaBeta and Alpha are both even or both odd. I'm not sure where to start. My basic logic class tells me to go with the idea: ...
2
votes
1answer
44 views

Group theory, order with permutation of Z

Let $S_{Z}$ be the set of permutations of ${Z}$ (note that this is an infinite group!). Find two elements of $S_Z$ which both have finite order, but whose product has infinite order. I just am really ...
0
votes
1answer
22 views

If σ is a cycle of length n, then σ^r is also a cycle if and only if n and r are relatively prime

If σ=(1.2.3), σσσ= identity permutation, which is cyclic in this case n=3 and r=3 but their gcd is not 1. I don't understand why -> this direction of theorem is true
0
votes
1answer
32 views

Discrete Math Boys and Girls

Problem 4: Boys and Girls Consider a set of m boys and n girls. A group is called homogeneous if it consists of all boys or all girls. In the following questions, practice the multiplication and the ...