java - Arrangements of sets of k positions in a n-competitors race -

this copy of post on mathexchange.com.

let e(n) set of possible ending arrangements of race of n competitors.

obviously, because it's race, each 1 of n competitors wants win. hence, order of arrangements does matter. let if 2 competitors end same result of time, win same spot.

for example, e(3) contains following sets of arrangements:

{(1,1,1), (1,1,2), (1,2,1), (1,2,2), (1,2,3), (1,3,2), (2,1,1), (2,1,2),(2,1,3), (2,2,1), (2,3,1), (3,1,2), (3,2,1)}.

needless say, example, arrangement (1,3,3) invalid, because 2 competitors supposedly ended in third place, actually ended in second place. above arrangement "transfers" (1,2,2).

define k number of distinct positions of competitors in subset of e(n). have example:

(1,1,1) -------> k = 1

(1,2,1) -------> k = 2

(1,2,3,2) -------> k = 3

(1,2,1,5,4,4,3) -------> k = 5

finally, let m(n,k) number of subsets of e(n) in competitors ended in exactly k distinct positions.

we get, example,m(3,3) = m(3,2) = 6 , m(3,1) = 1.

------------------------------------------------------------------------------------------- 

thus far question

it's problem came solely myself. after time of thought came following recursive formula |e(n)|: (don't continue reading if want derive formula yourself!)

|e(n)| = sum l=1 n of c(n,l)*|e(n-l)| where |e(0)| = 1

and code in java function, using biginteger class:

public static biginteger e (int n) {     if (!ens[n].equals(biginteger.zero))         return ens[n];     else     {         biginteger ends=biginteger.zero;         (int l=1;l<=n;l++)             ends=ends.add(factorials[n].divide(factorials[l].multiply(factorials[n-l])).multiply(e(n-l)));         ens[n]=ends;         return ends;     } } 

the factorials array array of precalculated factorials faster binomial coefficients calculations.

the ens array array of memoized/cached e(n) values quickens calculating, due need of repeatedly calculating e(n) values.

the logic behind recurrence relation l symbolizes how many "first" spots have. each l, binomial coefficient c(n,l) symbolizes in how many ways can pick l first-placers out of n competitors. once have chosen them, need figure out in how many ways can arrange n-l competitors have left, |e(n-l)|. following:

|e(3)| = 13

|e(5)| = 541

|e(10)| = 102247563

|e(100)| mod 1 000 000 007 = 619182829 -------> 20 ms.

and |e(1000)| mod 1 000 000 007 = 581423957 -------> 39 sec.

i figured out |e(n)| can visualized number of sets following applies:

for every i = 1, 2, 3 ... n, every i-tuple subset of original set has gcd (greatest common divisor) of of elements equal 1. i'm not 100% sure because not able compute approach large n. however, precalculating factorials , memoizing e(n)'s, calculating times higher n's grow fast. capable of verifying above formula , values? can derive better, faster formula? perhaps generating functions?

as m(n,k).. i'm totally clueless. absolutely have no idea how calculate it, , therefore couldn't post meaningful data points. perhaps it's p(n,k) = n!/(n-k)!. can figure out formula m(n,k)?

i have no idea function harder compute, either e(n) or m(n,k), helping me either of them appreciable.

i want solutions generic work efficiently large n's. exhaustive search not i'm looking for, unfortunately. looking solutions based purely on combinatorial approach , efficient formulas.

i hope clear enough wording , ask throughout post. way, can program using java. know mathematica pretty decently :) .

thanks lot in advance,

matan.

e(n) fubini numbers. m(n, k) = s(n, k) * k!, s(n, k) stirling number of second kind, because s(n, k) number of different placing partitions, , k! number of ways rank them.