2
$\begingroup$

Let $E(n)$ be the set of all possible ending arrangements of a race of $n$ competitors.

Obviously, because it's a race, each one of the $n$ competitors wants to win. Hence, the order of the arrangements does matter. Let us also say that if two competitors end with the same result of time, they win the same spot.

For example, $E(3)$ contains the 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 to say, for example, that the arrangement $(1,3,3)$ is invalid, because the two competitors that supposedly ended in the third place, actually ended in the second place. So the above arrangement "transfers" to $(1,2,2)$.

Define $k$ to be the number of distinct positions of the competitors in a subset of $E(n)$. We have for example:

$(1,1,1)\Rightarrow k = 1$

$(1,2,1)\Rightarrow k = 2$

$(1,2,3,2)\Rightarrow k = 3$

$(1,2,1,5,4,4,3)\Rightarrow k = 5$

Finally, let $M(n,k)$ be the number of subsets of $E(n)$ in which the competitors ended in exactly $k$ distinct positions.

We get, for example, $M(3,3) = M(3,2) = 6$ and $M(3,1) = 1$.

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

Thus far is the question

It's a problem I came up with solely by myself. After some time of thought I came up with the following recursive formula for $|E(n)|$: (Don't continue reading if you want to derive a formula yourself!)

$$|E(n)| = \sum_{l=1}^n\binom{n}{l}\cdot |E(n-l)| \quad\text{where}\quad |E(0)| = 1$$

The logic behind this recurrence relation is that $l$ symbolizes how many "first" spots we have. For each $l$, the binomial coefficient $\binom{n}{l}$ symbolizes in how many ways we can pick $l$ first-placers out of the $n$ competitors. Once we have chosen them, we to need to figure out in how many ways we can arrange the $n-l$ competitors we have left, which is just $|E(n-l)|$. I get the following:

$|E(3)| = 13$

$|E(5)| = 541$

$|E(10)| = 102247563$

$|E(100)|$ mod $1$ $000$ $000$ $007 = 619182829$ $\rightarrow$ 20 ms.

And $|E(1000)|$ mod $1$ $000$ $000$ $007 = 581423957$ $\rightarrow$ 39 sec.

I figured out that $|E(n)|$ can also be visualized as the number of sets to which the following applies:

For every $i = 1, 2, 3 ... n$, every $i$-tuple subset of the original set has GCD (greatest common divisor) of all of its elements equal to 1. But I'm not 100% sure about this because I was not able to compute this approach for large $n$. However, even with precalculating factorials and memoizing the $E(n)$'s, the calculating times for higher $n$'s grow very fast. Is anyone capable of verifying the above formula and values? Can anyone derive a better, faster formula? Perhaps with generating functions?

As for $M(n,k)$.. I'm totally clueless. I absolutely have no idea how to calculate it, and therefore I couldn't post any meaningful data points. Perhaps it's $P(n,k) = \frac{n!}{(n-k)!}$. Can anyone figure out a formula for $M(n,k)$?

I have no idea which function is harder to compute, either $E(n)$ or $M(n,k)$, but helping me with either of them will be very much appreciable.

I want the solutions to be generic as well as work efficiently even for large $n$'s. Exhaustive search is not what I'm looking for, unfortunately. What I am looking for is solutions based purely on combinatorial approach and efficient formulas.

I hope I was clear enough with the wording and what I ask for throughout my post. By the way, I can program using Java. I also know Mathematica pretty decently :) .

Thanks a lot in advance,

Matan.

$\endgroup$
2
$\begingroup$

The numbers $|E_n|$ are the Fubini (or ordered Bell) numbers, OEIS A000670. The OEIS entry has numerous alternative descriptions and references. Among the formulas are

$$|E_n|=\sum_{k=1}^nk!{n\brace k}=\sum_{k\ge 1}\frac{(k-1)^n}{2^k}$$

and your recurrence

$$|E_n|=\sum_{k=1}^n\binom{n}k|E_{n-k}|$$

with initial condition $|E_0|=1$. It’s also noted that $|E_n|$ is asymptotic to $\dfrac{n!}2(\log_2e)^{n+1}$. This is approximately $12.99629$ for $n=3$, $541.00152$ for $n=5$, and $102,247,563.0053$ for $n=10$; the corresponding values of $|E_n|$ are $13$, $541$, and $102,247,563$, so it appears to be a very good approximation.

There is a nice exponential generating function,

$$g(x)=\frac1{2-e^x}\;.$$

$M(n,k)$ is the number of surjections from $[n]$ to $[k]$. You can find a recurrence for it in this question and its answers. My answer to this question sketches the argument that

$$M(n,k)=\sum_{j\ge 0}\binom{k}jj^n(-1)^{k-j}=k!{n\brace k}\;.$$

($n\brace k$ is a Stirling number of the second kind.)

$\endgroup$
  • $\begingroup$ Amazing. Simply amazing.. I have no idea how did you know all of this. How did you? Wow.. I am absolutely amazed. My honest appreciation and admiration to you sir. I wish I will sometime be as smart. @Brian $\endgroup$ – Matan May 14 '15 at 22:43
  • $\begingroup$ @Matan: Partly experience, and partly knowing where to look for more information – which also comes from experience. Glad to help! $\endgroup$ – Brian M. Scott May 14 '15 at 22:51
  • $\begingroup$ Hey I just tried the formula u gave: $\sum_{k\ge 1}\frac{(k-1)^n}{2^k}$ But it doesn't give me the correct results. Maybe I didn't understand it properly.. But can you check it again or explain? I used the sum from k=1 to k=n. @Brian $\endgroup$ – Matan May 14 '15 at 23:05
  • $\begingroup$ @Matan: I simply quoted it, so I’m taking it on faith. Note that it’s an infinite series. I just evaluated the partial sum up to $k=13$ for $n=3$ and got about $12.6538$, so I can believe that it converges to the correct $13$. To use it in any practical way, though, you’d have to work out how many terms you have to include to get within $1$, say, of the correct value. $\endgroup$ – Brian M. Scott May 14 '15 at 23:12
  • 1
    $\begingroup$ @Matan: You’re welcome. If I have some time later, I’ll see if I can come up with an estimate for how many terms are needed. $\endgroup$ – Brian M. Scott May 14 '15 at 23:15
1
$\begingroup$

For convenience, let $[n] = \{1, 2, 3, \ldots, n\}$

Then M(n,k) is the number of onto functions $f:[n]\to[k]$.

I think that's

$\binom k k k^n - \binom{k}{k-1}(k-1)^n + \binom{k}{k-2}(k-2)^n + \cdots \pm \binom{k}{1}1^n$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.