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
1
vote
0answers
17 views

Algorithm for Gaussian elimination to permutation matrix over $\mathbb{Z}_2$

I wish to find an algorithm that reduces a matrix over $\mathbb{Z}_2$ to a permutation matrix using as few row summing operations as possible. Standard Gaussian elimination turns a matrix into the ...
2
votes
3answers
41 views

A question about weights

I have a question, but I'm not sure if this question is for this group or another ( I seem to remember there's another group for this kind of questions though ): A guy has $100$ stones, and they're ...
2
votes
2answers
34 views

In how many ways can 20 persons be seated round a table if there are 9 chairs?

The problem given is in the title: In how many ways can $20$ persons be seated round a table if there are $9$ chairs? I tried solving it as follows: I can fix one person to one of $9$ chairs. I ...
1
vote
0answers
36 views

Decomposing a cycle into transpositions

I am trying to go through some lecture notes found here, and am struggling with an assertion on page 21. It is meant to be a proof that any cycle $(a_1,..,a_k)$ can be written as a product of ...
0
votes
0answers
16 views

number of ways of selecting n balls from m buckets with each having different number of balls [duplicate]

Imagine you have been given n different colored balls and a task to choose at most k balls from them such that none of the same colored balls is selected for any given sequence and considering same ...
-1
votes
0answers
32 views

Why is a permutation braid ,a positive word?

How do we prove that every permutation braid is a positive word belonging to $B_n^+$? Geometrically, we can observe that each crossing is positive, so we should be able to write it as a word in $B_n^+...
1
vote
1answer
22 views

Number of lines in a tic tac toe of width $w$ and dimension $d$

