Intersections
Jim-dars
A random point is chosen from U(0,2*pi). A circle has zero degrees at 3
o'clock. Degrees being measured counter clockwise. Thus we have a random
point on a circle. The process is repeated and a chord is drawn. This "two
point selection" is repeated and a second chord is drawn. The process
continues until 5 chords are drawn. What is the probability that there are
exactly 8 chord intersections?
Best wishes, Jim
Chip Eastham
Jim,
Nice problem (again!).
The number of intersections depends only on the sequence or
permutation of points chosen. Without loss of generality the first
point chosen is taken to be at angle 0 (by rotational invariance), and
the numbering of the remaining points going counterclockwise around
the circle gives 9! possible sequences.
With just two chords (two pairs of points or four points in all) the
number of permutations is small enough for simple exhaustive
comparison. The chance of an intersection (at most one is possible)
is then 1/3.
With five chords the number of possible intersections ranges from 0 to
10. I don't have a clever way of pigeonholing the possibilities yet.
I've tried to apply a transition matrix (Markov process) approach, but
while this works for the simple case of two chords, it's difficult to
generalize to greater numbers of chords. A more promising line of
attach seems to be bootstrapping from n chords to n+1 chords.
Regards,
Chip
Jim-dars
"Chip Eastham" <eas...@bellsouth.net> wrote in message
news:fe86e950.02010...@posting.google.com...
Hi Chip,
Thanks, I think it is a "neat" problem. Unless I misjudge the situation,
not unlikely, you've walked all over a very simple solution, without
stepping on it.
Best wishes, Jim
Bob Harris
> A random point is chosen from U(0,2*pi). A circle has zero degrees at 3
> o'clock. Degrees being measured counter clockwise. Thus we have a random
> point on a circle. The process is repeated and a chord is drawn. This "two
> point selection" is repeated and a second chord is drawn. The process
> continues until 5 chords are drawn. What is the probability that there are
> exactly 8 chord intersections?
and Chip Eastham replied:
> The number of intersections depends only on the sequence or permutation of
> points chosen. Without loss of generality the first point chosen is taken to
> be at angle 0 (by rotational invariance), and the numbering of the remaining
> points going counterclockwise around the circle gives 9! possible sequences.
As I see it, it's 9*7*5*3*1 instead of 9!
I didn't see anything much easier than working them all out by hand. The
best 'shortcut' I found was to split the 5 points into two halves, and count
separately the configurations that crossed the divide 1, 3, or 5 times.
That's not much of a shortcut.
Here's what I ended up with; it could easily be incorrect. My answer for
the original question is "13".
. | 2 | 3 | 4 | 5 |
. intersections | chords | chords | chords | chords |
. --------------+--------+--------+--------+---------+
. 0 | 2/3 | 5/15 | 14/105 | 42/945 |
. 1 | 1/3 | 6/15 | 28/105 | 120/945 |
. 2 | | 3/15 | 28/105 | 180/945 |
. 3 | | 1/15 | 20/105 | 195/945 |
. 4 | | | 10/105 | 165/945 |
. 5 | | | 4/105 | 119/945 |
. --------------+--------+--------+--------+---------+
. 6 | | | 1/105 | 72/945 |
. 7 | | | | 33/945 |
. 8 | | | | 13/945 |
. 9 | | | | 5/945 |
. 10 | | | | 1/945 |
. --------------+--------+--------+--------+---------+
The top row, I'm pretty sure, is the catalan numbers (2, 5, 14, 42, ...)
Jim-dars later wrote:
> Unless I misjudge the situation, not unlikely, you've walked all over a very
> simple solution, without stepping on it.
I think I've tromped a very similar path. I've missed the simple solution.
A lot of the counts look like they're in Pascal's triangle. This makes me
suspiscious of 13 and 119 in my table.
--
-- Bob Harris =======================================================+
| One man's mink is another man's weasel |
+====================================================================+
Graham Jones
da...@mediaone.net> writes
[...]
>Thanks, I think it is a "neat" problem.
Do you have a neat solution? I have an answer of 1/63, but the solution
is not very neat, and I've not checked it carefully...
First, we have ten points on the circle, let's label them 0 to 9
clockwise. There are 10C2 * 8C2 * 6C2 * 4C2 * 2C2 / 5! = 9*7*5*3 = 945
ways of joining them up to make 5 chords. We want to know how many of
these ways give 8 intersections.
Second, if we go along each line in turn, we must encounter 16
intersections (each one twice). From this it follows that either one or
two of the lines intersects all the other four. (If no lines intersect
all others, we encounter at most 15 intersections, if 3 or more lines
each intersect all others, we encounter at least 18.)
Third, count the ones with one line that intersects all others. It must
be 0-5, 1-6, 2-7, 3-8 or 4-9, and all the other lines start one side if
it and end the other.
* | +
* | +
* | +
* | +
It's like this, and each * must join a +. By my reckoning there is just
one way of doing this without making another line that intersects all
four others. So that's 5 ways.
Fourth, count the ones with two lines that both intersect all others.
These two must be 0-5 and 1-6, 1-6 and 2-7, 2-7 and 3-8, 3-8 and 4-9 or
4-9 and 0-5, and all the other lines start one side of these and end the
other. (Why is an exercise.)
\ /
* \ / +
* X +
* / \ +
/ \
It's like this, and each * must join a +. By my reckoning there are two
valid ways of doing this. So that's 10 more ways.
Final probability = 15/945 = 1/63.
Graham
Chip Eastham
Bob,
I can confirm the 3 chord probabilities, at least in the sense that I
got the same numbers in my approach.
As for 5 chords, I agree that 9! possibilities can be reduced to a
"tree" with 9*7*5*3 = 945 leaves, but I expected some algebraic
regularity from the permutation point of view (that has yet to
materialize!).
Perhaps Jim is hinting that like the binomial coefficients, it may be
easier to find the terms close to the extreme. E.g. 10 intersections
between five chords can only occur in essentially one way in your
"tree". It's not completely clear to me how to apply it to your tree,
but "switching" the ends of any two "adjacent" chords (which can
happen five ways) in the 10 intersection configuration reduces the
intersection count to 9. Presumably the 5/945 figure can be derived
in this way, and likely there's a way to get at counting the 8
intersection configurations, too, without deriving all the
probabilities.
Regards,
Chip
Jim-dars
Well, I finally realized I don't have a solution. So be it.
What I had in mind was considering the sequence of end point (radians) as:
xxxx[xx]xxxx
denoting the result as D (here either I [indeterminate] or 0 [zero]).
and thus building a simple tree. Alas, not so simple. Still, working from
the middle does seem best.
Surely the case of n chords and j intersections has been considered?
Best wishes, Jim
Bob Harris
method. I found a couple errors, and so my table now reads thus:
. | 2 | 3 | 4 | 5 |
. intersections | chords | chords | chords | chords | factors
. --------------+--------+--------+--------+---------+
. 0 | 2/3 | 5/15 | 14/105 | 42/945 | 6 * 7
. 1 | 1/3 | 6/15 | 28/105 | 120/945 | 10 * 15
. 2 | | 3/15 | 28/105 | 180/945 | 12 * 15
. 3 | | 1/15 | 20/105 | 195/945 | 13 * 15
. 4 | | | 10/105 | 165/945 | 11 * 15
. 5 | | | 4/105 | 117/945 | 9 * 13
. --------------+--------+--------+--------+---------+
. 6 | | | 1/105 | 70/945 | 7 * 10
. 7 | | | | 35/945 | 5 * 7
. 8 | | | | 15/945 | 3 * 5
. 9 | | | | 5/945 |
. 10 | | | | 1/945 |
. --------------+--------+--------+--------+---------+
This agrees with Graham Jones's post for 15 ways to get 8 crossings.
The counts for column five have interesting factors. I almost see a
pattern, but not quite.
Bob Harris
the table:
| 2 | 3 | 4 | 5 | 6 |
| chords | chords | chords | chords | chords |
intersections | /3 | /15 | /105 | /945 | /10,395 |
--------------+--------+--------+--------+--------+---------+
0 | 2 | 5 | 14 | 42 | 132 |
1 | 1 | 6 | 28 | 120 | 495 |
2 | | 3 | 28 | 180 | 990 |
3 | | 1 | 20 | 195 | 1,430 |
4 | | | 10 | 165 | 1,650 |
5 | | | 4 | 117 | 1,617 |
--------------+--------+--------+--------+--------+---------+
6 | | | 1 | 70 | 1,386 |
7 | | | | 35 | 1,056 |
8 | | | | 15 | 726 |
9 | | | | 5 | 451 |
10 | | | | 1 | 252 |
--------------+--------+--------+--------+--------+---------+
11 | | | | | 126 |
12 | | | | | 56 |
13 | | | | | 21 |
14 | | | | | 6 |
15 | | | | | 1 |
--------------+--------+--------+--------+--------+---------+
Looking at the columns for 4, 5, and 6 chords, I do see a pattern emerging.
In the tbale below, 15c10 (for example) means 15-choose-10. The pattern
seems to work perfectly until we get to close to the top.
K | 4 chords | 5 chords | 6 chords |
---+------------------+--------------------+------------------------+
0 | 14 | 42 | 132 |
1 | 28 = 8c5 - 7*4c1 | 120 | 495 |
2 | 28 = 7c4 - 7*3c0 | 180 = 12c8 - 9*7c3 | 990 |
3 | 20 = 6c3 | 195 = 11c7 - 9*6c2 | 1,430 |
4 | 10 = 5c2 | 165 = 10c6 - 9*5c1 | 1,650 |
5 | 4 = 4c1 | 117 = 9c5 - 9*4c0 | 1,617 = 15c10 - 11*9c4 |
---+------------------+--------------------+------------------------+
6 | 1 = 3c0 | 70 = 8c4 | 1,386 = 14c9 - 11*8c3 |
7 | | 35 = 7c3 | 1,056 = 13c8 - 11*7c2 |
8 | | 15 = 6c2 | 726 = 12c7 - 11*6c1 |
9 | | 5 = 5c1 | 451 = 11c6 - 11*5c0 |
10 | | 1 = 4c0 | 252 = 10c5 |
---+------------------+--------------------+------------------------+
11 | | | 126 = 9c4 |
12 | | | 56 = 8c3 |
13 | | | 21 = 7c2 |
14 | | | 6 = 6c1 |
15 | | | 1 = 5c0 |
---+------------------+--------------------+------------------------+
--
-- Bob Harris =======================================================+
| If stupidity got us into this mess, how come it can't get us out |
| of it? |
+====================================================================+
Jim-dars
Not having programmed in a while I'm brushing up on my Visual Basic. Seems
I can Monte Carlo this and have the results cluster about the appropriate
integers. As Chip (I believe) pointed out, your first row is composed of
Catalan numbers (at least so far). Perhaps other patters might display
themselves --- perhaps even an algorithm is possible.
Best wishes, Jim
"Bob Harris" <nit...@mindspring.com> wrote in message
news:B8637FF1.1BDE1%nit...@mindspring.com...
Henry
I would suggest the pattern for the numerator
Sum_{j} (-1)^j * C( (n-j)(n-j+1)/2-1-i,n-1) * (C(2n,j)-C(2n,j-1))
where n is the number of chords,
i the number of intersections,
C(x,y) is x choose y when x>=y>=0 and 0 otherwise,
and j ranges over the integers
(though in fact 0<=j<=n would be more than enough to capture all
non-zero terms)
The denominator is clearly (2n)!/(n!*2^n)
For some examples for the numerator:
n=4, i=2 gives
C(7,3)*(C(8,0)-C(8,-1)) -C(3,3)*(C(8,1)-C(8,0))
+C(0,3)*(C(8,2)-C(8,1)) -...
=35*1-1*7+0*20-... =28
as in the table below
n=6, i=0 gives
C(20,5)*(C(12,0)-C(12,-1)) -C(14,5)*(C(12,1)-C(12,0))
+C(9,5)*(C(12,2)-C(12,1)) -C(5,5)*(C(12,3)-C(12,2))
+C(3,5)*(C(12,4)-C(12,3)) -...
=15504*1-2002*11+126*54-1*154+0*275-... =132
as in the table below
n=6, i=1 gives
C(19,5)*(C(12,0)-C(12,-1)) -C(13,5)*(C(12,1)-C(12,0))
+C(8,5)*(C(12,2)-C(12,1)) -C(4,5)*(C(12,3)-C(12,2))
+C(2,5)*(C(12,4)-C(12,3)) -...
=11628*1-1287*11+56*54-0*154+0*275-... =495
as in the table below
n=7, i=0 gives
C(27,6)*(C(14,0)-C(14,-1)) -C(20,6)*(C(14,1)-C(14,0))
+C(14,6)*(C(14,2)-C(14,1)) -C(9,6)*(C(14,3)-C(14,2))
+C(5,6)*(C(14,4)-C(14,3)) -...
=296010*1-38760*13+3003*77-84*273+0*637-... =429
which is the Catalan number after 132 as pointed out by someone else.
This would give two combinatorial results:
Sum_{j} (-1)^j * C( (n-j)(n-j+1)/2-1,n-1) * (C(2n,j)-C(2n,j-1))
=C(2n,n)/(n-1)
[the Catalan result with i=0]
Sum_{i,j} (-1)^j * C( (n-j)(n-j+1)/2-1-i,n-1) * (C(2n,j)-C(2n,j-1))
=(2n)!/(n!*2^n)
[the sum of all possibilities, with j taken over intergers and i over
non-negative integers]
Bob Harris
> ... perhaps even an algorithm is possible.
The program below can be used to count the distribution of intersections.
It agrees with my other counts through 6 chords. I can't believe I did so
much work the hard way before realizing how simple the algorithm was.
Bob H
------
#include <stdlib.h> // standard C stuff
#include <stdio.h> // standard C i/o stuff
#include <stdarg.h> // standard C variable arg list stuff
#include <string.h> // standard C string stuff
typedef unsigned long u32;
#define numChords 8
#define numPoints (2*numChords)
#define maxIntersections ((numChords*(numChords-1))/2)
int circle[numPoints]; // circle[p] is
// .. 0 => unused
// .. +n => first end of chord n
// .. -n => second end of chord n
u32 dist[maxIntersections+1]; // dist[i] is the number of ways we can
have
// .. exactly i interesections
int main (void);
void CountIntersections (int chordsLeft, int crossings);
int logprintf (char* format, ...);
int logvprintf (char* format, va_list args);
int main
(void)
{
int p, i;
// initialize the data structures
for (p=0 ; p<numPoints ; p++)
circle[p] = 0;
for (i=0; i<=maxIntersections ; i++)
dist[i] = 0;
// count intersections
CountIntersections (numChords, 0);
// print results
for (i=0; i<=maxIntersections ; i++)
printf ("%d %ld\n", i, dist[i]);
return 0;
}
//----------
// [[--- recursive function ---]]
//
// CountIntersections--
//
//----------
//
// Arguments:
// int chordsLeft: The number of chords left to place, in the circle[]
array.
// int crossings: The number of crossings that already exist in the
circle[]
// array.
//
// Returns:
// (nothing)
//
//----------
void CountIntersections
(int chordsLeft,
int crossings)
{
int p, q;
// find first two unused endpoints, accounting for the crossings between
// them
for (p=0 ; circle[p]!=0 ; p++)
;
for (q=p+1 ; circle[q]!=0 ; q++)
crossings++;
// if we've only got one chord left to place, this is it
if (chordsLeft == 1)
{ dist[crossings]++; return; }
// 'attach' one end of this chord
circle[p] = chordsLeft;
// 'attach' other end, and count the intersections for the remaining
// chords
circle[q] = -chordsLeft;
CountIntersections (chordsLeft-1, crossings);
circle[q] = 0;
// try all the other possible endpoints for it
while (++q<numPoints)
{
// if this endpoint is taken, adjust our crossing count
if (circle[q] != 0) { crossings++; continue; }
// otherwise, try this out as our second endpoint
circle[q] = -chordsLeft;
CountIntersections (chordsLeft-1, crossings);
circle[q] = 0;
}
// remove the first endpoint
circle[p] = 0;
}
Bob Harris
> Looking at the columns for 4, 5, and 6 chords, I do see a pattern emerging.
> In the tbale below, 15c10 (for example) means 15-choose-10. The pattern
> seems to work perfectly until we get to close to the top.
The K=1 row (i.e. number of wayus to have exactly one intersection) matches
with (2n)-choose-(n-2), where n is the number of chords.
I've found more on the rest of the pattern, too. But not enough to post
yet.
Bob H
Bob Harris
> I would suggest the pattern for the numerator
> Sum_{j} (-1)^j * C( (n-j)(n-j+1)/2-1-i,n-1) * (C(2n,j)-C(2n,j-1))
> where n is the number of chords,
> i the number of intersections,
> C(x,y) is x choose y when x>=y>=0 and 0 otherwise,
> and j ranges over the integers
> (though in fact 0<=j<=n would be more than enough to capture all
> non-zero terms)
That formula agrees with my program (previously posted) through the 8 chord
cases. How did you arrive at the formula?!
I wish I could see a way to prove the validity of the formula. Probably
some student in a sophomore combinatorics class could prove this as an easy
homework problem, but I don't see it. So far, all I know is the formula
agrees with my program, and my program agrees with my hand calculations.
For what it's worth, I'm appending the table (produced by the formula)
through ten chords. I also find the average number of chords pretty
interesting. Looks like it's n(n-1)/6, which is exactly one third of the
max number of intersections.
The most interesting number in the table is 13013, which, if read with
bleary eyes, is my name.
BOB
| number of chords |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
------+---+---+---+----+-----+------+-------+--------+---------+----------+
0 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | 4862 | 16796 |
1 | | 1 | 6 | 28 | 120 | 495 | 2002 | 8008 | 31824 | 125970 |
2 | | | 3 | 28 | 180 | 990 | 5005 | 24024 | 111384 | 503880 |
3 | | | 1 | 20 | 195 | 1430 | 9009 | 51688 | 278460 | 1434120 |
4 | | | | 10 | 165 | 1650 | 13013 | 89180 | 556920 | 3255840 |
5 | | | | 4 | 117 | 1617 | 16016 | 131040 | 946764 | 6267492 |
---+---+---+---+----+-----+------+-------+--------+---------+----------+
6 | | | | 1 | 70 | 1386 | 17381 | 169988 | 1419432 | 10620240 |
7 | | | | | 35 | 1056 | 16991 | 199264 | 1922904 | 16240440 |
8 | | | | | 15 | 726 | 15197 | 214578 | 2394450 | 22810260 |
9 | | | | | 5 | 451 | 12558 | 214760 | 2775080 | 29809670 |
10 | | | | | 1 | 252 | 9646 | 201460 | 3021444 | 36604944 |
---+---+---+---+----+-----+------+-------+--------+---------+----------+
11 | | | | | | 126 | 6916 | 178248 | 3112632 | 42558480 |
12 | | | | | | 56 | 4641 | 149464 | 3051024 | 47132160 |
n 13 | | | | | | 21 | 2912 | 119168 | 2858040 | 49961640 |
u 14 | | | | | | 6 | 1703 | 90540 | 2567340 | 50891880 |
m 15 | | | | | | 1 | 924 | 65640 | 2217480 | 49974237 |
b ---+---+---+---+----+-----+------+-------+--------+---------+----------+
e 16 | | | | | | | 462 | 45438 | 1845486 | 47432550 |
r 17 | | | | | | | 210 | 30024 | 1482264 | 43609845 |
18 | | | | | | | 84 | 18908 | 1150220 | 38908580 |
o 19 | | | | | | | 28 | 11320 | 862920 | 33735735 |
f 20 | | | | | | | 7 | 6420 | 626076 | 28459530 |
---+---+---+---+----+-----+------+-------+--------+---------+----------+
i 21 | | | | | | | 1 | 3432 | 439263 | 23380830 |
n 22 | | | | | | | | 1716 | 297891 | 18719370 |
t 23 | | | | | | | | 792 | 195075 | 14612805 |
e 24 | | | | | | | | 330 | 123165 | 11125260 |
r 25 | | | | | | | | 120 | 74817 | 8261523 |
s ---+---+---+---+----+-----+------+-------+--------+---------+----------+
e 26 | | | | | | | | 36 | 43605 | 5983290 |
c 27 | | | | | | | | 8 | 24293 | 4224935 |
t 28 | | | | | | | | 1 | 12870 | 2907190 |
i 29 | | | | | | | | | 6435 | 1947880 |
o 30 | | | | | | | | | 3003 | 1269466 |
n ---+---+---+---+----+-----+------+-------+--------+---------+----------+
s 31 | | | | | | | | | 1287 | 803605 |
32 | | | | | | | | | 495 | 493240 |
33 | | | | | | | | | 165 | 292885 |
34 | | | | | | | | | 45 | 167770 |
35 | | | | | | | | | 9 | 92359 |
---+---+---+---+----+-----+------+-------+--------+---------+----------+
36 | | | | | | | | | 1 | 48620 |
37 | | | | | | | | | | 24310 |
38 | | | | | | | | | | 11440 |
39 | | | | | | | | | | 5005 |
40 | | | | | | | | | | 2002 |
---+---+---+---+----+-----+------+-------+--------+---------+----------+
41 | | | | | | | | | | 715 |
42 | | | | | | | | | | 220 |
43 | | | | | | | | | | 55 |
44 | | | | | | | | | | 10 |
45 | | | | | | | | | | 1 |
------+---+---+---+----+-----+------+-------+--------+---------+----------+
avg | 0 |1/3| 1 | 2 | 10/3| 5 | 7 | 28/3 | 12 | 15 |
------+---+---+---+----+-----+------+-------+--------+---------+----------+
Henry
<nit...@mindspring.com> wrote:
>Henry wrote:
>> Sum_{j} (-1)^j * C( (n-j)(n-j+1)/2-1-i,n-1) * (C(2n,j)-C(2n,j-1))
>cases. How did you arrive at the formula?!
If you insist on knowing my secrets
(and the scientific - but illogical - approach to numbers)
You had previously posted values for 6 chords like
726 = 12c7 - 11*6c1
451 = 11c6 - 11*5c0
252 = 10c5
This would be neater as
726 = 12c5 - 11*6c5
451 = 11c5 - 11*5c5
252 = 10c5
etc.
which explains why the second term disappears.
(with 5 chords the pattern is xc4, with 4 it is xc3)
You also had some missing explanations
and using the previous pattern I got:
1,650 = 16c5 - 11*10c5 + ?(54)
1,430 = 17c5 - 11*11c5 + ?(324)
990 = 18c5 - 11*12c5 + ?(1134)
495 = 19c5 - 11*13c5 + ?(3024)
132 = 20c5 - 11*14c5 + ?(6650)
The first four bracketed terms are multiples of 54
(54*1, 54*6, 54*21, 54*56) and with an assumption for the last I got:
1,650 = 16c5 - 11*10c5 + 54*5c5
1,430 = 17c5 - 11*11c5 + 54*6c5
990 = 18c5 - 11*12c5 + 54*7c5
495 = 19c5 - 11*13c5 + 54*8c5
132 = 20c5 - 11*14c5 + 54*9c5 - 154*5c5
So the alternating signs are now apparent
Now I needed a possibility for the x and y in x*yc5
To take the last example: 20,14,9,5 have differences of 6,5,4 so I was
are looking at something offset from triangular numbers.
1,11,54,154 was not so immediately obvious, but looking it up in
http://www.research.att.com/~njas/sequences/
gives sequence A008315 which in turn suggests
12c0, 12c1-12c0, 12c2-12c1, 12c3-12c2.
Then it was just a matter of glancing at the 4 and 5 chord examples to
see how to produce a reasonably consistent formula,
testing it against some other values suggested by you and others,
and posting the result.
Jim-dars
Why OF COURSE!!! Sorry I posed a problem with such an obvious solution.
Best wishes, Jim
"Henry" <se...@btinternet.com> wrote in message
news:3c41f542...@news.btinternet.com...