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
0 votes
1 answer
24 views

What is the probability of at least one coincidence after a permutation?

Imagine we have N distinct and ordered elements. (1, 2, 3, 4, 5, 6, 7) # Example with 7 elements. And we permute them randomly, for example.... ...
skan's user avatar
  • 391
0 votes
0 answers
24 views

Combinatorics -- committee of 4 problem

The problem at hand is that we want to select a committee of 4 people from a pool of 6 men and 7 women (this problem is from a textbook, I didn't come up with it). We want to know how many ways we can ...
JBatswani's user avatar
0 votes
0 answers
25 views

Confusion with problem regarding 3-letter strings created from a 5-letter alphabet

I'm taking a discrete math course in university right now and we're studying permutations and combinations as one of the chapters. The question I'm confused about states that given a 5-letter alphabet,...
JBatswani's user avatar
3 votes
5 answers
91 views

Number of binary strings of length $56$ vs number of permutations of English alphabet

This is exercise $1.2$ in Nicholas Loehr's book "Combinatorics". Which is larger: the number of binary strings of length $56$, or the number of permutations of the English alphabet ($26$ ...
pyridoxal_trigeminus's user avatar
-2 votes
0 answers
17 views

Question involving Permutation and Combination [closed]

You have to choose 5 out of 7 items to arrange, 3 of which are the same. Solve this question.
ZhangJin's user avatar
1 vote
0 answers
44 views

Why is the traditional proof of the formula for permutations by the multiplication rule not formal?

The traditional, most common proof of $_nP_n = n!$ is by the multiplication rule: There are $n$ choices for the first position, $n-1$ for the second, and so on until there is only one choice for the ...
Cynicrom's user avatar
  • 296
0 votes
0 answers
40 views

A question regarding a permutation in $S_n$

Let $\sigma\in S_n$. For each $i\in\{1,2,\ldots,n\}$ let $k_i$ be the smallest positive integer such that $\sigma^{k_i}(i)=i$. Suppose now that $k_1,\ldots,k_n$ are all even. Is it true that $n$ must ...
boaz's user avatar
  • 4,757
0 votes
0 answers
43 views

Combination problem : 6 Schools , three sports.

Six schools participate in a youth sports conference and each school is represented by three players a cricketer, a soccer player, and a hockey player. It is required to select a committee of six ...
Angelo Mark's user avatar
  • 5,954
0 votes
1 answer
64 views

Probability that no partial sum of a permutation of $\{1,\dots,n\}$ are divisible by $3$ [duplicate]

Assume that $a_1,a_2,\cdots,a_n$ is a completely random permutations of numbers $1$ to $n$. What is the probability that none of the $n$ partial sums $A_1 = a_1$, $A_2 = a_1 + a_2, \dots$, and $A_n = ...
Eager's user avatar
  • 11
1 vote
2 answers
68 views

Number of integral solutions for $x_1 + x_2 - x_3 = n$ where $n \geq x_1 , x_2 , x_3 \geq 0$

I have been asked Integral solutions for $x_1 + x_2 - x_3 = n$ where $n \geq x_1 , x_2 , x_3 \geq 0$. My approach: We have, $0 \leq x_3\leq n$ $\Rightarrow n \leq x_1 + x_2 \leq 2n$ ...
QuantumQuipster's user avatar
-4 votes
0 answers
34 views

Number of cases such that $p\mid (a^2- bc)$? [closed]

a,b,c belongs to { 0,1,2,...,p-1}; a not equal to 0 p is a odd prime number. Then number of cases such that a²-bc is divisible by p
Yash's user avatar
  • 1
1 vote
3 answers
78 views

Showing There is No Group Epimorphism from $S_n \longrightarrow \mathbb{Z}/2\times\mathbb{Z}/2$, $n\geq 1$

I know that the function $\text{sgn}: S_n\longrightarrow \mathbb{Z}/2$ is a unique group epimorphism. I am having trouble proving that there does not exist such an epimorphism bewteen $S_n\...
Luk'yan Vilshansky's user avatar
0 votes
0 answers
36 views

Application of Permutation

I have this problem below: In a row of six houses (numbered, in order, 1–6) live six married couples, each consisting of a woman and a man, a couple in each house. Each of the women also has (exactly) ...
user1295782's user avatar
-1 votes
0 answers
25 views

Let $I$ be the collection of all involutions (for all $n \geq 0$). Find the EGF for $I$. [closed]

A permutation $\pi$ of $[n]$ is said to be an involution if its cycle decomposition consists of only $1$- or $2$-cycles. Let $I$ be the collection of all involutions (for all $n \geq 0$). Find the EGF ...
Beehunter7's user avatar
2 votes
0 answers
47 views

Finding a simple graph such that its automorphism group equals the subgroup of $S_3$ generated by a 3-cycle

I have found that the subgroup of $S_3$ generated by a 3-cycle is $\{e,(123),(132)\}$ where $e$ is the identity but I can't find any graphs that have this group as their automorphism group. I am a ...
mantaray's user avatar
0 votes
1 answer
111 views

On the number of $\sigma\in S_{p-1}$ of a given form.

Let $p$ be a prime, $d$ a proper divisor of $p-1$, and $\sigma\in S_{p-1}$ of the form (everything is modulo $p$): $$\sigma=(1,x,\dots,x^{d-1})(i_2,i_2x,\dots,i_2x^{d-1})\dots(i_k,i_kx,\dots,i_kx^{d-1}...
citadel's user avatar
  • 2,803
0 votes
0 answers
22 views

Grimmett and Stirzaker P57 (Letter Matching) updated

https://math.stackexchange.com/posts/2854522/edit I was stuck on step 4 of the derivation below. A secretary types n different letters together with matching envelopes, she then drops the pile down ...
Bazman's user avatar
  • 867
2 votes
2 answers
67 views

Can we choose a set to make sure the action of a permutation group transitive?

Let a finite group $G$ of order $n$ be given, so $G$ is isomorphic to a permutation group embedded in $S_n$. Can we always find a set $\Omega$ such that $G$ acts transitively on $\Omega$? (For example,...
utx7563yu's user avatar
0 votes
2 answers
24 views

Rencontres Numbers

I'm having trouble understanding rencontres numbers, $D_{n,k}$. The numerical values shown of the wiki page: https://en.wikipedia.org/wiki/Rencontres_numbers Looking at n = 3: $D_{3,3} = 1$ I think I ...
Bazman's user avatar
  • 867
0 votes
1 answer
116 views

How many distinct bracelets can be made?

A bracelet contains at least 1 and at most 4 beads of identical size on a loop of string. Anna is making a bracelet and has 3 green, 3 blue and 3 red beads. How many distinct bracelets can she ...
Bonnie's user avatar
  • 9
0 votes
0 answers
17 views

How to calculate permutations with fixed order? [closed]

I have a template looking like How is #u# in #l# while #t#? #u# can have values u1, u2. They all must appear in the place of <...
Evgeniy's user avatar
  • 119
1 vote
2 answers
86 views

Value too large

There are 30 people who have to be seated into 5 rows of equal size where each row has 6 people and many people have preferences for which row they sit in. Other than that, people don’t really care ...
PsychBit's user avatar
-2 votes
1 answer
58 views

Permutation or Combination? [closed]

There are 9 people such as P1,P2,...,P9 who have to stand in a line but P1 and P2 will each get angry if they are not in the first 3 or last 3 spots in line. How many ways can these people line up ...
PsychBit's user avatar
4 votes
1 answer
101 views

Triple-Transitivity/"Specify three know all" property of exotic transitive $S_5\subset S_6$

Let the exotic transitive subgroup $S_5\subset S_6$ act on $\{1,2,\dots,6\}$. For $1\leq i,j\leq 6$, define subsets: $$X_{ji}:=\{\sigma\in S_5\,\mid \sigma(j)=i\}.$$ Does the following properties hold ...
JP McCarthy's user avatar
  • 8,340
1 vote
1 answer
86 views

Prove that there are $n! - (n-1)(n-1)!$ ways to arrange $n$ objects in a circular arrangement.

Prove that there are $n! - (n-1)(n-1)!$ ways to arrange $n$ objects in a circular arrangement. I have tried algebraic proofs by equating it to $\frac{n!}{n}$ and to $(n-1)!$ but can't think of a way ...
dingus's user avatar
  • 39
1 vote
0 answers
104 views

Using two copies of a decreasing $k$-tuple, can you form a convex decreasing $k$-tuple greater than the original sequence?

Suppose $(x_n)_{n=1}^{k}\ $ is a decreasing $k$-tuple of positive real numbers. Let $(y_n)_{n=1}^{2k}\ $ be two copies of $(x_n)_{n=1}^{k},\ $ that is, $$ y_n= \begin{cases} x_n&\text{if}\ 1\leq ...
Adam Rubinson's user avatar
1 vote
0 answers
31 views

Formulas to calculate the number of inversions for a permutation of n length: (help solving)

While reading Donald Knuth's "Sorting and Searching" I have come across a table of inversions which lists the numbers of inversions $k$ for a number of permutations of lengths $n$ (varying ...
nore's user avatar
  • 11
7 votes
1 answer
192 views

What exactly is the orbit-stabilizer theorem?

Obviously, being a professional group theorist, I know what the orbit-stabilizer theorem is. Or at least I thought I did. I thought that the orbit-stabilizer theorem was that if $G$ is a finite group ...
David A. Craven's user avatar
-1 votes
1 answer
42 views

Cyclic permutation with restriction, am i wrong? [closed]

there are 4 boys and 4 girls, how many ways they are arranged to sit in circular table if the 3 boys always together? i found someone's video and the answer is just 5!3!, there are 4 boys why he didn'...
cahya python's user avatar
2 votes
1 answer
81 views

Why $n! \sum_{k=0}^n \frac{1}{(n-k)!} = n! \sum_{k=0}^n \frac{1}{k!}$?

According to OEIS, the formula for getting the number of arrangements of any subset of n distinct objects is: $$\sum_{k=0}^n{n \choose k}k! = \sum_{k=0}^n\frac{n!}{...
bytrangle's user avatar
  • 121
2 votes
1 answer
80 views

amount of numbers in [10000] of which the sum of digits equals to a specific number

I am working on calculating the amount of numbers between 1 and 10000 with a specific sum of digits using combinatorics. In the first problem, I have to find it for 9 and I did. I constituted the ...
impressive305's user avatar
0 votes
1 answer
81 views

The "action" of outer automorphisms of $S_6$ on subsets of $S_6$

Let $S_6$ be equipped with the natural action on $\{1,2,\dots,6\}$. For $1\leq i,j\leq 6$, define subsets: $$X_{j\to i}:=\{\sigma\in G\,\mid \sigma(j)=i\}.$$ Let $X:=\{X_{j\to i}\mid 1\leq i,j\leq 6\}$...
JP McCarthy's user avatar
  • 8,340
1 vote
1 answer
91 views

Where in the original statement of the birthday problem is the order people of assign matter in the numerator of the probability?

In $\dfrac{365 \choose \#people}{365^{\#people}}$ this counts no repeats for the probability of none assuming Jan, Feb, March is the same thing as Feb, March Jan. If We interpret the question as ...
user avatar
0 votes
1 answer
86 views

Total Sitting Arrangements

There are 5 people sitting on 5 chairs arranged in a straight line, all facing north. Everyone gets up and can do only one of the following things at a time. (i) Sit back again in their original chair....
Techno Highway's user avatar
4 votes
1 answer
65 views

Permutations in "PERSNICKETINESS" with Constraints on Letter Placement

I'm tackling a combinatorial challenge with the word "PERSNICKETINESS". The task is to determine the number of permutations where the second "S" appears after the last vowel, ...
neo's user avatar
  • 79
-2 votes
1 answer
74 views

Algorithm for Weighted Permutation

Suppose we would like to permute a list of $n$ elements, such that for each element $a_i$, it has a $p_{ij}$ probability of being in the $j$th slot in the permutation, and we assume $\sum_{i=0}^np_{ij}...
user avatar
2 votes
1 answer
59 views

$10$ different balls are to be placed in $4$ distinct boxes at random. The probability that two of these boxes contain exactly $2$ and $3$ balls is:-

If $10$ different balls are to be placed in $4$ distinct boxes at random, then the probability that two of these boxes containing exactly $2$ and $3$ balls is:- Solving:- total ways $$n(s)=4^{10}$$ ( ...
Daksh's user avatar
  • 47
0 votes
0 answers
15 views

Given all permutations of a set with n elements and the mth permutation, find m [duplicate]

For example, if I have a set of all permutations of the set {1, 2, 3, 4} and the permutation 1, 4, 3, 2 how do i calculate which element of the set it is without calculating all the permutations?
wiktort1's user avatar
  • 101
2 votes
1 answer
78 views

Special Isomorphism?

I was thinking about this concept the other day, but I couldn't reach a solid conclusion. Visualise your right hand in front of you, and put your thumb, second and third finger in a configuration such ...
J.Dmaths's user avatar
  • 704
3 votes
3 answers
137 views

Permutation with repetition, more elements than slots to choose from

Using 3 A's, 5 B's, 7 C's, how many 4-letter word can you arrange them into? Note that here 3+5+7>4. We can't use the formula: $\frac{n!}{p!q! \cdots}$ because $\frac{4!}{3!4!7!}$ will be a ...
techie11's user avatar
  • 391
0 votes
0 answers
32 views

Need some help understanding Artin 1.5.10 proof on the product of permutations.

He writes: Why are both terms equal to zero unless i = qj? I really don't understand what's happening here. Edit: The ei,j terms, as usual, represent matrix units. The 'pi' and 'qj' refer to ...
idk's user avatar
  • 103
0 votes
3 answers
95 views

Possible Password Combinations with Requirements

I'm trying to find the number of password combinations that are exactly 6 characters long using: lower case letters (a-z, total: 26) upper case letter (A-Z, total : 26) numbers (0-9, total: 10) ...
user1288291's user avatar
1 vote
0 answers
19 views

Is there a simple closed form solution for the $n$th permutation of a unique-permutation?

Let $U_{n_1,\ldots,n_k}(n)$ for $0\le n \le \frac{(n_1+n_2+\cdots)!}{n_1!n_2!\cdots}$ be the function that produces the $n$th unique-permutation using integers $(0,\ldots,k-1)$, in lexical order. For ...
Bobby Ocean's user avatar
  • 3,173
0 votes
2 answers
125 views

Examples of nilpotent subgroups of $S_n$ which have less than say 10^9 elements?

To make some computational experiments with finite nilpotent group - it would be helpful to know the following: Question: What are the examples of nilpotent (but not commutative) subgroups in ...
Alexander Chervov's user avatar
-4 votes
0 answers
59 views

Consider a board having $2$ rows and $n$ columns. Thus there are 2n cells in the board. Each cell is to be filled in by 0 or 1.

Consider a board having $2$ rows and n columns. Thus there are $2n$ cells in the board. Each cell is to be filled in by $0$ or $1$. (a) In how many ways can this be done such that each row sum and ...
tripathybhanu's user avatar
1 vote
1 answer
118 views

How to mathematically compute the transition probabilities in the secretary problem

My model for the secretary problem is as in (1) in this Mathstackexchange question. More precisely, I look at the unit interval $I=[0,1]$, and $\Omega = I^n \smallsetminus D$ where $D \subset I^n$ is ...
Chertopkhanov on Malek Adel's user avatar
0 votes
1 answer
48 views

Rewriting a sum over permutations

Suppose I have the set $I_{n} = \{1,...,n\}$ and $n$ formal objects $x_{1},...,x_{n}$ (you can think of these as elements of some algebra). Let me write: $$S(x_{1}\cdots x_{n}) = \frac{1}{n!}\sum_{\...
InMathweTrust's user avatar
1 vote
1 answer
61 views

How many $n$-digit numbers are there with no or even number of $1$s in them if only digits $1$, $2$, $3$ and $4$ are allowed?

You are given an unlimited supply of each of the digits 1,2,3 or 4. Using only these four digits, you construct n digit numbers. Such n digit numbers will be called LEGITIMATE if it contains the digit ...
Daksh's user avatar
  • 47
1 vote
0 answers
17 views

Algorithm to create a polynomial invariant only under specific permutations of the variables

I was solving the following problem (1.2.10 from Dixon and Mortimer's Permutation Groups): Given the group $G =\langle(x_1,x_2, x_3, x_4),(x_1,x_3) \rangle$, give an example of a polynomial that's ...
Robert Lee's user avatar
  • 7,131
-1 votes
2 answers
116 views

How many positive integral solutions does $a+b+c+d+e=20$ have, if $a<b<c<d<e$? [closed]

Let $a<b<c<d<e$ be positive integers such that $a+b+c+d+e=20$, then the number of such distinct arrangement possible are __? Please also provide the general solution for every sum of ...
Sarvesh Kanth's user avatar

1
2 3 4 5
257