Among them, S(n, k) stands for the second kind of Stirling number, which means that the N-tuple set is divided into k non-empty subsets, and the subsets are out of order, so the division number is S(n.k).
This topic 10 person is equivalent to 10 yuan set, and 6 stations are equivalent to non-empty sets. Note that there are differences between stations, so the conclusion of this question is 6! S( 10,6)。
Generally speaking, S (N.K) has no closed form expression, which means that this problem cannot be expressed in a very simple form.
The recurrence formula s (n, k) = s (n- 1, k- 1)+ks (n- 1, k) initial value s (n, 1) = s (k, k) = 65438.
The proof of this recursive formula is not difficult and interesting. Let's talk about it below.
Take an element A from the set of n elements. If A monopolizes a set, the problem becomes to divide the remaining n- 1 number into k- 1 nonempty sets, and there is a division of S(n- 1, k- 1).
If there are other elements in the set in which A belongs, the remainder of n- 1 is divided into a non-empty set classified by S(n- 1, k). When adding a, there are k different positions to choose from, so there is the classification method of kS(n- 1, k).
To sum up, s (n, k) = s (n- 1, k- 1)+ks (n- 1, k).
Another way to find S(n, k) is to use the exclusion principle, and the amount of calculation used in this problem is acceptable. Let's take this problem as an example.
Without considering the condition of getting off at each stop, everyone has six choices, and the conclusion is 6 10.
This is obviously too much, and at least one stop must be left unattended. First, one of the six stops is empty, and then let 10 people choose from the remaining five stops, * * * c(6 1)*(5 10). The preliminary conclusion is 610-c (61) * (510).
After careful analysis, the above process was shaved off a little. For example, when no one gets off at 1 and 2 stops, no one gets off at 1 stop once and no one gets off at the second stop once when planing above. C (6 6,2) * (410) should be added.
By analogy, according to the principle of inclusion and exclusion, the conclusion should be:
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)(*)
=60466 176-58593750+ 15728640- 1 180980+ 15360-6
= 16435440.
To sum up, this problem is easier to calculate with the principle of inclusion and exclusion, which can give consideration to the simplicity of calculation and the universality of thought.
By the way, the method of "pengp09 18" is indeed feasible, and the calculated figures are correct (only 1 was added in the previous step). But this method is not universal in thought. If k is big, there are too many and complicated situations to discuss. However, the method of including and excluding principles is not like this. As long as 10 and 6 are replaced by ordinary n and k, the above formula (*) can still find the answer.