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
39 views

Decompose and compute the sign of $\sigma(k)=n+1-k$

Let $n\geq 2$ and $\sigma$ is permutationof $\{1,2,\ldots,n \}$ defined by : $$\sigma(k)=n+1-k$$ Decompose permutation $\sigma$ into product of disjoint transpositions and compute the sign of it ?...
0
votes
1answer
60 views

How to prove that $\langle\{ (1,2),(1,2,\ldots,n) \}\rangle=\mathfrak{S}_n$

Let $n\geq 2, \tau=(1,2),\ c=(1,2,\ldots,n)$ two permutation of $\mathfrak{S}_n$ Prove that $$\biggl\langle\{ (1,2),(1,2,\ldots,n) \}\biggr\rangle=\mathfrak{S}_n$$ Indeed, normally i will ...
15
votes
3answers
875 views

Does the concept of permutation make sense for a set indexed by the real numbers?

I know that the concept of permutation makes sense for sequences, which are sets indexed by the natural numbers (if the sequence is infinite) or indexed by the first $n$ natural numbers (if the ...
0
votes
1answer
16 views

Formula for combinations number with aggregation

I've this scenario, 4 groups (as follow) with following values: Dimension A: A B Dimension B: K J L Dimension C: X Y Dimension D: F G I want to know numbers all possible combinations, ...
0
votes
1answer
33 views

Permutation formula for lock combination

I know the basic permutation formula for k objects out of an n set. But what is the formula for determining the number of permutations where k is a range (1..m) ? What are the formula for the ...
2
votes
1answer
65 views

Derangement combination calculation

For the traditional classic problem of derangement (https://en.wikipedia.org/wiki/Derangement), there is a formula $n! = (n-1)(!(n-1)+!(n-2))$, which calculates current results based on previous ...
4
votes
1answer
39 views

Probability in $S_{15}$

We consider the set of permutations of the first fifteen natural numbers. What is the probability that $1$ and $2$ aren't contiguous? My attempt: Denote by $C_{12}=$ "The numbers $1,2$ are ...
0
votes
2answers
40 views

Permutations of n numbers with no odd numbers next to each other

What is the number of $\{1, 2, \dots, n\}$ permutations, in which neither two neighbouring numbers are odd? Could somebody show me the reasoning that leads to the answer?
0
votes
1answer
33 views

Order of product of non-disjoint cycles

Let $a$ and $b$ be two non-disjoint cycles of order $m$ and $n$. Is there any general formula for the order of $a b$? I understand that we can convert any non-disjoint cycles into disjoint cycles and ...
2
votes
3answers
53 views

How many bit strings of length $5$ do not have consecutive $1$'s?

How many bit strings of length 5 do not have consecutive 1's? I'm trying to think of a way to calculate how many ways we can arrange a string of length 5 starting with the first position (or index). ...
1
vote
4answers
58 views

How to prove that $\langle\{ (1,2),(1,2,3) \}\rangle=\mathfrak{S}_3$

Prove that $\{ (1,2),(1,2,3) \}$ Generating set of a symmetric group $(\mathfrak{S}_3,\circ )$ SOlution provided by book we 've $(1,2,3)(1,2)(1,2,3)^2=(2,3)$ and $(1,2,3)^2(1,2)(1,2,3)=(1,3)$ ...
0
votes
3answers
34 views

A boat is to be manned by 8 men,of whom 2 can only row on bow side & 1 can only row on stroke side;in how many ways can the crew be arranged?

I tried it by selecting 2 men out of 8 for bow side,and then arrange them in 2! ways.This can be done in$ \binom{8}{2}$*2! ways,and the stroke side can be crewed in 6 ways.So the required no. of ways ...
-1
votes
1answer
44 views

$\forall x \in Fix( \sigma ),\ \mathcal{O}(x)=\{ x\} $ and $\forall x \in supp( \sigma ), \{ x\}\subset \mathcal{O}(x)$

Let $\sigma \in \mathfrak{S}_{n}$ Show that : $$\forall x \in \operatorname{Fix}( \sigma ),\ \mathcal{O}(x)=\{ x\} \quad \rm{ and }\quad \forall x \in \operatorname{supp}( \sigma ),\ \{ x\}\...
0
votes
1answer
31 views

Find the number of ways of choosing three initials from the alphabet if none of the letters can be repeated

This question is from Marcel Finan A Probability Course for the Actuaries A Preparation for Exam P/1 4.8 Find the number of ways of choosing three initials from the alphabet if none of the letters ...
0
votes
2answers
43 views

Permutation of keys inserted into a tree?

Give the fraction of permutations of the keys $A $ through $G$ that will, when inserted into an initially empty tree, produce the same Binary search tree as does $A$ $E$ $F$ $G$ $B$ $D$ $C$ ANSWER: (...
0
votes
2answers
36 views

6 women, 7 men form a pair of 1 woman 1 man. How many ways can we select 3 pairs.

So the way to do this I think is to 6C3*7C3*9 (where 9 is the number of ways we can arrange the men and women within the 3 pairs). But I can't seem to figure out how I would do this in a different ...
2
votes
4answers
93 views

Number of positive unordered integral solutions

What are the number of positive unordered integral solutions for $a+b+c=36$ Solution given is $108.$.But I am getting $91$ as $$\frac{\binom{35}2-3\times16-1}{3!}.$$ $3\times16($ for $a=b$ cases and ...
2
votes
1answer
43 views

Order of subgroup generated by two cyclic subgroups in $S_6$.

Let $S_6$ be the symmetric group, and $\alpha=(13456)$ and $\beta=(132)$ be its two permutations. How can we find the order of the subgroup generated by $\alpha$ and $\beta$. SOl: $\alpha^5$=...
0
votes
3answers
37 views

Let $\sigma :\{1,2,3,4,5\} \rightarrow \{1,2,3,4,5\}$ be permutations such that $ \sigma^{-1}(j) \leq \sigma(j)~\forall j, 1 \leq j \leq 5$.

Which of the following are true? $\sigma \circ \sigma(j)=j~\forall j, 1 \leq j \leq 5$. $\sigma^{-1}(j)=\sigma(j)~\forall j, 1 \leq j \leq 5$. The set $ \{k: \sigma(k) \neq k \}$ has even number of ...
0
votes
0answers
22 views

Find possible number of lists that can be formed. [duplicate]

I am new to such problems of number theory. Any help will be appreciated. I have a list containing n numbers. I can apply the following operation exactly K times. Pick some element in the array and ...
1
vote
2answers
28 views

Disjoint permutations?

I have some exercise examples that were give at the exam last year, but I'm having trouble with what they're asking of me. It's also possible that I misunderstood or have an incorrect exercise. This ...
1
vote
2answers
58 views

Find the sum of all 4-digit numbers formed by using digits $0, 2, 3, 5$ - possible formula for competitive exam

Find the sum of all 4-digit numbers formed by using digits 0, 2, 3, 5 without repetition There is a similar question in this site and Eric Tressler has provided a clear method to solve such ...
1
vote
1answer
51 views

What is the concept behind this derangement formula?

In permutations and combinations, what is the concept behind this derangement formula? $$D_n = n!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+...+(-1)^n\dfrac{1}{n!}\right)$$ Also, how is it ...
0
votes
2answers
25 views

Number of ways to have $N$ as sum of $K$ numbers such that one of them is odd

I want to know if there is a formula to find the number of ways to express $N$ as sum of $K$ non-negative numbers such that at least one of those $K$ numbers is odd. Example: if $N=2$ and $K=3$ the ...
3
votes
1answer
107 views

Primitive Wreath Product action

I am a little confused about the primitive action of the wreath product as when to use the inverse and whether to use left or right action. Let $H, K$ be groups and $K$ acts on $\Delta$, the wreath ...
2
votes
2answers
48 views

If $\sigma \in S_n$ has order some prime $p$, then is $|\{1 \le i \le n : \sigma(i)=i\}|\equiv n \pmod p$? [closed]

Let $\sigma \in S_n$ be such that $o(\sigma)=p$ (some prime). Then is it true that $$|\{1 \le i \le n : \sigma(i)=i\}|\equiv n \pmod p\ ?$$
0
votes
0answers
16 views

Permutation of binary bits results in the xor operation

Consider two n-bit binary string $d \in \{0,1\}^n$ and $e \in \{0,1\}^n$ How need to permute the bits of d using e such that the permutation of d results in $d \oplus e$.
5
votes
2answers
88 views

Determine $\frac{f''(\frac{1}{2})}{f'(\frac{1}{2})}$ if $f(x) = \sum_{k=0}^{1000} \ {2015 \choose k}\ x^k(1-x)^{2015-k}$

Problem : Determine $\frac{f''(\frac{1}{2})}{f'(\frac{1}{2})}$ if $f(x) = \sum_{k=0}^{1000} \ {2015 \choose k}\ x^k(1-x)^{2015-k}$ Trying to simply brute force the problem, yields the following ...
1
vote
0answers
99 views

Finding total number of multi-sets

I am provided with a multi-set, let's say S with elements as [num1, num2, num3] and these elements are integers (both negative as well as non negative). As this is a multi-set, elements in the multi-...
0
votes
1answer
19 views

Combination with Repetitions Including Duplication of N Value

Is a Combination with Repetition the correct term for the following problem N - Letters a, b, c R - 2 Example Result should equal aa ab ac bb ba bc cc ca cb Total ...
0
votes
2answers
40 views

Amount of possible passwords 8 characters long, with at least 1 number, no more than 3 repeating letters

What is the number of possible passwords that are 8 characters long, with at least 1 number, and no more than 3 repeating letters? How would you go about calculating this? Examples of invalid ...
0
votes
2answers
39 views

All even permutations correspond to cycle that has an odd length?

I am reading something about abstract algebra and got bit puzzled here. Suppose we know every permutation is a product of transpositions (cycles with length of two). If the definition of an even ...
2
votes
0answers
33 views

Number of linear orderings of a set to have balanced frequencies of triple orders

Let $S$ be a set of $n$ elements and let $Q = (s_1, s_2, \ldots, s_n)$ be an ordering of $S$. We write $s_i <_Q s_j$ when $s_i$ appears before $s_j$ in $Q$. I want to construct a set (or possibly ...
0
votes
1answer
32 views

Permutations of n distinct objects in r groups, given that some objects may not be able to go into some groups?

For example, let's say there are groups A, B and C and objects 1, 2 and 3. Objects 1 and 2 can go in groups A, B and C, but object 3 is only allowed in groups A and B. How many different ways can the ...
0
votes
3answers
48 views

Do I use Combination or Permutation? [closed]

I've been having trouble figuring out the right equation to use on this problem. Help? "Given two integers, M and N, compute the number of ways it is possible to choose M marbles from a set of N ...
4
votes
1answer
82 views

What is the dimension of this space?

The function $π(v)$ interchanges the coordinates of the vector $v$ randomly. For example: $v = (1,3,7,9), π(v) = (7,3,1,9)$. Fix some vector $v ∈ \mathbb{R}^n$ and construct a linear hull of all ...
1
vote
2answers
348 views

Maximum number of longest increasing subsequence for an array A

Lets say , I have an array A = [A1 A2 A3 .... An] with size n. All elements are distinct in the array. I can change positions of any two elements by swapping them . Now , The Longest increasing sub-...
2
votes
2answers
95 views

Counting Circular Sequence (Burnside Lemma?)

How many distinct circular binary sequences of length $n$ are there? How many distinct circular binary sequences of length $n$ containing a given pattern, e.g., $110$ are there? The same questions as ...
1
vote
1answer
99 views

How many ways we can find out the strip of N spins contains m “Parallel Pair” out of which m1 of them are “Up Parallel Pair”?

Let us consider a one-dimensional strip containing 8 spins. Spins can be up or down. And spins can be arranged randomly. So the total number of different microstates possible is $2^8$ (Taking Periodic ...
2
votes
0answers
21 views

Do permutations apply to places or indices?

Do permutations such as those in the group $S_3$ move elements based on place (of elements in the input) or index? E.g. does $$\bigg(\frac{123}{231}\bigg)$$ move 1 to 2's place (e.g. if the input ...
0
votes
1answer
44 views

Permutations or Combinations

A letter lock has $3$ rings containing $6$ different letters. No $2$ rings have the same letters. How many different combinations of passwords is possible? $15600$ $17576$ $\binom{26}{6}\binom{20}{6}...
1
vote
1answer
11 views

$p=\sigma \tau^{-1}$ fixes each element of the set $\{a_i : i ≤ j\}$?

I'm trying to understand the proof for Let $\sigma$ be any element of $S_n$. Then $\sigma$ may be expressed as a product of disjoint cycles. In this proof (p. 3) there's a part where $p=\sigma \...
47
votes
4answers
2k views

How many 7-note musical scales are possible within the 12-note system?

This combinatorial question has a musical motivation, which I provide below using as little musical jargon as I can. But first, I'll present a purely mathematical formulation for those not interested ...
0
votes
1answer
33 views

Recognizing Permutation of Group with different Label

Problem description: Assume, a group, $G \leq S_{26}$ , $S_{26}$ is a symmetric group. Each permutation of $G$ is labeled using $1,2,....26$ as usual. Suppose, $f$ is a function that changes label ...
1
vote
2answers
33 views

how many ways is it possible to seat eight people at a round table …

I know this is a permutation problem, selecting two from eight. My problem is how to use this information: "must sit one seat away from each other." In how many ways is it possible to seat eight ...
-1
votes
1answer
40 views

difference of at least 4 between two numbers

In how many ways we can select two numbers from first $10$ natural numbers so that difference between them is at least four? If we select the numbers from the interval $[1,10]$, will the answer ...
1
vote
1answer
56 views

distribution of 101 coins to three friends

In how many ways we can distribute 101 coins to three friends such that sum of the coins of two friends is more than or equal to the number of coins of third friend. my views:should I distribute 50 ...
3
votes
1answer
79 views

What is the probability of no pair's names being adjacent?

Suppose there are $N$ (even number, positive) people. And each one person has to find one and only one partner to form a pair. There is also a roster within which everyone's name appearing in ...
0
votes
0answers
40 views

How many ways can two cards be selected from five different cards with replacement when order matters?

So I have $5$ different cards and I am choosing $2$. I want to know the total possible permutations of choosing two cards (I know the answer is $25$ by using permutations). I need other ways to ...
1
vote
0answers
27 views

Find all the invariant invariant subspaces for the regular representation of $S_3$.

Using a little program I can build the regular representation of $S_3$ (the permutation group of three elements). The textbook that I am reading only tells that the regular representation contains all ...