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

learn more… | top users | synonyms

7
votes
0answers
185 views

Citation for subset complement result

Let $S = \{s_1, \ldots, s_n\} \subset \{1, \ldots, 2n\}$. Consider two operations on $S$, unfortunately both called complement in different setting: let $A(S) = \{1, \ldots, 2n\} \setminus S$ (set ...
6
votes
0answers
89 views

Knuth equivalence of unshuffles

For any permutation $\sigma\in S_k$ and any $i\in\left\lbrace 1,2,...,k\right\rbrace$, I will denote $\sigma\left(i\right)$ by $\sigma_i$. For any word $w$, I will denote by $\mathrm{st}w$ the ...
6
votes
0answers
61 views

functions representable as a sum of two permutations

I am trying to prove that for every function $f:\mathbb{Z}/n\mathbb{Z}\to \mathbb{Z}/n\mathbb{Z}$ satisfying $\sum_if(i)=0$, there exist permutations $\pi_1, \pi_2:\mathbb{Z}/n\mathbb{Z}\to ...
6
votes
0answers
115 views

Expression of basis vectors of permutation modules in different bases.

Write $[n]:=\{1,\ldots,n\}$. For a partition $\lambda\vdash n$, I will write $[\lambda]$ for the Specht module that corresponds to $\lambda$, i.e. the complex vector space spanned by all standard ...
5
votes
0answers
131 views

How find this $aA_{m+1}=\overline{\sigma_{0}\sigma_{1}\sigma_{2}\cdots\sigma_{m}}$

Question let $m$ is positive numbers,and such $m\ge 5$,and $$A_{m+1}=\overline{1234\cdots m}=1\times (m+1)^{m-1}+2\times (m+1)^{m-2}+\cdots+(m-1)\times (m+1)+m$$(or see ...
4
votes
0answers
190 views

Special Products of Transpositions

[Edit. Significantly expanded to add examples and (I hope) clarification. Feel free to skim by reading the gray boxes.] A colleague asked me for insights on a collection of special permutations, ...
4
votes
0answers
93 views

Wikipedia's Cayley Table and Pictures for 3 by 3 Permutation Matrices

Are there any explanations or clarifications of the pictures at https://en.wikipedia.org/wiki/Permutation_matrix#Permutation_of_rows_and_columns? ...
4
votes
0answers
73 views

Selecting k numbers out of N sorted numbers to a minimize a condition/Formula

A sorted list of $\mathbf N$ numbers is given. $X_1$ $\le$ $X_2$ $\le$ $X_3$ $\le$ .... $\le$ $X_N$ Select $\mathbf K$ Numbers - $Y_1$ , $Y_2$ , $Y_3$ , ..... , $Y_K$ - Such that the following ...
4
votes
0answers
120 views

Is there a name for such matrices

Let $Z$ be a $K \times K$ matrix. All its left diagonal elements are zero. Further it satisfies the following properties: 1.) $Z[ i ][ j ] = Z[j][i] > 0$ for $1 ≤ i < j ≤ K$. 2.) $Z[i][j]$ ...
4
votes
0answers
43 views

Classification of $n \times n$ matrix in which each two components differ in each row and column up to automorphism

Suppose, we define a class $A$ of $n \times n$ matrix as follows: $$\text{In each Row }i, \text{for any} j,k\ (1 \leq j,k \leq n )\ a_{ij} \neq a_{ik} $$ $$\text{In each Column }l, \text{for any } ...
4
votes
0answers
72 views

Expectation of Reciprocals Involving Permutations

Let $a_i$ be $n$ distinct real numbers. What is the expectation: $$\mathbb E_\sigma \left[ \sum_{i=1}^{n} \frac {1} {a_{\sigma(i)} - \sum_{j=1}^{i-1}a_{\sigma(j)}} \right] $$ where the expectation ...
3
votes
0answers
45 views

Is there away to swap adjacent items in a sequence, such that each permutation occurs once?

Let's us say you have a finite sequence of things. Some are identical, some distinct. For example: $$\langle 2,5,7,2,3\rangle$$ Now, under what conditions can each permutation of a sequence be ...
3
votes
0answers
31 views

Naming elements of a group

Assume one comes across some set and constructs a finite groups out of these elements. One knows what group it is, names the elements from 1 to order of the group and constructs the multiplication ...
3
votes
0answers
24 views

(Counting problem) more challenging Modular N algebraic eqs - for combinatorics-permutation experts

Experts in algebra please help - Part II after Part I: we would like to know the number of solutions for this set of six of modular N algebraic equations: $$ x_1 y_2 = x_2 y_1 \pmod N \qquad (1) \\ ...
3
votes
0answers
67 views

Number of ways to order a list of permutations by swapping

I want to solve a problem and I have no idea how or where to begin. I don't even know if it's possible to solve. I tried to find any clues in books about discrete maths but I didn't find anything that ...
3
votes
0answers
107 views

