Mixing
7 dancers on a circle
Clash Royale CLAN TAG#URR8PPP
up vote
9
down vote
favorite
7 dancers are going to participate in a contest. They are initially placed in their positions basis the initial letter of their surname.
At the second part of the contest, they are given random positions around the circle, which are determined by a draw. What is the probability that none of the dancers are in their initial positions or their neighboring?
It seems very simple to me but obviously isn't. For each dancer, the probability is $frac47$ so for all 7 it is $frac4^77^7$ – very simplistic, no?
probability combinatorics
edited 2 hours ago
Parcly Taxel
36.8k137095
asked 3 hours ago
Tom Galle
1584
 |Â
show 4 more comments
up vote
9
down vote
favorite
7 dancers are going to participate in a contest. They are initially placed in their positions basis the initial letter of their surname.
At the second part of the contest, they are given random positions around the circle, which are determined by a draw. What is the probability that none of the dancers are in their initial positions or their neighboring?
It seems very simple to me but obviously isn't. For each dancer, the probability is $frac47$ so for all 7 it is $frac4^77^7$ – very simplistic, no?
probability combinatorics
edited 2 hours ago
Parcly Taxel
36.8k137095
asked 3 hours ago
Tom Galle
1584
Why $4/7$? I would have understood your intention if you had said $6/7$ (which still does not give the right answer, unless the random assignment allows several dancers in the same position)
– Hagen von Eitzen
3 hours ago
@HagenvonEitzen: I said 4/7 because if they are not allowed their initial position and the two neighboring, then, out of the 7 positions, they are only allowed in the 4, right?
– Tom Galle
3 hours ago
Are the positions of the circle absolute or are they determined relative to the other dancers? Otherwise, everyone could move at least two spaces away from their position, but the configuration could still be the same afterwards.
– Paul
3 hours ago
Be careful. If the first dancer moves to position 3, the second dancer has 5 slots from which to pick. So there are more cases than what you're thinking or you may have to think about the problem differently.
– Joel Pereira
3 hours ago
You can't just multiply the probabilities, because the events are not independent. Suppose that dancers $1,2,$ and $3$ are assigned to positions $4,5,$ and $6$ in the second round. Then the probability that dancer $5$ is assigned to an admissible position is $1.$
– saulspatz
3 hours ago
 |Â
show 4 more comments
up vote
9
down vote
favorite
up vote
9
down vote
favorite
7 dancers are going to participate in a contest. They are initially placed in their positions basis the initial letter of their surname.
At the second part of the contest, they are given random positions around the circle, which are determined by a draw. What is the probability that none of the dancers are in their initial positions or their neighboring?
It seems very simple to me but obviously isn't. For each dancer, the probability is $frac47$ so for all 7 it is $frac4^77^7$ – very simplistic, no?
probability combinatorics
edited 2 hours ago
Parcly Taxel
36.8k137095
asked 3 hours ago
Tom Galle
1584
7 dancers are going to participate in a contest. They are initially placed in their positions basis the initial letter of their surname.
At the second part of the contest, they are given random positions around the circle, which are determined by a draw. What is the probability that none of the dancers are in their initial positions or their neighboring?
It seems very simple to me but obviously isn't. For each dancer, the probability is $frac47$ so for all 7 it is $frac4^77^7$ – very simplistic, no?
probability combinatorics
probability combinatorics
edited 2 hours ago
Parcly Taxel
36.8k137095
asked 3 hours ago
Tom Galle
1584
edited 2 hours ago
Parcly Taxel
36.8k137095
asked 3 hours ago
Tom Galle
1584
edited 2 hours ago
Parcly Taxel
36.8k137095
edited 2 hours ago
Parcly Taxel
36.8k137095
edited 2 hours ago
Parcly Taxel
36.8k137095
36.8k137095
asked 3 hours ago
Tom Galle
1584
asked 3 hours ago
Tom Galle
1584
asked 3 hours ago
Tom Galle
1584
1584
Why $4/7$? I would have understood your intention if you had said $6/7$ (which still does not give the right answer, unless the random assignment allows several dancers in the same position)
– Hagen von Eitzen
3 hours ago
@HagenvonEitzen: I said 4/7 because if they are not allowed their initial position and the two neighboring, then, out of the 7 positions, they are only allowed in the 4, right?
– Tom Galle
3 hours ago
Are the positions of the circle absolute or are they determined relative to the other dancers? Otherwise, everyone could move at least two spaces away from their position, but the configuration could still be the same afterwards.
– Paul
3 hours ago
Be careful. If the first dancer moves to position 3, the second dancer has 5 slots from which to pick. So there are more cases than what you're thinking or you may have to think about the problem differently.
– Joel Pereira
3 hours ago
You can't just multiply the probabilities, because the events are not independent. Suppose that dancers $1,2,$ and $3$ are assigned to positions $4,5,$ and $6$ in the second round. Then the probability that dancer $5$ is assigned to an admissible position is $1.$
– saulspatz
3 hours ago
 |Â
