How many ways can circles overlap? - Numberphile
Вставка
- Опубліковано 13 кві 2019
- T-shirt and poster details below.
Check out Brilliant (get 20% off their premium service): brilliant.org/numberphile (sponsor)
More links & stuff in full description below ↓↓↓
Featuring Neil Sloane from the OEIS: oeis.org
And thanks to Jonathan Wild: www.mcgill.ca/music/jonathan-...
OEIS A250001 - Number of arrangements of n circles in the affine plane: oeis.org/A250001
3-Circles T-Shirt: teespring.com/three-circles-n...
4-Circles Poster: teespring.com/four-circles-nu...
Other merch: teespring.com/stores/numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from Math For America - www.mathforamerica.org/
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Animation by Pete McPartlan
Patreon: / numberphile
Numberphile T-Shirts: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9 - Наука та технологія
From this video... 3-Circles T-Shirt: teespring.com/three-circles-numberphile
4-Circles Poster: teespring.com/four-circles-numberphile
Other merch: teespring.com/stores/numberphile
Thumbs down for continuing to support an oppressive, fascist Internet censor (i.e., Patreon).
Plus, I would have bought the shirt if you didn't support Patreon.
@@paulthompson9668 care to elaborate? I am not trying to troll, just don't know what you are talking about. Any links to an article or a video..
Well if the circle is infinitely thin couldn’t it overlap infinitely many times?
Paul Thompson can you provide evidence for such a bold statement
I tried to find a background for Paul Thompson's statement.
I think it comes from some far right content creators being banned from Patreon. It seems that as a result, some accuse Patreon of interfering with freedom of speech and having a left wing political agenda. I also read that hate speeches were the reason behind the bans.
Continuously transitioning between the 16951 combinations of 5 circles could make for a nice screensaver
I'd settle for that GIF of the 3 circles in the end card. Mesmorising! 0_0
@@MumboJ Same! I would love a video just of that! A screensaver, too!
@@MumboJ It's actually the 4 circles from earlier
Doesn't that not save the screen though, as many pixels wouldn't change over the duration of the animation?
@@MaxMckayful to be fair, screensavers only serve their original function on CRT monitors. LCDs don't need them, but we still have them because, why not? They're fun.
4:38 *whispers* "Look at these. This is a very delicate...configuration..."
sounds like he found the rarest flower ever or something haha
Thankfully I'm not alone in finding that moment... Delicate... Exquisite...
That one is badly drawn - as it looks like two circles are touching at a point.
ASMR with circles!
that was a moment of pure, raw, unadulterated, sexual energy.
Today I'm sleeping early
3 am:
_in how many ways can circles overlap_
it is literally 2.51 here
03:31 here...
Same 😂😂
2:38 😂😂
I mean that is sleeping early
4:34 I like how Neil whispers really gently here, as if to not disturb the very fragile circle arrangements
The 4 Audi and 5 Olympic rings cannot be formed because of copyright violations.
Sup Keith, I'm Keith, how's it Keithin'?
This video is explicitly educational. That wouldnt stand up under the fair use doctrine.
Beautiful comment!
😂
Whoa - penetrating insight!
Did NOT at all expect hear that my classical sonata form professor is actually the goat of geometry!!! Very fascinating and I’m now even more a fan of Prof. Wild
it's so cool that he's a music professor!
(That's the major my university offered at least)
“Jonathan wild took this series out to 5”
Oh that’s actually not that impress-
“3: 14, 4: 173, 5: 16,951”
Oh never mind
Jonathan Fishman well that escalated quickly
what I don't get is why not give the set of rules to a learning AI and using the answers we already have and this AI's job would be to graph all possible combinations of circles.
@@erikburzinski8248 The number of possibilities is much too large. The AI would have to try all combinations of sizes of each circle, and positions of each circle, for each set of the overlap truth table entries seen in this video.
@@kenmolinaro Sure it perhaps couldn't do like 10 circles but something like 6 probably won't have more than few milion combinations witch should be pretty easy for some supercomputer to do.
Then again this stuff would be expensive and there probably isn't much to be gained here.
@@petrkinkal1509 You are vastly underestimating how many options there are to shift the positions of the circles around in the plane while varying their size.
"This cannot be realized by circles, it can be realized with ellipses"
Time to recalculate all of these numbers but where ellipses are allowed
That would be NP-Hard
@@Rudxain ?
@@Memerath Ok maybe I'm using incorrect terms, it could be just NP, NP Complete or NP Hard. They are terms describing difficulty of problem solving, (or just computation in most cases)
@@Rudxain oh
@@Rudxain its all the same. Lol
Whispers "this is very delicate" as if speaking loudly will blow the circles away. Lol
Or frighten the circles out of their formations
@@popisdeadisagoodsong9997 circles are very frightful
@@trickytreyperfected1482 circles are tough, but intersection is delicate
Don’t disturb my circles !
I like how this video went full circle.
CryMor Gaming ha hA HAA ha HASHA haHaaaAAahAHHAAAA
314th like
🥁
*Applaud*
4:30 sounding like a mathematical Attenborough
He sounds EXACTLY alike
Absolutely extraordinary!
"Here we see the common circle in its native habitat."
I am Egg dad?
After three (3) days of tracking fewmets we have found X
"I want to tell you about a really lovely problem..." Well I was doing something else, really, but now i'm going to stop and listen to this amazing man.
Dr Sloane has one of those wonderfully relaxing-yet-compelling voices that are just ideal for podcasts.
Well you have a _soft_ lower bound for 6. It's just 5's count.
You can extend it to at least twice 5's bound: all of 5's configurations with an additional independent circle next to them and all of 5's configurations with a circle surrounding all of it.
@@nienke7713 yes and you COULD keep extending it until you have done all of them
@@selflessslug370 that's essentially the goal, isn't it? To find an upper and lower bound and narrow it down until they produce the same number
@@nienke7713 I was thinking "surround" but not "independent." You have doubled the soft bound!
George Underwood lol my thoughts exactly.
"The answer for one circle is one. For two circles, three ways. What about three circles?"
Me: Oh no, it's TREE(3), isn't it?
This is pure asmr. With the added bonus its really interesting
Especially 4:35. Gave me tingles
Neil Sloane. Always interesting stuff.
The man always has a way of pulling me into something I would not otherwise find interesting. A lot of passion there.
I love Neil's passion for mathematics and his joy in showing us some of it. But for this video, the comments are just as gold.
When a child paints supposedly random circles: "Oh look, it drew one of the countless configurations from n circles!"
This seems like it could work really well for some kind of fictional writing system. It almost reminds me of the one written language from Myst that used specific segments of circles to represent words. (Arayani, if I'm remembering right)
Hey that's what I was thinking too haha. Unfortunately I think it would be hard to read, and the circle can be wildly different sizes at times, but I think it would be very pretty.
And also galifreyan
Although it only exists as images and hasn't had its rules explained, the language of the Boov aliens from Adam Rex's "The True Meaning of Smekday" is shown to consist entirely of overlapping circles.
1:58 Nice, Gray made a cameo!
we do have a lowerbound for 6. it's atleast the total of 5 times 2, since we can take all configurations and put a circle next to it and a circle around it.
Plus taking all of the level 4 configurations and putting them into two circles, taking all of the level 3 configurations and putting them into three circles, taking all of the level 2 configurations and putting them into four circles, and the level 1 inside of 5 circles....
A trivial lower bound could be easily published. But, I assume, no one has done so. So it is technically correct to say that there's no lower bound that we have. You only have it if it's published and peer reviewed.
at least*
true, but it's more of a combinatorics problem, not straight math.
we also have a lower bound on the number of comments as every viewer will at least mention something about there being a lower bound.
littleratblue that would be incorrect as some of level 4s configurations are already a level 3 configuration with a circle around them so you would just get duplicates.
This is one of my favorite videos in a long time. Very beautiful.
@8:19 I see a triangle and a hexagon wearing a bikini.
I was looking for the 6 as boobies with perky nipples, but he didn't show it. Guess he figures most guys know that set.
Hey panini
Hawt
sigh... unzip
Rule 34 is the truest rule of them all
How much paper do these guys go through
Let n represent that number of videos made with x representing that average number of takes to get it right...
Not enough!
Yes
You haven't seen the mile of pi video i guess
Tree(3)
Lower bound could be defined in terms of the previous value. but if you wanted to calculate it, you could get a rough estimate for a lower bound, let's say 2x the previous value, simply defined as the entire set inside of the new circle, and the entire set excluding the new circle. The value has to be greater than this, as there are other places that you can put the new configurations.
3:57 OEIS, On-Line Encyclopedia of Integer Sequences. A beatiful pleace on the internet, full of things all numberphile fans will love.
I haven't watched the video and I'm already excited, I love Neil's videos. Thanks for helping me end this crappy week with a smile.
Thanks for the animation efforts
No one:
Mathematician: "how many ways can I overlap circles"
Lol that's why I love maths
it's not even maths, these guys are just bored i swear
@@kasajizo8963 just like any other question where the answer doesn't matter, it's a candidate for the ultimate expression of arbitrariness
Jonathan Wild isnt a mathematician, hes a musician lol
Hes just bored
That's almost everything in math tbh. XD
4:31 Neil Sloane turns into Bob Ross.
4:44 Neil Sloane is Neil Sloane again.
Delicate transition
he loves the maths but also the visualising. I'm not sure hów rare that is, but it feels relatively so.
I love your voice, & thank you for sharing this beauty.
I'm going to have to look up affine plane again. I'm sure it made sense to me at some point in the past, but these days I only understand projective, as I've been obsessed with the projective plane for so long.
I get hyped every time they upload a video
Wouldn't a lower bound for the number of configurations be at least 2 times the previous number, because you would simply have all the previous configurations with another circle next to it, and all previous configurations with a circle around them?
Yes, you can easily think of some lower bounds even bigger than that. Another option would be all of the previous arrangement with another circle inside one of the other circles without any further intersections which will always be possible because you can make the inside circle as small as you want. That would give you another whole set of unique configurations, so we're already at 3 times the previous number. But Neil probably meant that there isn't really a meaningful, calculated lower bound that goes beyond these naive first considerations.
It'd be really cool to watch this in three dimensions (with spheres). I'd love to see that in a collab with @3Blue1Brown... just sayin'
9:17 - So is that the music of the spheres~?
A part of me asks, why would anyone wonder how many ways a circle can intersect, but a bigger part of me is impressed that people can think of this.
It was explained in a video that some mathematical problems exist simply for the love of mathematics, and since then i understood a bit more on why these sometimes ridiculous problems exist, and frankly i appreciate the science more
These are answers to questions that have never been asked. At some point, technology catches up and somebody in the year 2074 will be like "Wow. I was trying to figure out how to program my AI to move three carbon-fiber discs around a surface to block high speed particle projectiles, and somebody already created every possible situation where they intersect as the limiting parameters for the AI to fill in the gaps with. Perfect!"
Or some such nonsense like that.
A lot of seemingly arbitrary problems have spurred the development of new mathematics, new methods, deeper knowledge, as people try to solve them. Consider Fermat's last theorem. When you think about it, why does it really matter whether a^n + b^n = c^n has positive integer solutions for n > 2? How does the answer affect anyone's life? But people tried for over 300 years to solve it, and in the end the solution required very deep and complicated mathematics. A problem's worth is not always in its answer; often it's in how the quest for an answer leads us down paths to greater knowledge.
You're well on your way to becoming an osu! Rythm champion
Dude look at the CS he's playing with, there's no way anyone thss untalented can git gud.
AR 0?
Thank you for publishing this video, I have been thinking about weary similar problem for two years. Now I know that I am not alone.
Great Video aus always! I just love the voice of this gentlemen! Please do more interviews with him he seems like a very interesting character.
I’ve got an elegant proof for this one, but this reply box is too small to contain it.
Is this your last or first theorem?
@@onionbroofastora4684 Yes.
Just leave it as an exercise for the reader
Fermat’s Last Theorem 2: Numberphile’s Reckoning
Classic
I just love this guy’s quirky, quirky office
Great video. One example (with only 3 circles) where there are two inequivalent arrangements with the same "truth table" situation (combinations of being inside or outside each circle that exist in the arrangement) is that the 14th (last) arrangement Slone drew is equivalent in that sense to the Venn Diagram, but in the 14th arrangement there are two non-contiguous regions where you are in one of the circles (the middle one) but neither of the other two.
4:51 I think that there is a simple (bad) upper bound. If n is the number of circles, then there are at most k < 2^n regions in the final diagram. Consider the incidence graph of those regions. This graph has at most k < 2^n vertices, corresponding to the different regions. Now, we will think of our set of circles as [n] and we will label each vertex of our graph by the subset of [n] which consists of those circles that contain the corresponding region. I'm not going to prove this here, but I claim that this function from arrangements of circles to labeled graphs on at most 2^n vertices is injective. i.e. I'm saying that if two arrangements give the same labeled graphs, then they are really isotopic.
Anyway, we now have an injective function from arrangements to the set of graphs on at most 2^n vertices labeled by 2^n labels. To get an upper bound on the number of arrangements, it is enough to upper bound this number of labeled graphs. The number of graphs on k vertices is trivially upper bounded by 2^{\binom{k}{2}}. There are 2^n labels, so given a graph on k vertices, the number of labelings is at most (2^n)^k. It remains to sum the product of these over k from 0 to 2^n. Each term can be upper bounded by the largest term, giving a bound of 2^{\binom{2^n}{2}}*(2^n)^{2^n}*2^n
4:35 ASMR
@Wardhouse I tried looking it up, but there was a condemned energy behind every link
3:06 neil you're not the only one laughing 😂
I loved this video, also realized how the configuration for 3 circle is 14, first 3 digits of pie. 🙌
4:50 ok I can't think of an upper bound but a lower bound is easy 16,951 you could take any arrangement of 5 an add a circle off to the side. If you want a bigger one then imagine the circle is arbitrarily small and could fit in any of the sections that the plain is cut into by the circles. Well for each configuration of 5 there are at least 6 sections (the reagon touching the inside of each circle and the outer reagon) so that makes a lower bound of 101,706 but you could also have a circle that surrounds the entire thing increasing the lower bound to 118,657.
Nope. Some of those configurations of 5, putting the new circle in all six+ sections won't create 6+ *distinct* configurations. As a simplified example, take 2 circles that overlap. There are 4 sections: outside, in A, in B, in A+B. But in A and in B are equivalent, so those 2 sections only yield 1 new configuration.
Likewise, some distinct configurations of 5 will yield duplicates. Another simplified example: start with A: 3 concentric circles, and B: 2 separate circles inside a 3rd. For A, you can add a circle inside the outer but separate from the other 2. For B, you can add a circle inside one of the inner circles. Both results are the same.
@@jursamaj thanks I didn't think of that but I still would bet that it is above 118,657 as my flawed logic still applies to all other examples. But I still know for sure it's above 50,853.
"We don't have a lower bound." Of course we do. Just make an arbitrary number of arrangements (e.g., 0) and you now have a lower bound. A slightly less useless lower bound is 16,951 (draw a circle around every arrangement of 5.
He probably means we don't have a non-trivial lower bound
We can make that 33,902 if we add the other trivial case of just adding the 6th circle next to the arrangement.
Certainly we can make the case that n=6 circles has every single permutation as n=5 with the addition of an extra circle by itself, and an extra circle surrounding the others, permutations where the extra circle is inside each other circle without touching, etc. So this quickly goes racing off without end, and the idea of not having a low end is probably within the context that where the simple permutations end and the complex ones start is somewhere we might not know yet.
And surely there must be a really large upper bound, right? Every one of these circle things can also be described by the types of sets it has. So, an upper bound for 6 should be the number of potential sets (2^6) and the put that to the power of two (2^(2^6)) to count whether that set exists or not.
A trivial upper bound for six is, then, 2^32, though it could probably be lowered by removing reflections and all that.
@@GellyGelbertson I was also thinking 2^(2^n) as an upper bound, but I don't think that necessarily works. He does say that for each vector from the truth table you could possibly draw it in more than one way. The truth table also seems specific to intersecting (i.e., it omits the distinction between containment and just intersecting). I still agree though that it should in principle be possible to enumerate all those combinations (whether or not they are realizable) and come up with an upper bound.
This is exactly the content I subscribed for! I love the featured number videos, but when it boils down to modular/base arithmetic I find it so much less interesting than the elegant, complicated, and unknown curiosities such as this. Nonetheless, thank you for this amazing channel Brady!
We do have a lower bound for 6 circles; there have to be at least as many as the previous set, since you can just put another circle next to the previous configurations. You could also completely encompass the previous configurations, so really you can say that the next set has to have at least twice as many as the last set.
TL:DR the lower bound for 6 circles is 33902
I had (in a previous comment) double + 1: double the number for the same reasons you gave + 1 (a linear chain of 6). But now that I think about it, this extra one I think can be generalized to transform the “lower bound” to at least the triple from 5. All from 5 with a 6th around it; all from 5 with a 6th not connecting any of them; all from five but with one extra just connecting one of the circles (this last set would contain the linear chain of 6th). But I guess he meant we don’t have a lower bound for the “non-trivial” configurations and we are just nitpicking. xD
@@littlelifes coming back to this after 3 years, a thought just occurred to me that, in addition to the other two conditions, we could add 5 more, one for which we add a circle that is entirely inside one circle from a previous configuration, which makes the lower bound 7 times as many as the previous configuration.
I love the UNIX book behind Mr. Sloane :)
7:50 "Maybe you can draw it in more than one way."
What's an example of two dissimilar arrangements with equivalent boolean truth tables with 5 circles? Does one exist for 4 circles?
I’m struggling to imagine an example which is a genuinely different arrangement but with the same truth table.
There’s clearly no examples with 1, 2 or 3 circles.
What there is clearly examples of (which might be what he meant) is two different truth tables that are actually the same arrangement.
Eg with two circles:
Not A not B - 1
A not B - 1
B not A - 0
A and B - 1
Is clearly the same as:
Not A not B - 1
A not B - 0
B not A - 1
A and B - 1
Since you just relabelled which one is the inner and which is the outer circle.
@@nicks210684 Assuming I'm not horribly misunderstanding what the truth table is meant to show, wouldn't two circles that are next to eachother and two circles nested but not touching both give a truth table that says that nothing is touching anything despite being completely different arrangements?
@@MurzacNo.
All truth tables here would have Not A not B as true, because the drawing is finite and thus has an outer region.
With that in mind, here’s two separate circles:
A not B - 1
B not A- 1
A and B- 0
And here’s the table for one circle inside the other:
A not B - 1
B not A - 0
A and B - 1
Since A contains B, there’s no region contained by B, but not A.
When I saw the title in my feed I thought, "Oh yeah, another Neil Sloane feature!" I love these.
This is really cool. I think the first step to figuring out how to take this further is to simplify what we know as far as possible. That chart of the configurations of four circles is painfully asymmetrical and makes random choices for the sake of visuals rather than uniform ones
Here some (bad) upper bound:
For n circles, you can look into the 2^n ways to choose a subset of them. For each subset you look into the intersection of the circles and look whether it's empty or non empty (if you have a singleton, look on the part that so not intersect with all other circles). Each one of the 2^n subsets can be empty or non empty, so you have 2^(2^n) possiblities, and there can not be to different drawings with the same intersection tabke I described.
You could also use the number for 5 as a loose lower bound
Neil's videos always rock.
Dr. Sloane's videos make me moan.
There are at least 118657 combinations for 6 circles. One for the 5 case surrounded by the 6th, one for the 6th being completely outside, and the others being the 6th combined with each of the other 5. I tried to find a way to represent each of the combinations uniquely, and while doing so found an upper limit of 2^(2^(n)-1) or 9223372036854775808 combinations for 6 circles. You can represent each of the combinations by describing the unique areas; as an example for the 3 case, 1: A,B,C 2: A, AB, B, BC, C and so on.
Loving how it’s all animated, nice
Neil Sloane (is that his name?) has the mind for math and the voice for story telling !
I wanna see that full circle animation already!
I think I will attempt that tomorrow. Thanks for the vid
This is very similar to a problem or two I've been working on since January. I'm taking a multidimensional venn diagram of some number of "circles" x having all possible intersections, then filling the intersections with integers 0 to some number y that all sum to y. I'm creating a program to compute and create a growing tree of depth y representing all unique types or configurations such that there is no specified order of "circles". However the 1st problem I was working on is equivalent to this problem except that a circle's contents can be "inverted", meaning a slower growing tree.
This will be used to show all unique types of Boolean functions given some number w inputs, which is an equivalent problem to solving the number of unique mutidimensional shapes that can be made by selecting vertices of a multidimensional cube of w dimensions all side lengths one. The selected vertices make a complete graph showing the squared distances between each vertice, and every equivalent graph represents an equivalent shape. Each unique Venn type, with inversions allowed, can easily be converted to a unique graph. I should make a UA-cam video of this in 1.5 months or so when I'm done; it'll be more clear.
4:20-4:45 when no one but you understands your doodling
can relate
Not even I understand my doodling.
Round
Like a circle in a spiral
Like a wheel within a wheel
Never ending nor beginning
On an ever-spinning reel
...
...
...
Like the circles that you find
In the windmills of your mind
There's a biblical reference in there (Ezekiel 1;16)
What song is that? Or did you just write it on the spot?
Love this guy he makes learning so much fun
Thanks for teaching us how to draw unique venn diagrams
Me: do you speak gallifreyan ?
Neil: 😏
Omg i legit thought it looked like gallifreyan text too!
Glad i wasn't alone.
The thing is there are MANY kinds of gallifreyan, so it can be one!
0:58 **Super Smash Bros theme gets increasingly louder*
Andrew P. Roberts circles in smash 👀
how did you do the 4 circles animations? could we some how calculate that by computer?
this was the golden age of numberphile
Very interesting. Two questions I am left with:
Is this solved for triangles? I am genuinely unsure if it actually makes a difference, although I would imagine so.
Seeing as "touches" is not acknowledged as a separate state, does that mean that this is approached as a geometrical problem and not a topological one?
It does make a difference, two triangles can intersect each other in six different places at once, for example in the star of david.
On the opposite side of the spectrum, my dog will turn around in circles trying to get comfy to sleep. But that’s his second choice. He chooses lap over circles every time.
I think 'circles over lap' would've been clearer
hehe.. my dog does the circles before pooping
this was so nice, just a guy sharing his fascination with the world
I was actually just thinking about something like this on my own the other day!! so neat
Hey Bradey, Can you ask Neil if the same is true for spheres? Great video, thanks!
Might as well go all the way and ask if it works for spheres in n-dimensions.
the number of digits of each number of configurations up to 5 circles makes up the Fibonacci sequence (1,1,2,3,5), so maybe the configurations for 6 circles is 8 digits long?
I thoroughly enjoyed this
Something I've been thinking about is if I doodle a figure consisting of a number of loops which may intersect but are never co-linear, this divides the plane into regions bounded by the loops. I seem to be always able to colour these regions with only two colours such that no two adjacent regions are the same colour
Ah it hurts to see a beautiful problem/question like that but not even knowing how to go about solving something like that~
(I wanna learn the problem solving mental gymnastics that's so integral to maths)
It seems like we should at least be able to put a lower bound on the problem. Let the number of ways to draw n circles be expressed as C(n).
I assert, trivially, that for every arrangement C(n), if you remove one circle, you obtain one of the elements of C(n-1). Said another way, all elements of C(n) can be created by added one circle somewhere to an element of C(n-1). Therefore, a trivial lower bound is C(n) >= C(n-1). We can, of course, do better.
All elements of C(n-1) with a circle disconnected from them are elements of C(n). All elements of C(n-2) with some element of C(2) disconnected from them are also elements of C(n).
By extension, C(n) >= C(n-1)C(1) + C(n-2)C(2) + ... + C(n-k)C(k); k = floor((n-1)/2).
We could improve this lower bound by also adding in all possible combinations of 3, 4, or more disconnected groups, for 'n' high enough to permit such.
An upper bound might be constructed by finding a way to notate elements such that each notation has at most one element that corresponds to it - notations that correspond to impossible elements are allowed, since this is an upper bound, but notations that are ambiguous are not. I suggest the following - Order the circles. For each unordered pair of circles, provide a value - disjoint, intersecting, lower-contains-higher, higher-contains-lower. Ignoring a circle paired with itself, this gives 2^(n(n-1)) possibilities. Then, for each pair of (circle, (unordered pair of circles)) such that the pair does not include the initial circle, provide a value - circle does not contain the intersection of the pair, circle contains both intersections of the pair, circle contains only the intersection clockwise of the pair's overlap, circle contains the intersection anticlockwise of the pair's overlap. This gives 2^(n(n-1)(n-2)) possibilities. Combined, these give 2^(n(n-1)(n-1)) possibilities. Finally, since the initial ordering of the labels of the circles doesn't matter, divide by n!.
This gives a first order upper bound of 2^(n(n-1)(n-1))/n!. We could improve this by taking more care to eliminate impossible notations from consideration - for example, if Circle A contains or is disjoint from Circle B, then no circle can contain their intersections. Taking this into account makes the number crunching more complex, but still doable, and could reduce the upper bound considerably, but this comment is already very long.
The counting argument in your second paragraph doesn't work. You'd need to show that these arrangements are distinct.
If an element is formed of two disconnected sub-elements with *different* order, it can be identical to another element if and only if both sub-elements of one are identical to the corresponding sub-elements of each other. So long as x > y, C(x)C(y) counts a set of distinct elements that consist of an X circle element disjoint to a Y circle element. If an element of C(x) is identical to an element of C(y), that implies x = y, therefore no element in C(x)C(y) can be identical to any other element in C(u)C(v) so long as (x > y) and either x != u or y != v. Therefore the terms in the series must count different elements.
Since a situation in which x = y (that is, a C(x)C(x) term in the sequence) would overcount its elements, we currently do not include any such terms, thus ensuring our total estimate is undercounting, and is thus a lower bound - however, it should be possible with combinatorics to determine a proper counting (or at least, an undercounting) for C(x)C(x), or indeed, for C(x)^n in the case of larger numbers of disjoint sub-elements. For example of a simple undercounting of C(x)C(x), consider only pairs of non-identical elements of C(x). The number of unordered pairs of non-identical elements of C(x) is C(x)(C(x)-1)/2. The number of unordered pairs of two identical elements from C(x) is simple C(x). Therefore, a suitable term to account for C(x)C(x) elements is C(x)(C(x) + 1)/2. Similar logic can be used if one is counting elements in with more than two disjoint sub-elements, though the combinatorics is a little more messy.
4:35 my man sure was busting one with those circles 😳
Absolutely love this video
Im interested what would happen if you could also use ellipses? Also it will be interesting if you take the problem to the 3rd dimension and instead of circles you use spheres.
That circle intersection animation would make a great website spinner! Is it available anywhere?
I scrolled the comment section to find out the creator of that animation.
@@gauravkucheriya6903 Actually just found his name, thanks!
what was it @@TannerHartwig
@@ReductioadVeritas don't you just love the guys that expect people to answer thém, but don't bother to share the information?
They often dó take the time to mention they found it though... Like "otherwise people might search for weeks just to give me the answer, I'd better tell them it's okay to stop"
“No upper bound, no lower bound”
Some easy bounds for it:
Each term must be at least double the last- the new circle could be added disjoint to any configuration, or contain any configuration. This creates a lower bound of (2^(n-1)).
Next, the use of a truth table of intersections to describe each configuration means that there exists an upper bound at 2^(intersections)-1, or 2^(2^n-1)-1. This is negated if and only if multiple meaningfully different configurations can have the same truth table value, which seems impossible.
A better upper bound would take advantage of symmetry groups- only one of each must be considered, as the remainder are either invalid or duplicate. For three circles there are 39 unique, non-null symmetry groups. I’m not sure how that might be calculated for higher numbers, though.
Here’s a list, in case I missed anything and someone wants to point it out. Format is (a,b,c,d,e) where a is the number of singles, b doubles that are fully represented in singles, c doubles that have only one half represented, d doubles with no representation, and e triples. Dashed groups represent an actual arrangement. (Again, let me know if this can be simplified.)
(1,0,0,0,0)
(0,0,0,1,0)
(0,0,0,0,1)
(2,0,0,0,0)
(1,0,1,0,0)
(1,0,0,1,0)
(1,0,0,0,1)
(0,0,0,2,0)
(0,0,0,1,1)
(3,0,0,0,0) -
(2,1,0,0,0)
(2,0,1,0,0) -
(2,0,0,0,1)
(1,0,2,0,0) -
(1,0,1,1,0)
(1,0,1,0,1) -
(1,0,0,1,1)
(0,0,0,3,0)
(0,0,0,2,1)
(3,1,0,0,0) -
(3,0,0,0,1)
(2,1,1,0,0) -
(2,0,2,0,0)
(2,1,0,0,1) -
(2,0,1,0,1)
(1,0,2,1,0)
(1,0,2,0,1) -
(1,0,1,1,1)
(0,0,0,3,1)
(3,2,0,0,0) -
(3,1,0,0,1)
(2,1,2,0,0)
(2,1,1,0,1) -
(2,0,2,0,1)
(1,0,2,1,1)
(2,1,2,0,1) -
(3,2,0,0,1) -
(3,3,0,0,0) -
(3,3,0,0,1) -
Upper bound: 3^(n*(n-1)/2) since there are only 3 ways for any pair of circles to overlap (either one is inside the other, they intersect, or they're entirely outside each other)
You also need to take into account all the possible 3-way intersections and higher. The video implied a very weak upper bound of 2^(2^n).
I actually thought of this 3 years ago when I was wondering how many ways I can overlap circles as I add them. I knew the first three, but when I tried to do the four circles, I gave up because there was so many ways to do it. I shouldn’t have gave up 😂. At least someone older than me did it 😂
An animation of these cycling through positions would make a very satisfying loading screen.
A video featuring the very celebrated Neil Sloane himself. Gold!
Does anyone know where one can find the graphic shown at 4:45 ?
Not only the equation is hard, but also writing a program to brute force in efficient way is hard
♫♪Ludwig van Beethoven♪♫ you’d have a hard time computing it due to the discrete nature of computers.
@@shapshooter7769 If you have an algorithm for it, then it would be easy. The question is how hard is it to develop an algorithm.
@@shapshooter7769 would it be easier on a quantum computer instead?
That similar shape was a “hight” of 1 in the triangle and 1.75 in the hexagon. This means that the one in the hexagon has an area of about 3 or exactly 3.0625
Do you mean that the bikini shape in the triangle has distance between the ends equal to 1 and in the hexagon to 1.75? If so, I disagree. In hexagon it's equal to sqrt(3).
piotrkakol1992 not the distance between the ends. If you put the thing in a square with two of the ends in two corners and one end in the middle of a side, then the side length of the square would be 1.75. I believe that you are correct about the end to end length.
@@brycemw If you put the bikini from hexagon in a square just like you described then the side will have the same length as distance between the ends. And that is sqrt(3). I calculated it with the help of a triangle maked from upper and left side of a hexagon and a line drawed from 2 upper bikini ends in hexagon. The upper angle is 120 deg and the others are 30 deg each. You cut that triangle in half and you have one with 30, 60, 90 deg. The hypotenuse is 1 and you calculate the lower cathetus from law of sines as sqrt(3)/2.
piotrkakol1992 I think I explained it wrong. The shape is like an equilateral triangle. The high is shorter than the side length. I measured the hight as 1.75 the side length you listed is the correct one.
@@brycemw Well, if you make an equilateral triangle out of the bikini shape in the hexagon it's height is 1.5 and the side is sqrt(3).
Could it be possible to use the binary truth table for 3,4 and 5 circles and also record how many ways there are to draw those circles with specific intersections. Then you could see if there is a pattern in the number of ways each specific intersection is possible.
This is so satisfying to contemplate. Thank you math friends!
Those drawings of 4 circles look like "new" or "circular" Gallifreyan from Dr. Who
i think it is possible to creat the equation for the overlaping circles, its would be a tedious process but one that would be satifying, in fact, if i someone manage to create the equation i will edit the comment and put the equation in it
Edit: nvm guys its really hard, i tried to find a regression line that would fit the points the best but i mean, i tried
Oh man, this is very cool stuff!
for n=6:
lower bound: 69 372 871 (based on a very simple assumption that increase ratio (of 2nd ... 5th degree) is always ascending sequence)
other lower bound: 63 277 316 (based on an assumption that ratio for 5th degree of increase ratio in first step has in fact decreased same way like the ratio between 1st and 2nd degree in first step)
other lower bounds: 39 436 246, 13 169 694 and 1 660 904 (the last one is VERY VERY VERY low and unlikely, based on an assumption that increase ratio of 1st degree 16951/173 = 97.98265896.... also holds for 1660904/16951)
most probable value: around 122M - 123M (based on an assumption that all increase ratios (of 2st ... 5th degree) is ascending "smoothly" in all steps
upper bound for n=6 is around 694M (based on an assumption that highest increase ratio of 5th degree in last step is 10 (which is VERY VERY unlikely to be so big)