Circular permutations - $n$ sitting at a round table without repeating neighbors

I hope this isn't a duplicate - the problem is to find the number of ways of sitting $n$ people (who initially were sitting in the order $1, 2, \dots,n$, with $1$ and $n$ being neighbors) at a round ...
3
votes
0answers
60 views

Probability/selection problem

Assume that we have $N$ items of $M$ distinct types in a closed bag. We also have $K$ bowls $(K \leq M)$ that can hold only items of same type. In the beginning bowls are empty. And bowls can hold a ...
3
votes
0answers
67 views

Permutation: How many ways to put 7 people in 10 rooms?

How many ways can 7 people be placed into 10 rooms, if (only) 2 of them can’t share a room with anyone? I'm not sure how to go about this, mostly because of the "share a room" bit. I'm thinking I ...
3
votes
0answers
79 views

Counting number of distinct systems

This is an enumeration problem in conjonction with some lottery problems. Given an integer $N \ge 5$. Let a ticket be a set of 5 distinct integers between $1$ and $N$. Given an integer $T$ between ...
3
votes
0answers
111 views

Is there a simple way to show that wreath product is associative?

Is there a simple way to show that wreath product is associative? If your proof is short, please write it explicitly. Thank you.
3
votes
0answers
165 views

Combinatorics Issue without repetitive combinations

We have 26 Boxes Labeled: Box 1, Box 2, Box 3 and so on. The boxes are in a specific order. We also have 15 rocks. Rocks are all identical. meaning Rock 1 is no different then Rock 2, or does not have ...
3
votes
0answers
120 views

Defining a signed involution

We define the displacement of $\pi$ as $\mathrm{disp}(\pi)=\sum_{i=1}^n|\pi(i)-i|$. I know that it's even. Could you help me to find a good signed involution of the set of permutation with ...
2
votes
0answers
54 views

Help calculating Combinations

A boy has n objects to paint, ordered in a row and numbered form left to right starting from 1. There are totally c colors, numbered from 0 to c-1. At the beginning all objects are colored in color ...
2
votes
0answers
205 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
2
votes
0answers
34 views

Possible number of permutations

I've generally been seeing the formula nPr = n!/(n-r)! to calculate the number of permutations. But this is the case only when elements cannot be repeated, am I correct? If elements can be repeated, ...
2
votes
0answers
38 views

Find k such that, $\displaystyle\frac{n^{\underline k}}{n^k}<a$

How to find k here $\displaystyle\frac{n^{\underline k}}{n^k}<a$ ? With, $n^{\underline k}=n\cdot(n-1)\cdot...(n-k+1)$ and $(n>k,\ a>0)$ Of course if $k\approx n/2$ the inequality ...
2
votes
0answers
17 views

Permutation elections

During a local campaign eight republician and five democratic candidates are nominated for president. a) If president to be one of thias candidates, how many possibilities are there for the eventual ...
2
votes
0answers
28 views

How many commutative block ciphers are there?

Let $K$ and $M$ and be two finite sets. Let $(G,\circ)$ be the group of permutations over $M$ under composition. Let a (implicitly: block) cipher with key in $K$ and message in $M$ be any application ...
2
votes
0answers
45 views

Composing permutations in factorial notation

Given two permutations $p_1$ and $p_2$ in factorial notation, is there a direct algorithm which computes their composition directly, i.e. without translating to a different notation or via computing ...
2
votes
0answers
18 views

Clarification on a cycle parity proof

Prove that cycle $(a_1a_2...a_k)$ is even $\iff$ $k$ is odd. This makes intuitive sense because $(a_1a_2a_3...a_k)=(a_1a_k)(a_1a_{k-1})...(a_1a_3)(a_1a_2)$ which will be an even number of ...
2
votes
0answers
37 views

Multiple Hypergeometric Distributions

I need to figure out a problem which involves multiple hypergeometric distributions. Referring to the Urn problem, the problem can be described like the following: We have $n$ urns $u_1,…,u_n$. Urn ...
2
votes
0answers
54 views

Symmetry of the pentagon and even permutation

I was doing part (iii). For the first part of that questions, $ D_{10} = \{e, \rho, \rho^2, \rho^2, \rho^4, \sigma\rho, \sigma\rho^2, \sigma\rho^3, \sigma\rho^4 \} $ where $\rho = (1 \ 2 \ 3 \ 4 \ ...
2
votes
0answers
78 views

Number of permutations when combining two sets?

I have two sets $\{a_{1},\ldots,a_{K}\}$ and $\{b_{1},\ldots,b_{L}\}$, where I know that $a_{1} \leq a_{2} \leq \cdots \leq a_{K}$ and $b_{1} \leq b_{2} \leq \cdots \leq b_{L}$, but do not know the ...
2
votes
0answers
65 views

How many different ways can 10 octupuses touch legs?

There are 10 octopuses (octopi?). Each octopus has 8 legs. Legs on an octopus can only touch touch legs on other octupuses. Assuming each leg touches exactly 1 other leg, how many different ...
2
votes
0answers
38 views

Decomposition of disjoint cycles

Work out the decomposition in disjoint cycles for the following. a) (14)(12345) = (15)(234) b) (12)(2345) = (12345) c) (12)(23)(34) = (14)(24) d) (13)(1234)(13) = (143)(2) Can anyone tell me ...
2
votes
0answers
45 views