show 4 more comments
Why $4/7$? I would have understood your intention if you had said $6/7$ (which still does not give the right answer, unless the random assignment allows several dancers in the same position)
– Hagen von Eitzen
3 hours ago
@HagenvonEitzen: I said 4/7 because if they are not allowed their initial position and the two neighboring, then, out of the 7 positions, they are only allowed in the 4, right?
– Tom Galle
3 hours ago
Are the positions of the circle absolute or are they determined relative to the other dancers? Otherwise, everyone could move at least two spaces away from their position, but the configuration could still be the same afterwards.
– Paul
3 hours ago
Be careful. If the first dancer moves to position 3, the second dancer has 5 slots from which to pick. So there are more cases than what you're thinking or you may have to think about the problem differently.
– Joel Pereira
3 hours ago
You can't just multiply the probabilities, because the events are not independent. Suppose that dancers $1,2,$ and $3$ are assigned to positions $4,5,$ and $6$ in the second round. Then the probability that dancer $5$ is assigned to an admissible position is $1.$
– saulspatz
3 hours ago
Why $4/7$? I would have understood your intention if you had said $6/7$ (which still does not give the right answer, unless the random assignment allows several dancers in the same position)
– Hagen von Eitzen
3 hours ago
Why $4/7$? I would have understood your intention if you had said $6/7$ (which still does not give the right answer, unless the random assignment allows several dancers in the same position)
– Hagen von Eitzen
3 hours ago
@HagenvonEitzen: I said 4/7 because if they are not allowed their initial position and the two neighboring, then, out of the 7 positions, they are only allowed in the 4, right?
– Tom Galle
3 hours ago
@HagenvonEitzen: I said 4/7 because if they are not allowed their initial position and the two neighboring, then, out of the 7 positions, they are only allowed in the 4, right?
– Tom Galle
3 hours ago
Are the positions of the circle absolute or are they determined relative to the other dancers? Otherwise, everyone could move at least two spaces away from their position, but the configuration could still be the same afterwards.
– Paul
3 hours ago
Are the positions of the circle absolute or are they determined relative to the other dancers? Otherwise, everyone could move at least two spaces away from their position, but the configuration could still be the same afterwards.
– Paul
3 hours ago
Be careful. If the first dancer moves to position 3, the second dancer has 5 slots from which to pick. So there are more cases than what you're thinking or you may have to think about the problem differently.
– Joel Pereira
3 hours ago
Be careful. If the first dancer moves to position 3, the second dancer has 5 slots from which to pick. So there are more cases than what you're thinking or you may have to think about the problem differently.
– Joel Pereira
3 hours ago
You can't just multiply the probabilities, because the events are not independent. Suppose that dancers $1,2,$ and $3$ are assigned to positions $4,5,$ and $6$ in the second round. Then the probability that dancer $5$ is assigned to an admissible position is $1.$
– saulspatz
3 hours ago
You can't just multiply the probabilities, because the events are not independent. Suppose that dancers $1,2,$ and $3$ are assigned to positions $4,5,$ and $6$ in the second round. Then the probability that dancer $5$ is assigned to an admissible position is $1.$
– saulspatz
3 hours ago
 |Â
