0

I have a set of $m$ points $(p_1,p_2,\ldots,p_m)$, that are to be taken two at a time as one of the edges of a triangle. It is given that consecutive edges are formed by $p_1 - p_2$ and $p_2-p_3$, etc - the points can be visualized to be on a line, one after the other. Also, I have another set of $n$ points $(q_1,\ldots,q_n)$, that I want to use as the third vertex of the triangle. These points can be assumed to be on a line as well. Essentially, I want to find out the number of triangles that I can draw, without any intersections - so I could have $p_1p_2q_1, p_2p_3q_1, p_3p_4q_2, p_4p_5q_3$ and so on, as the triangles if you get the drift.

I think my formulation of this as a question of assigning a label to $m$ ordered items, from $n$ labels, so that any later item doesn't get a lower label should give the correct answer, but I'm having a hard time solving it using my elementary knowledge of combinatorics.

Aside from an answer , any pointer to the relevant maths that I'd need to pick up to solve such questions would also be much appreciated.

Johannes Kloos
  • 9,091
indivisibleatom
  • 60

1 Answers1

1

It appears that you want to count the non-decreasing functions from $[m]=\{1,\ldots,m\}$ to $[n]$. Suppose that $f:[m]\to[n]$ is non-decreasing. For each $k\in[n]$ let $$D_f(k)=\{i\in[m]:f(i)=k\}\;;$$ $D_f(k)$ may be empty, but if it’s non-empty, it’s a set of consecutive integers in $[m]$, and if $k,\ell\in[n]$ with $k<\ell$, then $i<j$ whenever $i\in D_f(k)$ and $j\in D_f(\ell)$. Thus, we can think of $f$ as dividing $[m]$ into $n$ blocks, $D_f(1),D_f(2),\ldots,D_f(n)$, some of which may be empty.

Such a division of $[m]$ into $n$ blocks can equally well be accomplished by writing out $[m]$ in a row and inserting $n-1$ separators. For example, if $m=7$ and $n=5$, the arrangement

$$1\;2\;\mid\;3\;\mid\;\mid\;4\;5\;6\;7\mid$$

corresponds to the function $f$ that sends $1$ and $2$ to $1$, $3$ to $2$, and $4,5,6$, and $7$ to $4$ has $D_f(1)=\{1,2\}$, $D_f(2)=\{3\}$, $D_f(4)=\{4,5,6,7\}$, and $D_f(3)=D_f(5)=\varnothing$.

There are $$\binom{m+n-1}{n-1}=\binom{m+n-1}m$$ ways to choose where the $n-1$ separators are in a string of $m$ numbers and $n-1$ separators, so that is the number of non-decreasing functions from $[m]$ to $[n]$.

This is actually an instance of a kind of problem often called a stars-and-bars problem.

Brian M. Scott
  • 616,228