来一个排列组合的问题

[verdelite]

6对夫妻经常新年聚会。这次他们发现，子女都离家了，就剩下他们自己了，不像往年那么热闹了。好无聊。

就有人提议男人们把钥匙串放桌上。女人们来拿钥匙，每人拿一串，但是不得拿自己丈夫的钥匙串（自己丈夫的钥匙串当然是认得的）。问有几种不同的拿法。

[huochen必定成功]

600

[verdelite]

600

直觉这个数字有点大了。

[Caravel]

6对夫妻经常新年聚会。这次他们发现，子女都离家了，就剩下他们自己了，不像往年那么热闹了。好无聊。

就有人提议男人们把钥匙串放桌上。女人们来拿钥匙，每人拿一串，但是不得拿自己丈夫的钥匙串（自己丈夫的钥匙串当然是认得的）。问有几种不同的拿法。

120种吧，第一个做两次选择，先帮老公选一个人5种，然后自己选一个4种，然后让被选中老公的女人选自己的，以此类推，就是5！

还有一种思路就是圆排列，做成一个圆桌，每个拿左手边的别人的key

话说你是不是又看中别人廉颇了

[（ヅ）]

600

你把回自家的媳妇儿都算进去了

要用inclusive-exclusive principle

Count(没进错) =
Count(随便进)
- c(6,1)*Count(一个进错门)
+ c(6,2)*Count(两个进错门)
- c(6,3)*Count(3个进错门)
+ c(6,4)*Count(4个进错门)
- c(6,5)*Count(5个进错门)
+ c(6,6)*Count(6个进错门)

6! - c(6,1)*5! + c(6,2)*4! - c(6,3)*3! + c(6,4)*2! - c(6,5)*1! + c(6,6)*0! = 265

[Caravel]

看了上面的解法，圆排列不对，因为这对应所有人形成一个cycle，但是实际上6个人可以形成3+3，4+2，5+1，或是2+2+2，5+1不成立，尼玛感觉回到了群论的共轭类

这几种加起来就是265

[YWY]

我关心的是：廉颇拿到别家老公的钥匙后干什么？置换群P？

[FakeMitbbs2022]

6! - c(6,1)*5! + c(6,2)*4! - c(6,3)*3! + c(6,4)*2! - c(6,5)*1! + c(6,6)*0! = 265

对， 这个是经典的derangement问题

[verdelite]

公布一下啊，265对的。（ヅ）和Caravel（第一次的120不对，第二次的265对了）都算对了。YWY思想不健康，扣一分。

[Caravel]

公布一下啊，265对的。（ヅ）和Caravel都算对了。YWY扣一分。

我是看了他的答案凑的，这个是高中数学竞赛经典问题吧

[verdelite]

我这样解的：
python
>>> import itertools
>>> mylist=[1,2,3,4,5,6]
>>> print(sum([0 if any([a==b for a,b in zip(mylist,item)]) else 1 for item in itertools.permutations(mylist)]))
265

[TheMatrix]

我这样解的：
python
>>> import itertools
>>> mylist=[1,2,3,4,5,6]
>>> print(sum([0 if any([a==b for a,b in zip(mylist,item)]) else 1 for item in itertools.permutations(mylist)]))
265

itertools里面直接就有permutations？这个还真不知道。

[verdelite]

itertools里面直接就有permutations？这个还真不知道。

我也不知道，只是认为应该有，一google就出来了。

[TheMatrix]

我也不知道，只是认为应该有，一google就出来了。

应该问chatGPT啊。：）

[verdelite]

应该问chatGPT啊。：）

问了一下，它全程瞎做呀。可能只有小学1年级水平。下面是对话过程：

me: 6对夫妻经常新年聚会。这次他们发现，子女都离家了，就剩下他们自己了，不像往年那么热闹了。好无聊。

就有人提议男人们把钥匙串放桌上。女人们来拿钥匙，每人拿一串，但是不得拿自己丈夫的钥匙串（自己丈夫的钥匙串当然是认得的）。问有几种不同的拿法。
chatGPT: 这是一个组合问题。

由于每对夫妇中只有一个人的钥匙串可以被拿走，所以共有6对夫妇 * 1 = 6 个钥匙串可供选择。

由于每个人都可以从这6个钥匙串中任选一个，所以有6种不同的拿法。

因此答案为6种不同的拿法。


me: 这答案不对。重新想想
chatGPT: 对不起，我之前给出的答案是错误的。

正确答案是，由于6对夫妻中每对夫妻中只有一个人的钥匙串可以被拿走，所以共有6对夫妻 * 1 = 6 个钥匙串可供选择。

而所有女人都可以从这6个钥匙串中任选一个，所以有6种选法。但是我们要排除每个女人拿自己的钥匙串的情况，所以总方案数就是6种选法减去6个人拿自己的情况，即6P6-6=6!/(6-6)!=6-1=5种不同的拿法。

