questions regarding the re-orderings of some finite set of objects.
0
votes
2answers
23 views
How many elements are in the conjugacy class of $\tau \in S_9$?
Just one simple question:
Let $\tau =(56789)(3456)(234)(12)$.
How many elements does the conjugacy class of $\tau$ contain? How do you solve this exersie?
First step is to write it in disjunct ...
-3
votes
0answers
29 views
Permutations questions [closed]
thanks for the person that helps me on this question. I need it to be answered within the next hour if possible!
I am struggling to grasp the method that I need to use. I know the formula, but these ...
0
votes
1answer
22 views
Anagrams with sequences inside
I need some help with this exercise:
Find the number of anagrams of the word “MONOCROMO” containing atleast one of the sequences “OMO”, “MON”, “CRO”.
Normally I know what to do, but in this one ...
3
votes
3answers
48 views
Matrix which commutes with permutation matrix
I'm trying to show that if $A$ commutes with all $3\times 3$ permutation matrices, then $A$ has to be of the following form:
$ A =
\begin{pmatrix}
a & b & b \\
b & a & b \\
b & b ...
1
vote
0answers
27 views
Partition Proof
Let $\lambda$ be a partition of $N$ of rank $r$. How can I show that:
$$\sum_wx^\lambda(w)=f^\lambda(-1)^{t(\lambda)}\prod^r_{i=1}(\lambda_i-1)!(\lambda'_i-1)!$$
where $w$ ranges over all ...
1
vote
3answers
46 views
How many different numbers are composed by n repeated digits?
For example, there are 3 digits: 1, 1, 4 and they compose 3 different numbers: 114, 141, 411.
My questions is: given n repeated digits: 1 * n1, 2 * n2, 3 * n3, ..., 9 * n9, in which ni >= 0 and n1 + ...
1
vote
2answers
57 views
What powers of an $18$ cycle permutation are also $18$ cycles?
Suppose we are given a permutation $A = (1,2,...,18)$ which is an $18$ cycle in $S_{18}$. We want to find $i \in \mathbb{Z}$ such that $A^i$ is also an $18$ cycle. Now I know how to do this by trial ...
1
vote
1answer
45 views
Probability of higher occurrence of an element within a random permutation with repetition
I generate $n$ random numbers, each one from a set $X={1,\ldots,N}$, where $n\geq N$. This results in a random permutation with repetition of length $n$ over $X$. Ideally for me, each number of $X$ ...
0
votes
0answers
29 views
Enumerating the number of subsets of size i that sum to a specific value
Suppose we are given an integer $n$ and an integer $i$ where $i \le n$. We want to find all the subsets of {1, 2, 3 ... n-1} of size $i$ that will sum to $kn$ where $k$ is a positive integer.
Edit: ...
0
votes
1answer
19 views
Divide objects into parts
I want to divide x distinct objects in some specified groups..
Lets say 3 groups of a,b,c number of
I am able to find when objects are similar but not in this case.
-2
votes
1answer
750 views
How many permutations of $N$ number that sum of every two adjacent is at most $M$
Moderator Note: This is a current contest question on codechef.com.
Given two integers $N$ and $M$, find how many permutations of $1, 2, \dots, N$ (first $N$ natural numbers) there are where the ...
0
votes
0answers
26 views
Need to figure out the logic/algorithm of this question. [duplicate]
Given two integers N and M, find how many permutations of 1, 2, ..., N (first N natural numbers) are there where the sum of every two adjacent numbers is at most M.
Examples :
4 5
answer = 4
5 8
...
0
votes
0answers
35 views
Counting Permutations [duplicate]
I have 1 Permutation of $N$ numbers i.e. $1,2,\ldots,N$. I have another integer $M$ which lies in range $(N,2N)$ . I want to find no. of permutations of $1\ldots N$ where sum of two adjacent numbers ...
2
votes
1answer
39 views
Number of circular placements of $n$ identical letters such that no two letters are adjacent.
Suppose I have to place $3$ identical letters on a circular table which has $7$ slots in such a way that no two letters are in consecutive slots. In how many ways can I do this?
Can this be ...
3
votes
2answers
81 views
How many solutions are there to $abc+def=ghi$, where $a,b,\ldots, h,i$ are distinct non-zero digits?
I saw this problem posted by Google. Those posting in the comments found solutions using computer programming. I would like to know if there is an easier solution than trying every single combination.
...
1
vote
4answers
51 views
The isomorphism from $S_3/\langle (123)\rangle$ to $\mathbb{Z}_2$.
Suppose that $N=\{(123), (132), \operatorname{e}\}$ and $N$ is normal in $S_3$. Show that the quotient group $S_3/N$ is isomorphic to $\mathbb{Z}_2$.
What mapping should I use?
1
vote
2answers
90 views
Permutation representation of group described by $a_i^2=\theta^2=1, a_ia_{i+1}=\theta a_{i+1}a_i=a_{i+2}$.
Let $G$ be a group with elements $\{e, a, b, c, \theta, \theta a, \theta b, \theta c \}$ where $a^2 = b^2 = c^2 = \theta$, $\theta^2 = e$, $ab = \theta b a = c$, $bc = \theta c b = a$, $ca = \theta a ...
6
votes
2answers
318 views
How many possible iPhone passwords?
A standard iPhone has $10$ digits (ranging from $0$ to $9$) Consider a user who has oily fingers (which is normal for an average user) and he unlocks the iPhone by pressing the numbers on the number ...
0
votes
1answer
49 views
Interpreting vaguely written questions [closed]
There are stalls for 10 animals. In how many ways can the shipload be made, if there cows,calves and horses to be transported, animals of each kind being not less than 10?
Does this question even ...
1
vote
1answer
39 views
Permutations and Combinations reference request
I have an exam on Wednesday on Permuations and Combinations and while I understand most of the concepts, I find it difficult to apply it to the questions because I haven't done many practice ...
1
vote
2answers
54 views
What is the smallest alphanumeric string that has 10 million permutations?
I'm aiming to create UUIDs, for a project I'm working on.
The standard UUID generators create a very long strings. I'm only anticipating a maximum of 10 million uses and because I'm storing that many ...
0
votes
1answer
36 views
Number of rules in my fuzzy logic
I have 6 variables with 4 membership functions such as "tiny,small,large,huge".
I tried to write the rules and came up with 200 rules but the combinations are killing me and it is still incomplete.
...
2
votes
3answers
51 views
Number of ways to distribute 5 distinguishable balls between 3 kids such that each of them gets at least one ball
How many ways are there to distribute 5 distinguishable balls between 3 kids such that each of them gets at least one ball?
My approach is $ \binom{5}{3} 3! $ + $ \binom{2}{2} \binom{3}{2}2!$ ...
0
votes
5answers
31 views
Permutation order proof question
I dont understand the following very simple statement:
If $\tau \in S_n$ has order $m$, then $\sigma \tau\sigma^{-1}$ has also order $m$.
The proof is:
Suppose $\tau$ has order $m$.
$(\sigma \tau ...
1
vote
3answers
32 views
Need help with combinatorics question(probably cyclical permutation)
A human invites 6 of his friends to a meeting. In how many different arrangements they along with the human's wife can sit at a round table if the hosts and the wife always sit together?
Is this a ...
5
votes
0answers
44 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 ...
0
votes
1answer
23 views
Arranging marbles in a row
Samson has $5$ identical blue marbles, $11$ identical white marbles and $4$ identical red
marbles which he wants to arrange randomly in a row.
What is the probability that:
every red marble will ...
0
votes
1answer
37 views
linear arrangements in a row
there are 7 teams A,B,C,D,E,F, each with 5 members. In how many ways can the 35 people be made to sit in a row such that every F team member sits next to
i) at least one team G member 2^5*5!*30! (ANS ...
4
votes
0answers
106 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]$ ...
0
votes
2answers
33 views
the product of a matrix and a permutation matrix
Can a permutation matrix ($P$) be used to change the rank of another matrix ($M$)?
Is there any literature to this effect, or to the contrary?
I've tried a few small examples and the resulting matrix ...
1
vote
2answers
26 views
How to determine the parity of a permutation by its cycle decomposition
If one is given the length of a permutation and the number of cycles, is it possible to determine the parity of the permutation?
Oddly enough, there's no definition in the text I'm reading for ...
1
vote
5answers
37 views
finding overlapping permutations
I have a data set $3\; 4\; 5\; 6\; 7\; 8\; 9$
I want to find all the permutations that can be formed using this such that neither $7$ nor $8$ is adjacent to $9$.
0
votes
2answers
38 views
The symmetric group $S_4$ and cycles as product of permutations
i have a question, i think it is very easy but i didn't see it: I know that:
$$S_4=\langle(1~~2),(2~~3),(3~~4)\rangle$$
Now i want to write $(1~~2~~3)$ and $(1~~2~~3~~4)$ as products of them. ...
2
votes
0answers
78 views
distributing z different objects among k people almost evenly
This is part of an ongoing contest. I have locked this question and deleted the answers. Both actions will be reversed eventually. I'm sorry for the inconvenience. - Michael Greinecker
We have ...
3
votes
3answers
52 views
probablity of selecting balls
If i have three pots with balls in them as follow.
1st: 2 red 4 black
2nd: 2 red 12 black
3rd: 2 red 4 black
what is the chance of getting exactly 2 black ...
-4
votes
0answers
84 views
In how many ways/permutations can the students form the queue
Post Notice:
This is a question from the current codechef competition. Please do not ask ongoing contest questions here to try to gain a competitive advantage. This question will be locked until ...
1
vote
1answer
58 views
arrangement of objects in circle (circular permutation)
I know circular arrangement of $n$ different objects can be done is $(n-1)!$ ways.
For example :-
I arranged $7$ objects in circle
This can be done in $720$ ways (using $6!$)
$1$) Can I also do ...
1
vote
3answers
418 views
What is the proof of permutations of similar objects?
What is the proof of permutations of similar objects? I know the formula, but I cannot figure out how to derive it!
permutations of similar objects
The number of permutations of $n=n_1+n_2+\dots+n_r$ ...
0
votes
0answers
98 views
Permuting natural numbers [duplicate]
We have three integers $z, k$ and $p$.
we form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, \ldots z$.
Now we have to find total number of permutations of this sequence such that the ...
0
votes
1answer
56 views
How many selection ways are possible?
There are 6 girls and 5 boys. You need to make a team of 4 persons. In how many ways can you form this team?
One way is to select 0,1,2,3,4 girls in team, but this is a very lengthy process. Is there ...
1
vote
0answers
52 views
balls and bins problem: how to calculate the number of arrangements corresponding to a specific ball sequence before all bins are overflowed?
Considering throwing balls into $k$ bins where each bin can hold $m$ balls at most. Every time a ball is thrown into a bin and we get "$0$" if the bin is not overflowed; Otherwise, we get "$1$". This ...
4
votes
2answers
191 views
Nearest matrix in doubly stochastic matrix set
Suppose $\mathcal{D}_N$ denote an $N\times N$ doubly stochastic matrix, given any element $M\in \mathcal{D}_N$ , the singular value decomposition for $M$ is $$ M=USV'$$
where $U$ and $V$ are two ...
0
votes
0answers
191 views
Finding summation up to $10^{18}$ [closed]
In this problem, both $n$ and $k$ are given values, with $n \leq 10^{18}$.
A number is good if any of the two conditions holds true:
a) number of digits $\le k$
b) sum of first $k$ digits is equal ...
2
votes
2answers
48 views
The probability of data loss
There are 300 files, each of which has 3 copies. Evenly and (by some mechanism)randomly distribute all the 900 files into 10 hard drives such that no drive will contain both a file and its copy. Now 3 ...
4
votes
5answers
85 views
Confused about the group of permutations $S_{n}$
In an exercise, I must prove $S_{n}$ is generated by 2 elements. I'll ignore here the trivial case $n = 1$. Let $I_{n} = \{1, 2, 3, ..., n\}$. I then defined $f : I_{n} \rightarrow I_{n}$ by $f(1) = ...
1
vote
0answers
28 views
Finding k-d sum for all numbers upto maxVal [duplicate]
a number n is a k-d number if either of the following holds true:
a) number of digits <=k
b) sum of first k digits is equal ...
3
votes
3answers
86 views
Showing that a transitive abelian permutation group is necessarily regular
I am trying to show that a transitive, abelian permutation group acting on a set $X$ is necessarily regular, given this hint: 'Given $g \in G$, consider the set $X^g:=\{x \in X\,|\,gx=x\}$. Show that ...
1
vote
1answer
106 views
Primitivity implies transitivity?
I am noting a simple problem about a permutation group from "Permutation Group" By J.Dixon, its answer and my attempt to understand it in details:
Q: A primitive permutation group $G(≠1$) is ...
1
vote
2answers
51 views
Is there a formula in permutations and combinations if we are to find the sum of number of 1's in binary expansion of a number from 1 to n
We are given $N$. Suppose $f(x) =$ number of $1$'s in the binary expansion of $x$.
We have to calculate $f(1) +f(2) +f(3)+ \dots +f(N)$.
So is there a formula for this sum directly in terms of ...
1
vote
1answer
49 views
Whether solutions of a particular matrix equation are only the permutation matrices
Let $V \in R^{d \times d} $ be a real orthogonal matrix. Denote by $V \circ V$ the Hadamard product (elementwise product).
I wish to show that if $V \left(V \circ V \right)^T V$ is "close" to $V ...
