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

learn more… | top users | synonyms (1)

2
votes
1answer
20 views

For counting permutations with identical objects, why does dividing nPr by the factorial of the number of identical objects give the correct answer?

I can find plenty of sites that say that this works, but I can't seem to find an explanation for why it works. I'm rather stumped.
1
vote
2answers
19 views

Expected sum value of permutaion

We have a set(A) of N elements. Let's assume elements are e1,e2,e3..etc. Value of each element can be 0 or 1. Another set of N elements(set B) are given, ...
0
votes
1answer
25 views

Linear Algebra - Permutations

Is it possible to multiply two permutations of different lengths together? If so how would you go about doing it?
1
vote
2answers
45 views

Suppose a coin in tossed $12$ times and there are $3$ heads and $9$ tails. How many sequences…

Suppose a coin is tossed $12$ times and there are $3$ heads and $9$ tails. How many sequences are there in which there are at least $5$ tails in a row? I know this is Permutation with repetition. My ...
0
votes
0answers
41 views

How many ways to arrange these gifts? (Inclusion-exclusion\derangement)

Each one of 30 people has bought 2 identical presents for the poor (every person's gifts are different from everyone else's). All the gifts were put in a large bag. In turns, 30 poor people ...
0
votes
2answers
2k views

There are $7$ empty seats on a bus and four people get on. How many different ways can they be seated?

There are $7$ empty seats on a bus and four people get on. How many different ways can they be seated? Would it be ${}^7C_{4}$ or ${}^7P_{4}$?
2
votes
1answer
30 views

Using the Binomial Identity, prove that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Using the Binomial Identity, prove that: $${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$$Because this is in the form of a Binomial Coefficient, I can break down the LHS ...
1
vote
1answer
438 views

How many different ways can you choose a group of $4$ people?

You have a total of $9$ people to choose from. Of these $9$ people you are supposed to create a group of $4$. How many different ways can the new group look? This is my reasoning: To the new group, ...
0
votes
1answer
29 views

How does $9\choose 4,3,2$ $=8$ $7\choose 4$

Can someone please explain to me how $9\choose 4,3,2$$=8$$7\choose 4$? From my understanding $9\choose 4,3,2$$ = $$9\choose 4$$5\choose 3$$2\choose 2$$=$$9\choose 4$$5\choose 3$$\cdot 1$ But for ...
4
votes
1answer
25 views

Counting permutations in $S_n$ with $1,2,..,k$ all in same cycle

The number of permutations in $S_n$ for which the first $k$ items $1,2,...,k$ are all in the same cycle can be shown (by a somewhat tedious argument) to be $n!/k.$ I'm looking for less computational ...
1
vote
0answers
27 views

Finding a particular permutation

Simple Notation: For a permutation $P=(a_1,a_2,...,a_n)$ , we define $\{P_k\} = \{a_1,a_2,..,a_k\}$. (i.e. set of first $k$ numbers). Problem: Given $N=\{1,2,3,..,n\}$ and $m$ subsets of it, $S_1, ...
3
votes
0answers
18 views

Determinant of $\delta$ function

Let $$\delta_i^j=\left\{ \begin{aligned} 1 ~~~~~~i=j \\ 0 ~~~~~~i\ne j \end{aligned} \right. $$ $1\le i,j\le n$. How to prove $$ \begin{vmatrix} \delta_{j_1}^{i_1} ~...~ \delta_{j_n}^{i_1} \\ \\ ...
1
vote
0answers
11 views

Calculating the number of permutations that do not have at least one set of duplicate elements adjacent.

Ok, so I've got a set of elements, some are duplicates but each are considered unique as far as set-making goes. I need to find how many permutations exist that do not put two of the duplicates next ...
0
votes
1answer
25 views

Mr and Mrs Zimmerman want to give their baby a first name and a second name so that the baby's three initials are in alphabetical order.

Mr and Mrs Zimmerman want to give their baby a first name and a second name so that the baby's three initials are in alphabetical order. How many different initials could this baby end up with eg. ...
1
vote
1answer
19 views

Permutations of $n$ objects where $r = n -1$

In my text book the question is as follows: Find the way in which $5$ persons can sit in a row if two insist on sitting next to each other. They give the answer as $48$. I fail to understand how ...
1
vote
2answers
30 views

Permutations and Combinations based probblem

Find the value of the expression: $$ 1+1\times1!+2\times2!+3\times3!+.....+n\times n! $$ It is a problem based on the concept of permutations and combinations I don't have a perfect idea to solve ...
8
votes
0answers
76 views

Covering pairs with permutations

Consider an $n \times n$ matrix $M_n$ with the following properties: Each row is a permutation of $A_n \equiv \{1, 2, ..., n\}$. Every ordered pair $(i,j)$, $i,j \in A_n$, $i \neq j$, appears as a ...
-2
votes
1answer
17 views

For any permutation $ \sigma \in S_n$, $(σ(1) − 1)(σ(2) − 2) . . . (σ(n) − n)$ is even when $n$ is odd [on hold]

Let σ be a permutation of ${1, 2, 3, . . . , n}$, n odd. I want to show that $(σ(1) − 1)(σ(2) − 2) . . . (σ(n) − n)$ is even. Thank you.
-2
votes
1answer
16 views

Numbers of words allowing repetition [duplicate]

10 different letters of an alphabet are given. words with 5 letters are formed from these given letters.I have to determine the number of words which have at least one letter repeated. Answer is - ...
0
votes
1answer
41 views

Combinatorics problems involving permutations

Let $A= \{ 1,2,3,...,n\}$ a set and $f:A \to A$ a permutation of the set A. We call a number $x \in \{ 2,3,...,n-1 \}$ special if $f(x)>\max \{f(x-1),f(x+1) \}$ or $f(x)<\min \{f(x-1),f(x+1) ...
0
votes
4answers
18 views

sum of numbers formed by permutations

I have digits 2,3,4,5. I have been asked to find the sum of all 4 digits the numbers that can be formed using these digits without repetition such that all are included in the number. Can someone ...
1
vote
1answer
29 views

I need help answering a few simple math problems related to permutations and probability

Question 1: How many words can you make from the letters Texas if repeats are not allowed? Question 2: How many words can you make from the letters Texas if repeats are allowed? Question 3: What is ...
0
votes
0answers
27 views

Divisibility of N [on hold]

If there are $N$ tuples $(a,b,c)$ such that they are positive integers and $a>b>c$ and $$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}=\frac{1}{2}$$ then $N$ is divisible by ? The answer is an integer ...
2
votes
1answer
59 views

What is the probability that a five-card poker hand has four ACES?

What is the probability that a five-card poker hand has four ACES? When I was solving the above stated problem, I got confused while trying different methods : Assume a normal $52$ deck of ...
0
votes
1answer
21 views

Polynomial roots conditions vary with coefficients

Polynomial equation $\sum_{i=0}^4 p_i x^i=0$ have the following root conditions: 1) $a_0 \pm b_0 i, a_1 \pm b_1i$ 2) $a_0 \pm b_0 i, a_1, a_2$ 3) $a_0, a_1, a_2 \pm b_2i$ 4) $a_0, a_1, a_2, a_3$ I'm ...
0
votes
2answers
16 views