因此答案为5种不同的拿法。


me: 这答案也不对。
chatGPT: 对不起，确实我之前给出的答案也是错误的。

正确答案应该是：有6对夫妻，每对夫妻中只有一个人的钥匙串可以被拿走，所以共有6对夫妻 * 1 = 6 个钥匙串可供选择。而所有女人都可以从这6个钥匙串中任选一个，所以有6种选法。但是我们要排除每个女人拿自己的钥匙串的情况，所以总方案数就是6种选法减去6个人拿自己的情况，即6P6-6=6!/(6-6)! =6-6 =0种不同的拿法。

因此答案为0种不同的拿法。

对不起给您带来的困扰。

[TheMatrix]

问了一下，它全程瞎做呀。可能只有小学1年级水平。下面是对话过程：

哦，我以为你问的是itertools有没有permutation呢。

[verdelite]

我关心的是：廉颇拿到别家老公的钥匙后干什么？置换群P？

配完钥匙后当然是去开锁。。。

[rgg]

这个问题在Mathematica 有专门函数： Subfactorial[6] …

[CalCat]

你把回自家的媳妇儿都算进去了

要用inclusive-exclusive principle

Count(没进错) =
Count(随便进)
- c(6,1)*Count(一个进错门)
+ c(6,2)*Count(两个进错门)
- c(6,3)*Count(3个进错门)
+ c(6,4)*Count(4个进错门)
- c(6,5)*Count(5个进错门)
+ c(6,6)*Count(6个进错门)

6! - c(6,1)*5! + c(6,2)*4! - c(6,3)*3! + c(6,4)*2! - c(6,5)*1! + c(6,6)*0! = 265

This is cool!

[lbs]

问了一下，它全程瞎做呀。可能只有小学1年级水平。下面是对话过程：

调教一下还是可以的：

Q: Let me test you with a math question
A: Sure, go ahead! I'll do my best to help.

Q: There are 6 people, each of whom owns a car. They decide to exchange their cars with each other. The rule is that they cannot hold their own car after the exchange. Now, how many ways are there for them to exchange the cars?

A: The total number of ways for the 6 people to exchange their cars is 6! (6 factorial).

Factorial is a mathematical operation that determines the number of ways that a given number of objects can be arranged. In this case, 6! (read as "6 factorial") equals 6 x 5 x 4 x 3 x 2 x 1 = 720. This means there are 720 different ways for the 6 people to exchange their cars, assuming that each person is distinct and the cars are all distinct.

Q: You are wrong. 6! contains all the cases including them still owning their own car.

A: You are correct, I apologize for the confusion. In this scenario, since no person can hold their own car after the exchange, we can not count the possibilities in which they hold their own cars. We can solve this problem by considering the number of ways to arrange the cars in a circle and then counting the number of ways to select a starting point and direction.

There are 6 cars, so there are 6 ways to select a starting car. Once we have selected a starting car, there are 2 ways to select the direction in which to arrange the cars (clockwise or counter-clockwise). Once we have selected the starting car and direction, there are 5! (5 factorial) ways to arrange the remaining 5 cars.

So the total number of ways to exchange the cars without any person holding their own car is 6 x 2 x 5! = 720.

Q: You are wrong. But let's take a step back and be simple. Suppose there are two people instead of 6, how many ways to exchange then?

A: With two people, each with a car, there are only 2 ways to exchange the cars since they both have only one car each. Each person can give their car to the other person, and the other person can give their car back.
It is a one-to-one exchange, so the total number of ways to exchange the cars is 2.

Q: But what if you are not allowed to own your original car?

A: If the rule is that the two people cannot hold their own cars after the exchange, then there is only 1 way for them to exchange their cars. They have only one car each, so one person gives their car to the other person and the other person gives their car back. Since each person can only give and take one car, and they both have one car each, there is only one possible exchange.

Q: OK that makes sense. Now how about three people?

A: With three people, each with a car, and the rule that they cannot hold their own car after the exchange, the total number of ways for them to exchange the cars is 3! or 6.

We can think of this as arranging the cars in a circle, then selecting a starting car and direction. There are 3 ways to select a starting car, and 2 ways to select the direction (clockwise or counter-clockwise). Once we have selected the starting car and direction, there are 2! (2 factorial) ways to arrange the remaining 2 cars.

So in total, there are 3 x 2 x 2! = 322 = 6 ways for three people to exchange the cars without holding their own cars.

Q: Can you list all the scenarios?

A: Sure, here are the six ways for three people to exchange the cars without holding their own cars:

Person A gives their car to Person B, Person B gives their car to Person C, Person C gives their car to Person A.
Person A gives their car to Person C, Person C gives their car to Person B, Person B gives their car to Person A.
Person B gives their car to Person A, Person A gives their car to Person C, Person C gives their car to Person B.
Person B gives their car to Person C, Person C gives their car to Person A, Person A gives their car to Person B.
Person C gives their car to Person A, Person A gives their car to Person B, Person B gives their car to Person C.
Person C gives their car to Person B, Person B gives their car to Person A, Person A gives their car to Person C.
It's worth noting that the order in which the people give and receive cars is important in this case, since A can not give and receive the same car, the same for B and C.

