Orders of Finish (Posted on 2008-01-12)

	Submitted by Charlie
No Rating
Solution:	(Hide)
For any given way of n contestants to arrive in i groups, there are i ways of n+1 contestants arriving in i groups, as the additional contestant can be added to any of the i groups. But also, there are also i ways that i-1 groups from n contestants can become i groups if the (n+1)th person comes in alone, to form a group of one member. So the number of ways of n contestants coming in in i groups equals i times the number of ways n-1 contestants can come in i-1 ways plus i times the number of ways n-1 contestants can come in i ways. i:1 2 3 4 5 6 7 8 9 10 total n 2| 1 2 | 3 3| 1 6 6 | 13 4| 1 14 36 24 | 75 5| 1 30 150 240 120 | 541 6| 1 62 540 1560 1800 720 | 4683 7| 1 126 1806 8400 16800 15120 5040 | 47293 8| 1 254 5796 40824 126000 191520 141120 40320 | 545835 9| 1 510 18150 186480 834120 1905120 2328480 1451520 362880 | 7087261 10| 1 1022 55980 818520 5103000 16435440 29635200 30240000 16329600 3628800|102247563 For example the 1560 for n=6, i=4 is 4*(150+240) from the preceding line. So the total possible orders of arrival for 10 contestants is 102,247,563

	Subject	Author	Date
	answer	K Sengupta	2008-02-26 05:38:03
	re(2): simple computation algorithm	Daniel	2008-01-14 01:56:33
	Formula for the general case	FrankM	2008-01-13 23:58:49
	re: simple computation algorithm	Steve Herman	2008-01-13 14:29:36
	simple computation algorithm	Daniel	2008-01-13 09:53:07
	researched answer	Dennis	2008-01-12 12:41:10