What is the probability of winning.

$2$ teams of $5$ players each play a game against each other in pairs. Find the probability that no team wins all the games and no team loses all the games. I tried to solve and determined that there ...
2
votes
0answers
70 views

How many combinations does Android pattern have?

Rules- 1) At-least 4 and at-max 9 dots must be connected. 2) There can be no jumps 3) Once a dot is crossed, you can jump over it.
2
votes
0answers
81 views

Sign of some permutation.

I trying to find the sign of this permutation: $\left(\begin{array}{cccccccccc} 1 & 2 & 3 & \cdots & \cdots & \cdots & \cdots & \cdots & n-1 & n\\ 2 & 4 & ...
2
votes
0answers
70 views

Find all possible solutions!

Find solutions for $$^nP_r=s!$$ For $(n,r,s)\in \mathbb{N}$ I could find some trivial solutions $(6,3,5)~,~(1,1,1)$ etc.
2
votes
0answers
49 views

What's the connection between irreducible polynomials and fixed-frobenius elements in a finite ring?

Consider the ring $A_{p,n} = \mathbb{F}_p [x]/ (x^{p^n}-x)$. It has a basis $\{1, x, x^2, \ldots, x^{p^n - 1}\}$. The Frobenius endomorphism $x \mapsto x^p$ permutes elements of this basis. I've ...
2
votes
0answers
142 views

Every group is isomorphic to a group of permutations?

Theorem: Every group is isomorphic to a group of permutations. Proof: Would Cayley's Proof from 1854 suffice the proof to this theorem?
2
votes
0answers
77 views

Number of permutations possible?

Given two permutation of $1, \ldots, N$. Where 3<=N<=1000 Example For $N=4$ First is $\begin{pmatrix}3& 1& 2& 4\end{pmatrix}$. Second is $\begin{pmatrix}2& 4& 1& ...
2
votes
0answers
154 views

Getting K heads out of N biased coins problem (formula generation ).

Problem- Given a set of coins n with each coin i having Pi probability to give heads. Find the probability of getting k heads, when all coins are tossed together. hi i have solved this problem ...
2
votes
0answers
175 views

Is it possible to find sum of this series?

I am trying to find the sum of the following series asked by my friend. $$n\cdot\left(\bigl\lfloor\tfrac{n}{2}\bigr\rfloor+ \bigl\lfloor\tfrac{n}{3}\bigr\rfloor+ \bigl\lfloor\tfrac{n}{4}\bigr\rfloor+ ...
2
votes
0answers
69 views

numbering permutations with repeated items

I want to number each permutation of ${1,1,1,1,0,0,0,0,0,0,0,0}$ (4 ones and 8 zeros) with a number. There are $\frac{12\cdot 11\cdot 10 \cdot 9}{4\cdot 3\cdot 2\cdot 1} = 495$ permutations. I want ...
2
votes
0answers
208 views

Summation equivalence in proof of permutation as composition of transpositions.

First of all, good morning everybody. My problem is related with a summation equivalence presented in one demostration. In the fifth summation presented in this link, here. The one which replaces the ...
2
votes
0answers
235 views

Number of permutations such that no two adjacent elements in the original remain adjacent

$N$ students are standing in a line. How many permutations exist such that no two students who were originally next to each other remain next to each other? Suppose $n=4$ and assuming the original ...
2
votes
0answers
47 views

Terminology: is there a term for one order being on a geodesic between two others in the Cayley graph?

Think about the graph whose nodes are total orders on a finite set, and whose edges connect orders that only differ on two elements. This is actually a Cayley graph of $S_n$, but I don't want to fix ...
2
votes
0answers
293 views

sum with permutations

Let $a$ be vector in $R^{2m}$. And let $S_{2m}$ be group of all permutations on the set $\{1,\dots,2m\}$. I would like to calculate $$ \sup_{\pi\in S_{2m}}\sum_{d(\sigma, ...
2
votes
0answers
73 views

Is $P_\omega$ a $p$-Sylow subgroup of $G_\omega$

We have the following theorem Let $G$ be a group, acting on a set $\Omega$ and let $p^m\Bigm||\omega^G|$ wherein $p$ is prime and $\omega \in \Omega$. If $P$ is a $p$-Sylow subgroup of $G$ then, ...