show 4 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
I get $144.$ I did this by computing the permanent of an appropriate matrix. (See my answer here(Combinatorial Analysis - Specific problem) for an explanation of this method.
The matrix in question is a $7times7$ matrix with a $1$ in position $(i,j)$ is dancer $i$ is allowed to occupy position $j$ and zeros elsewhere.
I append the script, though I would not recommend using a python script to compute the permanent of a large matrix.
#perm01.py
'''
Compute the permanent of a 0-1 matrix
'''
import numpy as np
from math import factorial
def minor(M, i, j):
return np.delete(np.delete(M,i,axis=0), j, axis=1)
def perm(M):
size = M.shape[0]
colsums = sum(M)
rowsums = sum(M.transpose())
c = np.argmin(colsums)
r = np.argmin(rowsums)
answer = 0
if colsums[c] <= rowsums[r]:
if colsums[c] == size:
return factorial(size)
for k in range(size):
if M[k, c] == 1:
answer += perm(minor(M,k,c))
else:
for k in range(size):
if M[r, k] == 1:
answer += perm(minor(M,r,k))
return answer
if __name__=='__main__':
M = np.zeros((7,7), dtype=np.int)
for k in range(7):
M[k,k]=M[k,(k+1)%7]=M[k,(k-1)%7]=1
M = np.ones((7,7), dtype=int)-M
print(perm(M))
answered 1 hour ago
saulspatz
12.2k21326
add a comment |Â
up vote
1
down vote
The problem is asking for the number of permutations of $0,dots,6$ such that the difference between each element and its image is more than 1 (modulo 7), as a proportion of the total number of permutations. The permutations must have no fixed points, which means they can only have four types of cycle structures – $7, 5,2,4,3,2,2,3$ – and these give rise to eleven patterns for permuting the dancers around:
Except for the two starry 7-cycles, each pattern can be in any of 7 orientations. They can also have $2^n$ cycle directions, where $n$ is the number of cycles that are not transpositions, written in the top-left corner of each permutation in the picture. Thus we have $7(8cdot2+4)+2+2=144$ admissible permutations, and this is out of $7!=5040$, so the desired probability is $frac1445040=frac135$.
Permutations of this sort, where elements move more than one place around a circle, are termed discordant and enumerated (with links to a general enumeration system) under OEIS A000183.
answered 3 hours ago
Parcly Taxel
36.8k137095
@Parcly Taxel: Thank you very much for your solution. Could you possibly be a little more analytic? I don't quite understand the part with the patterns, modulo 7 etc.
– Tom Galle
2 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I get $144.$ I did this by computing the permanent of an appropriate matrix. (See my answer here(Combinatorial Analysis - Specific problem) for an explanation of this method.
The matrix in question is a $7times7$ matrix with a $1$ in position $(i,j)$ is dancer $i$ is allowed to occupy position $j$ and zeros elsewhere.
I append the script, though I would not recommend using a python script to compute the permanent of a large matrix.
#perm01.py
'''
Compute the permanent of a 0-1 matrix
'''
import numpy as np
from math import factorial
def minor(M, i, j):
return np.delete(np.delete(M,i,axis=0), j, axis=1)
def perm(M):
size = M.shape[0]
colsums = sum(M)
rowsums = sum(M.transpose())
c = np.argmin(colsums)
r = np.argmin(rowsums)
answer = 0
if colsums[c] <= rowsums[r]:
if colsums[c] == size:
return factorial(size)
for k in range(size):
if M[k, c] == 1:
answer += perm(minor(M,k,c))
else:
for k in range(size):
if M[r, k] == 1:
answer += perm(minor(M,r,k))
return answer
if __name__=='__main__':
M = np.zeros((7,7), dtype=np.int)
for k in range(7):
M[k,k]=M[k,(k+1)%7]=M[k,(k-1)%7]=1
M = np.ones((7,7), dtype=int)-M
print(perm(M))
answered 1 hour ago
saulspatz
12.2k21326
add a comment |Â
up vote
1
down vote
I get $144.$ I did this by computing the permanent of an appropriate matrix. (See my answer here(Combinatorial Analysis - Specific problem) for an explanation of this method.
The matrix in question is a $7times7$ matrix with a $1$ in position $(i,j)$ is dancer $i$ is allowed to occupy position $j$ and zeros elsewhere.
I append the script, though I would not recommend using a python script to compute the permanent of a large matrix.
#perm01.py
'''
Compute the permanent of a 0-1 matrix
'''
import numpy as np
from math import factorial
def minor(M, i, j):
return np.delete(np.delete(M,i,axis=0), j, axis=1)
def perm(M):
size = M.shape[0]
colsums = sum(M)
rowsums = sum(M.transpose())
c = np.argmin(colsums)
r = np.argmin(rowsums)
answer = 0
if colsums[c] <= rowsums[r]:
if colsums[c] == size:
return factorial(size)
for k in range(size):
if M[k, c] == 1:
answer += perm(minor(M,k,c))
else:
for k in range(size):
if M[r, k] == 1:
answer += perm(minor(M,r,k))
return answer
if __name__=='__main__':
M = np.zeros((7,7), dtype=np.int)
for k in range(7):
M[k,k]=M[k,(k+1)%7]=M[k,(k-1)%7]=1
M = np.ones((7,7), dtype=int)-M
print(perm(M))
answered 1 hour ago
saulspatz
12.2k21326
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I get $144.$ I did this by computing the permanent of an appropriate matrix. (See my answer here(Combinatorial Analysis - Specific problem) for an explanation of this method.
The matrix in question is a $7times7$ matrix with a $1$ in position $(i,j)$ is dancer $i$ is allowed to occupy position $j$ and zeros elsewhere.
I append the script, though I would not recommend using a python script to compute the permanent of a large matrix.
#perm01.py
'''
Compute the permanent of a 0-1 matrix
'''
import numpy as np
from math import factorial
def minor(M, i, j):
return np.delete(np.delete(M,i,axis=0), j, axis=1)
def perm(M):
size = M.shape[0]
colsums = sum(M)
rowsums = sum(M.transpose())
c = np.argmin(colsums)
r = np.argmin(rowsums)
answer = 0
if colsums[c] <= rowsums[r]:
if colsums[c] == size:
return factorial(size)
for k in range(size):
if M[k, c] == 1:
answer += perm(minor(M,k,c))
else:
for k in range(size):
if M[r, k] == 1:
answer += perm(minor(M,r,k))
return answer
if __name__=='__main__':
M = np.zeros((7,7), dtype=np.int)
for k in range(7):
M[k,k]=M[k,(k+1)%7]=M[k,(k-1)%7]=1
M = np.ones((7,7), dtype=int)-M
print(perm(M))
answered 1 hour ago
saulspatz
12.2k21326
I get $144.$ I did this by computing the permanent of an appropriate matrix. (See my answer here(Combinatorial Analysis - Specific problem) for an explanation of this method.
The matrix in question is a $7times7$ matrix with a $1$ in position $(i,j)$ is dancer $i$ is allowed to occupy position $j$ and zeros elsewhere.
I append the script, though I would not recommend using a python script to compute the permanent of a large matrix.
#perm01.py
'''
Compute the permanent of a 0-1 matrix
'''
import numpy as np
from math import factorial
def minor(M, i, j):
return np.delete(np.delete(M,i,axis=0), j, axis=1)
def perm(M):
size = M.shape[0]
colsums = sum(M)
rowsums = sum(M.transpose())
c = np.argmin(colsums)
r = np.argmin(rowsums)
answer = 0
if colsums[c] <= rowsums[r]:
if colsums[c] == size:
return factorial(size)
for k in range(size):
if M[k, c] == 1:
answer += perm(minor(M,k,c))
else:
for k in range(size):
if M[r, k] == 1:
answer += perm(minor(M,r,k))
return answer
if __name__=='__main__':
M = np.zeros((7,7), dtype=np.int)
for k in range(7):
M[k,k]=M[k,(k+1)%7]=M[k,(k-1)%7]=1
M = np.ones((7,7), dtype=int)-M
print(perm(M))
answered 1 hour ago
saulspatz
12.2k21326
answered 1 hour ago
saulspatz
12.2k21326
answered 1 hour ago
saulspatz
12.2k21326
answered 1 hour ago
saulspatz
12.2k21326
12.2k21326
add a comment |Â
add a comment |Â
up vote
1
down vote
The problem is asking for the number of permutations of $0,dots,6$ such that the difference between each element and its image is more than 1 (modulo 7), as a proportion of the total number of permutations. The permutations must have no fixed points, which means they can only have four types of cycle structures – $7, 5,2,4,3,2,2,3$ – and these give rise to eleven patterns for permuting the dancers around:
Except for the two starry 7-cycles, each pattern can be in any of 7 orientations. They can also have $2^n$ cycle directions, where $n$ is the number of cycles that are not transpositions, written in the top-left corner of each permutation in the picture. Thus we have $7(8cdot2+4)+2+2=144$ admissible permutations, and this is out of $7!=5040$, so the desired probability is $frac1445040=frac135$.
Permutations of this sort, where elements move more than one place around a circle, are termed discordant and enumerated (with links to a general enumeration system) under OEIS A000183.
answered 3 hours ago
Parcly Taxel
36.8k137095
@Parcly Taxel: Thank you very much for your solution. Could you possibly be a little more analytic? I don't quite understand the part with the patterns, modulo 7 etc.
– Tom Galle
2 hours ago
add a comment |Â
up vote
1
down vote
The problem is asking for the number of permutations of $0,dots,6$ such that the difference between each element and its image is more than 1 (modulo 7), as a proportion of the total number of permutations. The permutations must have no fixed points, which means they can only have four types of cycle structures – $7, 5,2,4,3,2,2,3$ – and these give rise to eleven patterns for permuting the dancers around:
Except for the two starry 7-cycles, each pattern can be in any of 7 orientations. They can also have $2^n$ cycle directions, where $n$ is the number of cycles that are not transpositions, written in the top-left corner of each permutation in the picture. Thus we have $7(8cdot2+4)+2+2=144$ admissible permutations, and this is out of $7!=5040$, so the desired probability is $frac1445040=frac135$.
Permutations of this sort, where elements move more than one place around a circle, are termed discordant and enumerated (with links to a general enumeration system) under OEIS A000183.
answered 3 hours ago
Parcly Taxel
36.8k137095
@Parcly Taxel: Thank you very much for your solution. Could you possibly be a little more analytic? I don't quite understand the part with the patterns, modulo 7 etc.
– Tom Galle
2 hours ago
add a comment |Â
up vote
1
down vote
up vote
1
down vote
The problem is asking for the number of permutations of $0,dots,6$ such that the difference between each element and its image is more than 1 (modulo 7), as a proportion of the total number of permutations. The permutations must have no fixed points, which means they can only have four types of cycle structures – $7, 5,2,4,3,2,2,3$ – and these give rise to eleven patterns for permuting the dancers around:
Except for the two starry 7-cycles, each pattern can be in any of 7 orientations. They can also have $2^n$ cycle directions, where $n$ is the number of cycles that are not transpositions, written in the top-left corner of each permutation in the picture. Thus we have $7(8cdot2+4)+2+2=144$ admissible permutations, and this is out of $7!=5040$, so the desired probability is $frac1445040=frac135$.
Permutations of this sort, where elements move more than one place around a circle, are termed discordant and enumerated (with links to a general enumeration system) under OEIS A000183.
answered 3 hours ago
Parcly Taxel
36.8k137095
The problem is asking for the number of permutations of $0,dots,6$ such that the difference between each element and its image is more than 1 (modulo 7), as a proportion of the total number of permutations. The permutations must have no fixed points, which means they can only have four types of cycle structures – $7, 5,2,4,3,2,2,3$ – and these give rise to eleven patterns for permuting the dancers around:
Except for the two starry 7-cycles, each pattern can be in any of 7 orientations. They can also have $2^n$ cycle directions, where $n$ is the number of cycles that are not transpositions, written in the top-left corner of each permutation in the picture. Thus we have $7(8cdot2+4)+2+2=144$ admissible permutations, and this is out of $7!=5040$, so the desired probability is $frac1445040=frac135$.
Permutations of this sort, where elements move more than one place around a circle, are termed discordant and enumerated (with links to a general enumeration system) under OEIS A000183.
answered 3 hours ago
Parcly Taxel
36.8k137095
edited 43 mins ago
answered 3 hours ago
Parcly Taxel
36.8k137095
answered 3 hours ago
Parcly Taxel
36.8k137095
answered 3 hours ago
Parcly Taxel
36.8k137095
36.8k137095
@Parcly Taxel: Thank you very much for your solution. Could you possibly be a little more analytic? I don't quite understand the part with the patterns, modulo 7 etc.
– Tom Galle
2 hours ago
add a comment |Â
@Parcly Taxel: Thank you very much for your solution. Could you possibly be a little more analytic? I don't quite understand the part with the patterns, modulo 7 etc.
– Tom Galle
2 hours ago
@Parcly Taxel: Thank you very much for your solution. Could you possibly be a little more analytic? I don't quite understand the part with the patterns, modulo 7 etc.
– Tom Galle
2 hours ago
@Parcly Taxel: Thank you very much for your solution. Could you possibly be a little more analytic? I don't quite understand the part with the patterns, modulo 7 etc.
– Tom Galle
2 hours ago
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2963575%2f7-dancers-on-a-circle%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Why $4/7$? I would have understood your intention if you had said $6/7$ (which still does not give the right answer, unless the random assignment allows several dancers in the same position)
– Hagen von Eitzen
3 hours ago
@HagenvonEitzen: I said 4/7 because if they are not allowed their initial position and the two neighboring, then, out of the 7 positions, they are only allowed in the 4, right?
– Tom Galle
3 hours ago
Are the positions of the circle absolute or are they determined relative to the other dancers? Otherwise, everyone could move at least two spaces away from their position, but the configuration could still be the same afterwards.
– Paul
3 hours ago
Be careful. If the first dancer moves to position 3, the second dancer has 5 slots from which to pick. So there are more cases than what you're thinking or you may have to think about the problem differently.
– Joel Pereira
3 hours ago
You can't just multiply the probabilities, because the events are not independent. Suppose that dancers $1,2,$ and $3$ are assigned to positions $4,5,$ and $6$ in the second round. Then the probability that dancer $5$ is assigned to an admissible position is $1.$
– saulspatz
3 hours ago