In how many
ways (order matters) can 14 heterosexual married
couples be seated in chairs numbered
consecutively 1 to 28 about a round
table in such a manner that there is
always one man between two women
and none of them is ever next to his
own wife?
There are 13! ways of arranging the wives counterclockwise from Mrs. A. However, we're supposed to consider the chair numbers as well, so there are 14! ways of arranging the ladies.
We need to know, for any given arrangement of the ladies, how many arrangements of the men are acceptable. The number may be unacceptably large actually to compute it by finding all the ways for 14 couples.
Clearly it is only possible for 3 or more couples. For 3 couples there is only 1 arrangement of the men for any given arrangement of the ladies: each man sits opposite his wife.
The program below computes all possible arrangements for the men for a given arrangement of the wives. Each man is numbered relative to the position of his wife.
clearvars
global nCouples menSrce menSeq ct
for nCouples=3:11
menSrce=1:nCouples;
menSeq=[]; ct=0;
addon(1)
disp([nCouples,ct])
end
function addon(psn)
global nCouples menSrce menSeq ct
for i=1:length(menSrce)
m=menSrce(i);
nxtpsn=psn+1;
if nxtpsn>nCouples
nxtpsn=1;
end
if m~=psn && m~=nxtpsn
savesource=menSrce;
saveseq=menSeq;
menSeq(end+1)=m;
menSrce(i)=[];
if psn==nCouples
ct=ct+1;
else
addon(psn+1);
end
menSeq=saveseq;
menSrce=savesource;
end
end
end
The results are
3 1
4 2
5 13
6 80
7 579
8 4738
9 43387
10 439792
11 4890741
This matches elements in sequence A000179 in the OEIS, where the value for 14 is 10927434464.
As mentioned, this is multiplied by the 14! positions that the women can be arranged in. The product comes out to 9.52635063771508 x 10^20, or 952,635,063,771,507,916,800.
Edited on January 4, 2025, 1:00 pm
|
|
Posted by Charlie
on 2025-01-04 12:59:42 |
computer solution
