珍珠湾ART

标题: 10个人来聚餐 [打印本页]

作者: constant 时间: 2005-12-11 01:05
标题: 10个人来聚餐

难度：+++

脑坛有10个人。这10个人来聚餐和离开的顺序一共有多少种可能？几个人可以一起来，也可以一起走。也可以一人走的同时另一人来。

本贴由[constant]最后编辑于：2005-12-11 11:47:13

作者: QL 时间: 2005-12-11 06:07
标题: 回复：10个人来聚餐

Can a person come and go at the same time?

作者: constant 时间: 2005-12-11 19:48
标题: No. Everybody has to come in and eat something

No. Everybody has to come in and eat something

作者: QFT 时间: 2005-12-12 18:03
标题: 回复：10个人来聚餐

It is equivalent to arrange the following 20 symbols,

A1, A2, ..., A10

B1, B2, ..., B10

under some rules.

(1) they can occupy same position.

(2) B1 must behind A1, B2 hehind A2, and so on.

We can first ignore the 2nd reqirement, but use instead the condition that A1 and B1 cannot be in the same position, and so on. The result divided by 2^10 is what we need.

we have such recurrence relationship,

T(n+1, 2) = T(n, 2) * P(2,2)

T(n+1, 3) = T(n, 2) * 2*3 +T(n, 3) *P(3,2)

T(n+1, 4) = T(n, 2) *3*4 +T(n, 3) * 3*4 +T(n, 4) * P(4,2)

...

T(n+1, m) = T(n, m-2) *(m-1)*m +T(n, m-1) *(m-1) *m +T(n, m)*P(m, 2)

where T(n, m) denotes n pairs occupy m positions.

We can use matrix multiplication to present the above relations. A computer program will do the calculations.

I don't find a general expression for this problem.

作者: constant 时间: 2005-12-12 21:30
标题: 回复：回复：10个人来聚餐

应该是对的。我也只有递推解。最后算出来 T(10) = 1843200116875263613

欢迎光临珍珠湾ART (http://66.160.158.134/)