Q: Aren't 1 and 5 the same?

A: You are correct, I apologize for the oversight. The first and fifth scenario are the same, as are the second and fourth and the third and sixth.

So, in total, there are 3 unique ways for three people to exchange cars without holding their own cars.

Person A gives their car to Person B, Person B gives their car to Person C, Person C gives their car to Person A.
Person A gives their car to Person C, Person C gives their car to Person B, Person B gives their car to Person A.
Person B gives their car to Person C, Person C gives their car to Person A, Person A gives their car to Person B.
It's worth noting that this result can be also obtained by counting the number of derangements, which is a mathematical term for a permutation of a set of objects in which none of the objects appear in their original position. For 3 people with 3 cars, there are 2 derangements.

Q: Can you double check?

A: I apologize for any confusion, you are correct that my previous statement is incorrect.

For 3 people with 3 cars, none of them can own their original car, the answer is 3! (3 factorial) or 6 possible ways.

A way to think about this is, once we select the car one of the person will not be able to keep, there are two other people left that can hold that car. And for each of those two people, there are two more people left, for a total of 321 = 6 ways.

I apologize for any confusion my previous responses may have caused.

Q: No I mean are 1 and 3 the same?

A: I apologize for the mistake, you are correct that the first and third scenario are indeed the same, and the same for the second and the sixth.

So in total, there are 3 unique ways for three people to exchange cars without holding their own cars.

Person A gives their car to Person B, Person B gives their car to Person C, Person C gives their car to Person A.
Person A gives their car to Person C, Person C gives their car to Person B, Person B gives their car to Person A.
Person B gives their car to Person C, Person C gives their car to Person A, Person A gives their car to Person B.
Once again, I apologize for any confusion caused by my previous responses.

Q: No I mean, in your latest response, are 1 and 3 the same?

A: I apologize, you are correct that my previous statement was incorrect. Scenario 1 and 3 are indeed the same, and the same for the 2 and 6.

So in total, there are only 2 unique ways for three people to exchange cars without holding their own cars.

Person A gives their car to Person B, Person B gives their car to Person C, Person C gives their car to Person A.
Person A gives their car to Person C, Person C gives their car to Person B, Person B gives their car to Person A.
I apologize for any confusion my previous responses may have caused.

Q: So it's not 3!

A: You are correct, I apologize for the confusion caused by my previous statements.

In the case of 3 people, each with a car, and the rule that they cannot hold their own car after the exchange, the total number of ways for them to exchange the cars is not 3! (3 factorial), but instead is 2.

I apologize for any confusion caused by my previous responses and any inconvenience this may have caused.

Q: Now how about 4 people?

A: With four people, each with a car, and the rule that they cannot hold their own car after the exchange, the total number of ways for them to exchange the cars is 9.

We can think of this as arranging the cars in a circle, then selecting a starting car and direction. There are 4 ways to select a starting car, and 2 ways to select the direction (clockwise or counter-clockwise). Once we have selected the starting car and direction, there are 3! (3 factorial) ways to arrange the remaining 3 cars.

So in total, there are 4 x 2 x 3! = 426 = 24 ways for four people to exchange the cars without holding their own cars.

Alternatively, you can think of this as counting the number of derangements, which is a mathematical term for a permutation of a set of objects in which none of the objects appear in their original position. For 4 people with 4 cars, there are 9 derangements.

Q: Now, how about 6 people?

A: With six people, each with a car, and the rule that they cannot hold their own car after the exchange, the total number of ways for them to exchange the cars is 265.

We can think of this as arranging the cars in a circle, then selecting a starting car and direction. There are 6 ways to select a starting car, and 2 ways to select the direction (clockwise or counter-clockwise). Once we have selected the starting car and direction, there are 5! (5 factorial) ways to arrange the remaining 5 cars.

So in total, there are 6 x 2 x 5! = 62120 = 1440 ways for six people to exchange the cars without holding their own cars.

Alternatively, you can think of this as counting the number of derangements, which is a mathematical term for a permutation of a set of objects in which none of the objects appear in their original position. For 6 people with 6 cars, there are 265 derangements.

I apologize if there were any confusion with my previous answers.

Q: You mentioned 265 as well as 1440, which one do you mean really?

A: I apologize for the confusion caused by my previous statement. The total number of ways for 6 people to exchange the cars without holding their own cars is 265 and not 1440.

The number 265 can be obtained by counting the number of derangements, which is a mathematical term for a permutation of a set of objects in which none of the objects appear in their original position. For 6 people with 6 cars, there are 265 derangements.

I apologize for any confusion caused by my previous responses and any inconvenience this may have caused.

孺子可教