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

learn more… | top users | synonyms (1)

1
vote
0answers
34 views

Prove that if $\tau \in N_{S_A}(H)$ then $\tau$ stabilizes the sets $F(H)$ and $A \backslash F(H)$

Prove that if $\tau \in N_{S_A}(H)$ then $\tau$ stabilizes the sets $F(H)$ and $A \backslash F(H)$ $H$ is the set of fixed points on $A$ $A$ : set, $H \le S_A$, $F(H) = \{ a \in A : \sigma (a) = a, ...
1
vote
1answer
21 views

Prove the set of permuations which permute only finitely many elements is a normal subgroup

Let $A$ be a non-empty set and let $X$ be a subset of $S_A$ Now let $F(X) = \{a \in A : \sigma(a) = a, \forall \sigma \in X\}$, $M(X) = A\backslash F(X)$, and $D = \{ \sigma \in S_A : \mid ...
0
votes
2answers
23 views

Probability; bridge hand question

$13$ cards are chosen at random with no replacement from a deck of $52$ cards. find the probability there are $5$ spades chosen, $4$ hearts, $3$ diamonds and $1$ club. I got ...
0
votes
1answer
37 views

Properties of lists with arbitrary lengths and alphabet size

I am having trouble understanding a problem of applying the concepts of permutations and combinations in an example that I found while reading my textbook. Basically, it wants the number of elements ...
0
votes
3answers
35 views

How many different varieties of pizza can be made if you have the following choices:

How many different varieties of pizza can be made if you have the following choice: small medium, large; thin, hand tossed, pan; and $12$ toppings (cheese is an automatic), from which you may select ...
5
votes
1answer
52 views

How can I check whether the group $[16,13]$ in GAP with $3$ generators can be generated by $2$ elements?

The group $[16,13]$ in GAP has structure $(C4\times C2):C2$ and is generated by the permutations $(1234)(5678)$ , $(15)(26)(37)(48)$ and $(57)(68)$ . The group $[16,3]$ in contrast with the same ...
0
votes
0answers
14 views

Fraction of permutations satisfying a poset

Let $[n]:=\{1, ..., n\}$. Let $P$ be a poset on $[n]$. What is the fraction of permutations that satisfy $P$ when we view a permutation as inducing a linear ordering on the numbers? For instance, if ...
0
votes
0answers
22 views

G-set of 8 colors and 6 sides

"How many distinguishable wooden cubes can be painted if u use 8 colors (different colors on every side)" I have solved this question using Burnside's lemma ...
0
votes
1answer
48 views

Prove that (01) and (01…n-1) generate Sn? [duplicate]

Show that every element of Sn can be written as an arbitrary product of the elements (01) and (01...n-1). I understand that this can be solved using induction, and I've set up my base cases. ...
5
votes
2answers
49 views

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is …

What is the number of ordered triplets $(x, y, z)$ such that the LCM of $x, y$ and $z$ is $2^33^3$ where $x, y,z\in \Bbb N$? What I tried : At least one of $x, y$ and $z$ should have factor ...
6
votes
3answers
162 views

Is there any algorithm to find Isomorphism function between two graphs?

Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a ...
3
votes
1answer
48 views

How many DFA's exist with two states over the input alphabet $\{0,1\}$?

How many DFA's exist with two states over the input alphabet $\{0,1\}$? My attempt : Input set is given. So, we have 3 parts of DFA which we can change: Start state Transition Function Final ...
-3
votes
0answers
35 views

$S_X = \{f(x) = x : \text{ bijective} \}$. prove $S_x$ is isomorphic to $S_n$

Aright, to start $S_n$ is the Symmetric group and $S_X = \{x_1, x_2, \ldots x_n\}$. Going through the mapping $\phi(S_X) \to S_n$, I'm not sure how I'd show this mapping and the first thought that ...
5
votes
2answers
139 views

How many numbers of $10$ digits that have at least $5$ different digits are there?

In principle I resolved it as if the first number could be zero, to the end eliminate those that start with zero. The numbers that can use $4$ certain figures (for example, $1$, $2$, $3$ and $4$) are ...
4
votes
1answer
58 views

Alternating group on infinite sets

It is well known that the only normal subgroup of $S_n$ is $A_n$ when $n\geqslant 5$, and that $A_n$ is also simple. Furthermore, $A_{\infty}$, the even permutations on $\mathbb{N}$, is also simple. ...
3
votes
0answers
25 views

oligomorphic subgroups of $S_\infty$

Is it true that every oligomorphic subgroup of $S_\infty$ is not abelian? A subgroup of $S_\infty$ is said oligomorphic if its action on $\mathbb N^n$ has only finitely many orbits for each ...
0
votes
1answer
37 views

Polish subgroups of $S_\infty$

Let $S_\infty$ considered as Polish Group. Prove that every Polish subgroup of $S_\infty$ has the following form: $\overline{{\left \langle X \right \rangle}}$, where $X$ is a countable subset of ...
2
votes
0answers
18 views

Factorization of permutations into two factors with fixed number of cycles, plus a placement condition

I have asked this question in MathOverflow, but it received no answers, so I am posting it here. In my recent work I have been led to consider the following type of permutation factorizations. Let ...
0
votes
1answer
23 views

How find the length of an array

Story: In fact this question is related to THIS. How to create an array maintaining following conditions- ...
2
votes
2answers
23 views

Number of ways to distribute 4 different objects and 5 identical objects in 3 separate groups?

So, the question goes as: The number of ways in which 4 different toys and 5 identical marbles can be distributed between 3 different people, if each person gets at least one toy and one marble is? ...
1
vote
1answer
27 views

26 flavours of ice-cream, how many different banana splits can be made that have 3 different flavours?

A boutique ice cream bar stocks 26 flavours and offers a rainbow banana split that contains 3 scoops of ice cream, each of a different flavour. How many different rainbow splits can the store ...
-1
votes
1answer
44 views

Permutation of letters, the principle of inclusion and exclusion [closed]

How many permutations of the letters ABCDEFG do not include ABCDE, EDAB, EDG, GFAB. My solution: $$7! - \left(\frac{7!}{5!} + 2 \cdot \frac{7!}{4!} + \frac{7!}{3!}\right)$$
2
votes
2answers
42 views

In how many ways can 5 men and 5 women sit at a round table such that no 2 persons of the same gender sit next to each other?

In how many ways can 5 men and 5 women sit at a round table such that no 2 persons of the same gender sit next to each other? The book's answer is $2\times 5! \times 5!$ Why is it not $2\times 4! ...
0
votes
2answers
26 views

Counting ways to arrange the word REGULATIONS.

Find the number of ways the word REGULATIONS can be arranged such that there are exactly $4$ letters between $R$ and $E$ . I did $4!\ \ \ \ \text{for}\ \ ...
0
votes
2answers
26 views

Permutation and Combination Committee Questions [closed]

Q1. In how many ways can we select a committee of 6 persons from 6 boys and 3 girls, if at least two boys and two girls must be there in the committee? Given Answer: 65 Q2. In how many ways 7 persons ...
0
votes
2answers
32 views

How to calculate the minimum and maximum number of matches between two sequences?

I have two sequences of the same length $n=3$: $\{A,B,C\}$ and $\{A,A,B\}$. When I compare them, there is 1 match since both have an "$A$" in the first position. Generating all 6 permutated versions ...
1
vote
0answers
26 views

$S_n$ is isomorphic the permutations of the identity matrix?

Prove that the set of permutations $S_n$ is isomorphic to the group of invertible square matrices of order $n$ where each row has $n-1$ zeros and $1$ in one place. This is very intuitive to me, ...
0
votes
1answer
37 views

Permutation representations of symmetric group of small order

Thanks for any comments or help. What is the list of faithful permutation representations of $S_k$ of degree at most $n=2k$ for $k=3,4,5,6$? Is it possible to find its centralizer in each case?
-1
votes
0answers
51 views

No. of ways to Generate the String [duplicate]

I want to generate a binary string, such that number of occurrence of $00,01,10$ and $11$ are to be fixed. How can we find out the numbers of ways for given value. For example: number of occurrence ...
-3
votes
0answers
33 views

Find the different Binary String [duplicate]

I want to generate a binary String, such that number of occurrence of 01,10,00 and 11 are to be fixed. For Ex: Number of occurrence of 01,10,11 and 10 are 1 1 2 and 1 respectively. ...
1
vote
0answers
20 views

Unique unordered combinations of varying length

Given random set of integers. I.e. $\{1,2,2,3,3,3,5\}$ Find the number of unique, unordered of varying length sets that can be created. My Workings This is not a homework problem, but rather, ...
-1
votes
1answer
63 views

find number of strings

Find the number of strings consisting of only a and b which have P occurrence of aa Q ...
1
vote
1answer
83 views

Number of binary numbers given constraints on consecutive elements

I've been trying to solve this question for quite a while, given to us by our discrete maths professor. I've been having a hard time in general with it, so I thought I tried looking it up online but ...
3
votes
1answer
45 views

Is it enough to determine if two finite groups are isomorphic if we can map the generators?

Heading: A General Inquiry about Finite Isomorphic Groups and Their Generators If I am given two finite groups whose generators I know, is it enough to show that by mapping the generators ...
2
votes
1answer
28 views

If $\alpha,\beta \in S_{n}$, and $\alpha\beta = \beta\alpha$, then $\beta$ permutes those elements left fixed by $\alpha$.

Here is my solution. Let ${a_1,...,a_k}$ represent all the integers that are permuted by $\alpha$, and let ${a_{k+1},...,a_{k+j}}$, where $k+j \leq n$, be all the elements that are left fixed by ...
4
votes
1answer
100 views

How to partition $nk$ objects $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size $k$, so that no combination of $k$ is repeated.

What is an algorithm to partition $nk$ objects a total of $\frac{1}{n}\binom{nk}{k}$ times, each time making subsets of size exactly $k$, so that no subset of size $k$ is ever repeated? For example, ...
0
votes
0answers
13 views

How does cycle index change along an equivariant map?

Question. Suppose $G$ acts on $X$ (via $\Psi$) and on $Y$ (via $\Phi$), and let $f : X\to Y$ be an equivariant map ($f\circ\Psi = \Phi$). Is there a formula relating the cycle indices $Z_\Psi$ and ...
0
votes
2answers
31 views

Subgroup of $S_{2n}$ that sends evens to evens and odds to odds.

I got this question in the exam: $T_{2n}$ is the subgroup of $S_{2n}$ that sends even numbers to even numbers and odd numbers to odd numbers, for example: $(2 4 6 8)(1 3 5)$ is a permutation in ...
1
vote
2answers
62 views

Ways to create a quadrilateral by joining vertices of regular polygon with no common side to polygon

How many ways are there to create a quadrilateral by joining vertices of a $n$- sided regular polygon with no common side to that polygon? It's quite easy to solve for triangles for the same ...
0
votes
2answers
58 views

Combination - Distribution of gifts.

Seven different type of gifts are to be distributed among $10$ children. Every kind of gift must be at least given to one child. Then, how many combinations do we have? Note:You have $A, A, A....$ ...
1
vote
1answer
24 views

What is the probability of getting two spades in five draws?

For easier viewing, here is the question: What is the probability of getting two spades from five draws I understand how to solve this question using permutations. I have explained my work ...
0
votes
1answer
17 views

Determine the parity and the inverse for each of the following permutation of {1, 2, . . . , 9}:

So i was given this question. Determine the parity and the inverse for each of the following permutation of {1, 2, . . . , 9}: (a) (987654321) (b) (135792468) I don't understand how to go about ...
0
votes
0answers
20 views

Expected Number of Cycles in Random Permutations with a Random Number of Symbols

It is known that for permutations sampled uniformly from $S_k$ that $\mathbb{E}[C] = H_k = O(\log k)$ (more precisely, $\Theta(\log k)$), where $C$ is the number of cycles in a random permutation. If ...
0
votes
1answer
31 views

Proving if a permutation cipher is perfectly secret?

From what I've read, perfect secrecy in its most basic form, that the encrypted text reveals no information about the plaintext, be it structure or content. A permutation cipher is easy for me to ...
2
votes
1answer
33 views

Permutations + Combinations Proof

$W_n^{(k)}$ is the number of permutations in a set of all $n!$ permutations in a $n$-element set which has $k$ fixed points. $W_n^{(0)}$ is the number of n-derangements where $\frac{W_n}{n!} ...
0
votes
1answer
21 views

Number of Permutation with Pro = k equals the Eulerian Number A(n,k+1)

The problem phrases as follows: Let $\sigma = (\sigma_1, . . . , \sigma_n)$ be a permutation. We say that element $i$ is progressive if $\sigma_i > i$. We write $pro(\sigma)$ for the number of ...
0
votes
0answers
13 views

Interpreting the table of classification of the partitions of $n$

I am going through A NON-RECURSIVE EXPRESSION FOR THE NUMBER OF IRREDUCIBLE REPRESENTATIONS OF THE SYMMETRIC GROUP $S_n$ by AMUNATEGUI. In table I, the classification of the partitions of n according ...
2
votes
2answers
30 views

How many combinations of three numbers using 1, 2, 3, and 4 exist?

If you count (4 4 3) as one combination, you cannot count (4 3 4) as another. My approach is $\dfrac{4^3}{3!}$, but obviously this does not work. I don't know why it doesn't work, and I don't know ...
0
votes
0answers
15 views

Finite Permutation Composition

This is a problem I'm trying to solve. Given a permutation $ \sigma $ on a finite set $ \mathcal{A} $ of order $ n $, show that there exists a positive integer $ 0< k \leq n $ such that $$\bigl( ...
2
votes
2answers
35 views

permutations of elements of vector

I'm trying to find a simple representation of a set I can describe with words, but not mathematically... probably a simple question.. Consider some two-element vector $q=(q_1,q_2)$. How can I ...