I was watching a video by pbs infinite series on tic-tac-toe(https://www.youtube.com/watch?v=FwJZa-helig). Here, they discuss if there is a winning strategy for the starting player in tic-tac-toe of ...
0
votes
1answer
55 views

Question for product and inverse in group theory I think

I have a question which I assume is under Group or set theory. I have attempted to answer it but I have now a colleague is saying I am wrong. Need your wisdom on it please. Question: Consider the ...
1
vote
1answer
24 views

Can we swap items in a list an odd number of times without changing it?

Suppose there is a list with finitely many distinct items. In each move we swap two of them. How to show that it is impossible to make moves odd times and make the list back to the original state? (...
0
votes
1answer
25 views

On the co-primality of bracelet-type binary numbers

Let an integer N be the number of digits imprinted on a bracelet, which can come in two values, 1 and 0. You can produce a binary number by writing down the 1's and 0's on the bracelet from left to ...
9
votes
1answer
110 views

How to find the order of a Rubik's cube algorithm?

For example, the algorithm $R U R' U'$ has an order of $6$, that is, repeat the algorithms $6$ times to return to the original position. How would I go about finding the order of any other algorithm?
0
votes
1answer
49 views

Changing positions about 10 people around a circular table

Consider 10 people sitting around a circular table. In how many different ways can they change seats so that each person has a different neighbor to the right? I'm not sure about my answer. It is an ...
1
vote
1answer
25 views

Number of permutations with k inversions

Let: $P_n(x) = 1(1+x)(1+x+x^2)+ \dots +(1+x+x^2+ \dots +x^n)$ I heard that the $k$-th coefficient of $P_n(x)$ is the number of permutations $\sigma \in S_n$ with $k$ inversions and I want to prove ...
1
vote
2answers
58 views

What is the probability of drawing a number which is equal to the number of the draw?

I am dealing with a problem right now. It sounds like this: assume that there are N papers with numbers throughout 1 to N in a box. Whenever one of them is drawn it is not put back in the box. What is ...
-2
votes
0answers
48 views

Arya is P times of Sansa [duplicate]

Arya Stark and Sansa Stark are sisters but often fight with each other for one or the other reason. Recently, Sansa beat Arya by cheating in the hunt game and made fun of her. Arya is full of anger ...
-1
votes
1answer
25 views

Coefficient of an expansion

Find the coefficient of $x^k$ in $(x+a)(x+b)...(x+n)$ where $a$, $b$ and $n$ are integers. I am not able to approach this problem.
0
votes
0answers
18 views

Sum of n sums, Permutations of the indices, how to write them in Mathematica? [on hold]

I was wondering how to write a function $ F (r, q, n, f) $ in Mathematica, defined in this way: $$F(r,q,n,f):=\sum_{i_0=1}^q f(i_0) \Biggl(\sum_{i_1=i_0+1}^{q+1} f(i_1)\biggl(\sum_{i_2=i_1+1}^{q+2} ...
1
vote
1answer
37 views

How to obtain the number of RNA chains after a selective fragmentation?

The problem is as follows: A molecular scissor is an enzyme which breaks down RNA chain. At a laboratory a technician uses a G-enzyme into the chain CCGGUCCGAAAG and it gets broken in the sites ...
0
votes
1answer
32 views

Expressing a set of Permutations as tuples

Say we want to construct a 5 letter word from the English alphabet $E=\{\mathsf a, \mathsf b, \dots,\mathsf z\}$, with repetition not allowed. Suppose for the moment, that repetition is allowed. In ...
0
votes
0answers
36 views

No of ways of making Garland using different kinds of flowers [duplicate]

Question: There are 6n flowers of one type and 3 flowers of another type, total no of garlands possible? My approach-: I have considered 3 cases Case 1. Garland contains only 6n flowers No of ...
1
vote
1answer
51 views

Composition law defined by a map of elements' labels.

Let: $G$ be a finite set, say $G=\{a_1,\dots,a_n\}$; $I_n:=\{1,\dots,n\}$; $f\colon I_n \times I_n \rightarrow I_n$ a map. The composition law: $$a_ia_j:=a_{f(i,j)}$$ turns $G$ into a group ...
0
votes
1answer
31 views

double derangement

Let $[n]$ be a set with $n$ elements. Two derangement of this set, $\sigma$ and $\psi$ contents the next condition. $for\ \forall i\in [n], \sigma(i)\neq \psi(i)$ This condition make $\sigma$ also a ...
-2
votes
0answers
22 views

Forming Rival Teams given individual Player Rivalry

Suppose there are $N$ people. You are given pairs of the form $u, v$ which means that person $u$ and a person $v$ are rivals. Two teams($T_1$ and $T_2$) are rival iff for each pair $x,y$ where $x$ ...
-3
votes
0answers
28 views

COMPLEX SPORTS COMPETITION FIXTURES PLAN [on hold]

I need a schedule for a 7 team weekly league. Each team plays 6 games. The games are played at 2 venues with 3 teams attending each venue where they play the other 2 teams attending (1 team is not ...
0
votes
0answers
12 views

Partitioning elements - Group Testing for a Contaminant

My question relates to finding which of $n$ vials contains a "contaminant" with $\lceil{\lg n \rceil}$ tests, completed at the same time. In order to test this, the experimenter is allowed to mix ...
1
vote
1answer
16 views

How many different crews have a robot as leader? exactly one robot on the crew? at least one robot on the crew?

I can solve for how many ways there is to choose five team members from $16$ workers $= 16C5$. But, I'm having a hard time figuring how to approach the other question can anyone guide me in the right ...
0
votes
0answers
18 views

Regarding longest increasing subsequences in permutations of n elements

I was trying to solve a problem wherein I had to find the number permutations of $n$ elements which have a longest increasing subsequence (LIS) of length $m$. Ideally, I'd want to have a function $F(n,...
0
votes
1answer
39 views

Among the numerals 1., 2, 3, 4, 5, and 6 how many 4- number combinations can be made so that there would not be three consecutive numbers in a row? [on hold]

Among the numerals 1, 2, 3, 4, 5, and 6 how many 4- number combinations can be made so that there would not be three consecutive numbers in a row?
4
votes
1answer
39 views

How many ways can you arrange 3 pennies and 2 nickels in a line?

All coins of the same type are indistinguishable. So I start with a 5 choose 3 for the pennies. 5!/(3!2!). Giving me 10 ways to arrange the pennies. For each combination of the pennies it ...
3
votes
0answers
62 views

Worst case for algorithm solving a game

I came up with the following algorithm on a whim, and it doesn't relate to any deeper mathematics, but I'd like to see if someone can prove a connection it has to a sequence I found. You can think of ...
1
vote
1answer
24 views

Finding matrix representation of linear transformation with respect to permuted basis

I'm struggling with understanding how I can figure out exactly what the following matrix representation looks like: Let $V$ be an $n$-dimensional vector space. Let $\mathcal{B} = (b_1,\ldots,b_n)$ ...
0
votes
2answers
19 views

Multiplication of cyclic permutation

Find $f^{-1}gf$, where $f=(123)$, $g=(2345)$. Since $f$ and $g$ are cyclic permutations, we have $gf=fg$. Hence $f^{-1}gf=f^{-1}fg= (f^{-1}f)g=ig=g=(2345)$, where $i$ is identity permutation. Since i ...
1
vote
0answers
32 views

How many n-bit binary numbers can be formed such that, for every prefix (position) the number of 0's is at least 'x' times than the number of 1's?

For ex- (1) if n = 5 and x=3 Then 3 such binary nos. are possible, which are- 00000, 00001, 00010 All these nos have no of 0's at least 3 times the no of 1's at any prfix(position) (2) if n=6 and x=...
15
votes
2answers
297 views

The best $n$-digit password?

I suddenly thought of a question today: What is the best $n$-digit password? It is not specific so I'll write it in a better way: There is a password lock that has $n$ digits. There are $t$ choices ...
0
votes
1answer
53 views

Find number of ways to select subset with distinct objects of at most K size.

I have a set of x number of 'A' type object, y number of 'B' type object and z number of 'C' type object. Now, I need to find the number of subsets of atmost 'k' size that can be made such that all ...
3
votes
1answer
41 views

Proving a matrix has Kronecker product form

Is there a property unique to Kronecker product of two matrices, so that one could use it to prove that a certain matrix has Kronecker product form? Is there a proof technique to this type of ...
-3
votes
1answer
37 views

Permutations question - very confused and our teacher has taught us nothing. Any input would be helpful so thanks very much! [closed]

A computer randomly selects 4 digits from between 2 and 8 (includes both 2 and 8) a) repetitions are not allowed b) no repetitions are allowed and it must start with an 8? c) no repetitions are ...
1
vote
0answers
25 views

Permutations Questions - How many ways to order books with constraint?

Question: There are 50 books. Dan tries to order them. His only constraint is $5$ books by Dan Brown that need to be next to each other. How many possible orders for the $50$ books are there ...
0
votes
1answer
39 views

Permutations on circular table so that i cannot go to i or i+1.

Suppose $n$ objects are placed in a circular table in clockwise order. Find the no of permutations where $i$ cannot go to $i$ or $i+1$. i.e. $1$ cannot be mapped to $1$ or $2$, $2$ cannot be mapped to ...
3
votes
1answer
31 views

Over-Counted Permutations

Setup We have 4 unique cards I am trying to find the probability that none of them are in the same position after shuffling The Given Solution My Questions They reason that there are 4 ...
1
vote
2answers
32 views

How to interpret this combination formula

If you have $m$ and $n$ number of distinct items, and you get to choose $p$ and $q$ things respectively out of them, then the number of ways you can permute $p+q$ items is as follows: $m$ items can ...
0
votes
0answers
26 views

Number of arrangements of one $1$, two $2$'s, three $3$'s, four $4$'s, …, and nine $9$'s (given constraints)

We have no zeros, one $1$, two $2$'s, three $3$'s, four $4$'s, five $5$'s, six $6$'s, seven $7$'s, eight $8$'s, and nine $9$'s. How many $12$-digit numbers can we make using at least three $6$'s so ...
3
votes
2answers
119 views

In how many ways can $14$ people be seated in a row if there are $8$ men and they must sit next to one another?

In how many ways can 14 people be seated in a row if: a.) there are 7 men and 7 women and no two men or two women sit next to each other? My attempt: Since no two men or women can sit next to each ...
1
vote
1answer
45 views

Count Subsets of size less than equal to k [duplicate]

This is a variation of question asked on this site before. Consider a set with $𝑎_1$ 'distinct' 1s, $𝑎_2$ 'distinct' 2s, ... , $𝑎_𝑛$ 'distinct' ns. You have $𝑎_1+1$ choices for the 1s (including ...
0
votes
1answer
19 views

Number of three-digit even numbers with no repeat condition.

I have to find the total number of three-digit even numbers where no digit can be repeated. I tried and got answer $9 \times 9 \times 5$, but it is wrong. There is something weird with $2$ digits. I ...
0
votes
1answer
30 views

What is the connection between number of permutations and number of subsets? [closed]

How many different ways to fill 100 boxes in a line with black or white balls. (One box can only contain one ball at a time.) My attempt : Different ways to fill 1 st box = 2 Different ways to fill ...
3
votes
2answers
110 views

How many ways can $2$ different history books, $5$ different math books, and $4$ different novels be arranged on a shelf if …?

This is my first class in probability so I just wanted verification as to my attempted solution. Question: In how many ways can $2$ different history books, $5$ different math books, and $4$ ...
0
votes
0answers
51 views

Proof the existence of identity element in a group of $n!$ permutations on a set of $n$ elements

We know that $n!$ permutations on a set of $n$ elements is a group. A proof of this statement starts by considering a set $S=\lbrace a_1, a_2, ..., a_n\rbrace$ and $S'=\lbrace p:~p~\text{is a ...
0
votes
1answer
33 views

Arranging the $26$ English letters in a row given two constraints

In how many ways can we arrange the $26$ English letters in a row so that no two vowels are adjacent to each other, and each block of consonant(s) (between $2$ vowels) is/are in alphabetical order?...