Sign of composition of transpositions

Let $\sigma \in S_n$. Definition: Suppose that $\text{sign}\sigma=(-1)^N$, where $N$ - number of inversions in permutation $\sigma$. Suppose that $\tau_1$ and $\tau_2$ transpositions. How to prove ...
0
votes
1answer
29 views

Find commuting elements within a permutation group

The question is like this: IF $G=S_5$ and $g=(1\quad 2\quad 3)$, determine the number of elements in $H=\{x\in G:xg=gx\}$. To do the question, first it says $$x(4)=(x(1\quad 2\quad 3))(4)=(1\quad ...
-1
votes
1answer
18 views

How many possible placements are there for a Battleship puzzle?

I am studying the NP-Completeness of the battleship puzzle; the pencil and paper game found in newspapers and not the more popular 2-player version. I understand why the puzzle is NP-Complete because ...
1
vote
1answer
33 views

Fourier transformation of a group

At the beginning of the section 4 of Fast Quantum Fourier Transforms for a Class of Non-abelian Groups, it is said that, ... calculating a Fourier transform for a group $G$ is the same as decomposing ...
1
vote
1answer
18 views

Sign of permutation. Confusing example

Let $\sigma=(2314)\in S_4$. We have different definitions of sign of permutation. 1) Our $\sigma=(24)(21)(23)$ hence $\text{sgn}\sigma=(-1)^3=-1.$ 2) Our $\sigma$ has two inversions namely $(2,1)$ ...
0
votes
1answer
18 views

Does every partition of n correspond to some permutation of [1,2, … n]?

It is known that every permutation can be decomposed into disjoint cycles. The cycle type gives the length of each cycle. The sum of cycles length is n. I am wondering whether every partition of n ...
2
votes
1answer
43 views

what is the smallest non-abelian finite group which has normal, non-abelian subgroups (plural)

I am looking for smallest example of a group $G$ such that: $G$ is a finite, non-abelian group $G$ is not simple $G$ has non-trivial, proper, normal subgroups: $H_1, H_2, \dots $ $H_1, H_2, \dots $ ...
0
votes
0answers
21 views

Cycle structure of the generators of the dihedral group

