10个人来聚餐

constant · 发表于 2005-12-11 01:05:17

难度：+++

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

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

QL · 发表于 2005-12-11 06:07:45

Can a person come and go at the same time?

constant · 发表于 2005-12-11 19:48:10

No. Everybody has to come in and eat something

QFT · 发表于 2005-12-12 18:03:58

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:42

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

		自动登录	找回密码
密码			立即注册

动态微博

10个人来聚餐

回复：10个人来聚餐

No. Everybody has to come in and eat something

回复：10个人来聚餐

回复：回复：10个人来聚餐