Question

一道排列组合数学问题

火车在跑，车上有10个人，前面有6个站。每个人都会在6个站的其中一个站下车，并且已知每个站至少有一个人下车。请问存在多少种下车的情况？给出详细解答过程，先挂20分，回答满意直接追加80分。
拜托各位，仔细想想再回答好不？要真这么简单我不会挂出来问的。回答前请参考下前面的回答，不要都一样随便给个答案，没这么简单，要有这么简单我也不问啦！
提高悬赏！等强人给解！真的没有人能解答了吗？
答案是16435440，给出个合理做法，我是用程序跑出来的！

Answer 1

这个问题的结论是6!S(10,6)=16435440.

其中S(n,k)表示第二类Stirling数，它的组合含义是：把n元集划分为k个非空子集，各子集间不计次序，所得的分法数为即为S(n.k).

在本题中，10个人相当于10元集，6个站相当于6个非空子集。注意到各站之间是有区别的，所以本题结论为6!S(10,6).

一般来说，S(n.k)没有闭形式的表达式，也就是说此题没法用很简便的形式表达。
计算机里常用递推式S(n,k)=S(n-1,k-1)+kS(n-1,k)及初值S(n,1)=S(k,k)=1来求S(n.k).
这个递推式的证明不难，而且比较有趣，下面说一下。

从n元集中取定一个元素A，如果A独占某一个集合，那问题变成剩下的n-1个数分成k-1个非空集合，此时有S(n-1,k-1)种分法。
如果A所在的集合还有其他元素，先不考虑A, 剩下的n-1个数分成个非空集合，有S(n-1,k)种分法；把A加入时，由k个不同位置可选择，故此时有有kS(n-1,k)种分法。
综上，S(n,k)=S(n-1,k-1)+kS(n-1,k).

另一种求S(n,k)的方式是利用容斥原理，用在本题中计算量可以接受。下面就以本题为例讲一下。

如果不考虑每站都有人下车的条件，每个人有6种选择，结论就是6^10.
这样显然算多了，至少有一站没人下的情况应刨去。先从6站里选出一站没人下，再让10个人从剩下五站中选，共C(6,1)*(5^10)种情形。初步的结论是6^10-C(6,1)*(5^10).
仔细分析一下，上面的过程由多刨掉了一些。比如第1,2站都没人下的情形，上面刨除时按第1站没人下刨了一次，又按第二站没人下刨了一次。应该补上C(6,2)*(4^10).

依此类推，由容斥原理，结论应为：
6^10-C(6,1)*(5^10)+C(6,2)*(4^10)-C(6,3)*(3^10)+C(6,4)*(2^10)-C(6,5)*(1^10) (*)
=60466176-58593750+15728640-1180980+15360-6
=16435440.

综上，此题用容斥原理好算些，可以兼顾计算的简单性和思想的通用性。

顺便一提，“pengp0918”网友的方法确实可行，算出的数也是对的（只是最后一步多加了个1）。但那种方法不具有思想上的通用性。若k较大，需讨论的情况太多，过于繁杂。而容斥原理的方法则不然，只要把10和6换成一般的n和k, 上面的(*)式仍然可以求出答案。

Answer 2

一步一步分析：
首先，每个站至少有一个人下车，那么第一站的可能为10，第二站的可能为9，依次类推，第六站的可能5，总共有：10*9*8*7*6*5种可能
这样，就满足了“每个站至少有一个人下车”的条件
然后，剩下的4个人，对于每个人来说，他下车的可能有6种，即在6个车站的任意一个站下，所以对于剩下的4个人，共有：6^4种可能
所以：下车可能有：10*9*8*7*6*5*6^4=195955200

希望我的分析能够帮助到你，望采纳，不懂请追问~(*^__^*) ~

追问

明显有重复！
人编号为0到9，按照你的说法。0～5号人分别安排到1-6站下车，然后6～9号人全部在6站下车。
下车情况就是1站0号人，2站1号人，3站2号人，4站3号人，5站4号人，6站5-9号人。
同样，0～4号人在前5站下，9号人在第6站下，然后5～8号人在第6站下。下车情况也是1站0号人，2站1号人，3站2号人，4站3号人，5站4号人，6站5-9号人。
这样两种情况实质是相同的下车方式，但是在你的计算中确当两种来算。

Answer 3

首先，6个站 每个站一个人 有 A6/10种；
接下来还有4个人 可以在6个车站随意一个下；
没个人有6种选择 总的6*6*6*6

A6/10*6*6*6*6=272160种

Answer 4

1 1 1 1 1 1 1 1 1 1
假设这是10个人，
我们可以先用“插板法”算出 10人走6个站下车，“人数”的方案
像这样
1|1|1|1|11|1111
表示先后各有1个，1个，1个，1个，2个，4个人从1~6号门下车
等于从9个空里插入5个板 板之间表示在一个门里下车的人
C(9,5) 这样子等于我们人是有序地下车的
所以我们可以再给车门排列一下，这样子，人的下车位置就任意了，而同一个门里下车的顺序又不会影响答案而重复
所以答案是
C（9，5）*A(6,6)=90720
楼上的楼上是不是平均分组的重复没有考虑到

追问

你忽略的人和人是不同的吧？你把所有人都当作相同的物体了，把人编号了0～9，如果板子插定了之后，人虽然下车的位置任意，但是人所在的车门已经固定，不同的人在不同的车门下车是不同的情况。。。。理解我的意思吗？
我想过你这个做法，但是考虑到这个问题时，我使用了先排列插板，但是这样的话，存在重复的情况，比如0|1|2|3|4|56789和0|1|2|3|4|78956是排列不同，但是插板后下车的情况又存在重复。

追答

我发现我做法有错 没有考虑（例如0和9在一个门下）的情况
不过不是0|1|2|3|4|56789和0|1|2|3|4|78956 排列不同， 我排列的是车门哦
有时候排列组合的题目也不是都有很方便的解的， 详细分析所有情况做出答案也是很必要的，高考或者竞赛的时候有时候你写出状态了，别人已经数出来了 同学您分类讨论的能正解么 我继续帮您想想。。

追问

我第二段不是针对你的方法的问题，是针对你的方法改进后依然存在的问题。
你的方法问题很明显，插板法的话，一起下车的人只能是相邻的人，不相邻的人不可能一起下车，比如0123456789，1和9绝对不可能在同一个站下车.所以你的方法计算的可能性会少！

追答

你说的没错，我不熟练了~ 刚学没多久

Answer 5

先每站都安排一个人下站，6个站10个人 就是A6/10，还有4个人，每站都有下的可能，就是6^4，结果就是A6/10 * 6^4