Would the following be correct about generating the dihedral group $D_n$ by permutations? If $n$ is even, the group can be generated as $\langle(2\quad n)(3 \quad n-1) \ldots (\frac{n}{2}-1 \quad ...
1
vote
2answers
52 views

Partition of natural number not equal to factorial

I wish to prove the following statement so I can use it as a lemma for a group theory result. To be honest I have not tried much yet, my intuition tells me this is going to be connected to the ...
0
votes
1answer
384 views

Determining Permutation/Combinations with Bit Strings

I've got a discrete math problem on my hands...I'm trying to understand the steps behind working with bit strings; specifically, how a bit string of x length has "at least" or "exactly" a certain ...
0
votes
1answer
21 views

permutations of n objects

Does the number of permutations of $n$ objects, $r$ alike of one kind and $n−r$ alike of another kind, always equal the combinations of n different objects taken $r$ at a time? Explain. I know ...
0
votes
1answer
15 views

Arrangements of crew in two sides of a boat - permutations and combinations

A boat crew consist of 8 men, 3 of whom can row only on one side and 2 only on the other. The number of ways in which the crew can be arranged is This is a problem my math teacher has given ...
2
votes
1answer
81 views

Random permutations composition

I'm trying to prove a theorem that seems very intuitive. However, I seem to be missing a piece of the puzzle. If: $\pi$ is a random permutation ($S_n$), $\pi_1, \pi_2$ - random permutations with ...
-3
votes
1answer
68 views

Simple Question on Binomial theorems… [closed]

I have tried to solve this question by putting the value of each coefficients but it is really becoming very lengthy.... what i got was this number 10510100501... But how to get this in the required ...
2
votes
4answers
7k views

how many 5 digit numbers are there with distinct digits?

I found this question on gre forum, it's answer was given by this expression: $9\cdot9\cdot8\cdot7\cdot6$ which I heard in school as well. What I tried to do was: for numbers from index $4$ to ...
7
votes
2answers
549 views

Number of ways of visiting N places

A tourist wants to visit $N$ cities, each numbered from $1$ to $N$, but he wants to visit them in a weird order. A weird order is such in which no city numbered $i$ is the $i$-th to visit in his ...
3
votes
1answer
30 views

How many straight lines can be made between 10 points such that 4 of them are colinear?

So i know how to get the answer. We just have to find $C(10,2)$ and subtract $C(4,2)$ and add 1. We are basically counting all the points between co-linear points as 1. So the question is why we are ...
0
votes
3answers
73 views

How many distinct ways can the number be written as product of $3$ factors?

How many distinct ways can the number $126$ be written as a product of $3$ positive integer factors? I found that the prime factors are $126=2\times3\times3\times7$. But how to get number of ...
2
votes
1answer
19 views

For each of the following restrictions, find the smallest size n for strings over $\{a, b, c\}$ that can be used as codes for $27$ people.

For each of the following restrictions, find the smallest size $n$ for strings over $\{a, b, c\}$ that can be used as codes for $27$ people. a. There are $k$ $a$’s, $l$ $b$’s, and $m$ $c$’s and $k + ...
3
votes
2answers
42 views

What is probability that out of the first half on N objects, none will be matched with their own label?

The problem: We have N (even) objects ordered $o_1 ... o_N$ , each having their own label. The labels are reassigned to the objects randomly. What is the probability that that neither of the first ...
5
votes
2answers
95 views

If we are given that a list of $n$ numbers has $11,660$ derangements, what is the value of $n$?

The Full Question For the positive integers $1,2,3,\dots n-1,n$, there are $11,660$ where $1,2,3,4,5$ appear in the first five positions. What is the value of $n$? My Work First I considered all ...
2
votes
1answer
22 views

Understanding derangement.

From the inclusion-exclusion principle we get that out of $N$ objects with one label each, there is a probability of $$\sum_{k=1}^N (-1)^{k+1}\frac{1}{k!}$$ that a random assignment of the $N$ labels ...
0
votes
0answers
23 views

Centralizer of $\sigma\in S_n$ [duplicate]

Let $\sigma\in S_n$ . Describe the centralizer of $\sigma$. Thought: If I conjugate $\sigma$, then $\tau^{-1}\sigma\tau=\sigma.$ This means that $\tau$ is a power of $\sigma,$ and ...
1
vote
1answer
24 views

How many ways are there to arrange the letters of word $ALGEBRA$ such that the relative order of the vowels and consonants doesn't change?

I did this question this way :- there are 4 consonants in the words (LGBR) and there are 7 letters in the word. $therefore$ number of in which consonants can be arranged in relative order will be ...
0
votes
2answers
35 views

A question of permutations and combinations with six cards and six envelopes.

Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same ...