How many ways can circles overlap? - Numberphile
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- T-shirt and poster details below.
Check out Brilliant (get 20% off their premium service): brilliant.org/... (sponsor)
More links & stuff in full description below ↓↓↓
Featuring Neil Sloane from the OEIS: oeis.org
And thanks to Jonathan Wild: www.mcgill.ca/...
OEIS A250001 - Number of arrangements of n circles in the affine plane: oeis.org/A250001
3-Circles T-Shirt: teespring.com/...
4-Circles Poster: teespring.com/...
Other merch: teespring.com/...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoun...
And support from Math For America - www.mathforame...
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Videos by Brady Haran
Animation by Pete McPartlan
Patreon: / numberphile
Numberphile T-Shirts: teespring.com/...
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
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.
4:34 I like how Neil whispers really gently here, as if to not disturb the very fragile circle arrangements
He’s learnt from Archimedes.
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
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
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!
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
Dr Sloane has one of those wonderfully relaxing-yet-compelling voices that are just ideal for podcasts.
"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.
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 !
This is pure asmr. With the added bonus its really interesting
Especially 4:35. Gave me tingles
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?
XD
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.
This is one of my favorite videos in a long time. Very beautiful.
1:58 Nice, Gray made a cameo!
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.
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 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.
Tsk! I were gonna go that!
@@AsherStone-wd3rbwhere did you find this?
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)
When a child paints supposedly random circles: "Oh look, it drew one of the countless configurations from n circles!"
Thanks for the animation efforts
3:57 OEIS, On-Line Encyclopedia of Integer Sequences. A beatiful pleace on the internet, full of things all numberphile fans will love.
I get hyped every time they upload a video
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.
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.
9:17 - So is that the music of the spheres~?
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
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.
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.
@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
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
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.
I just love this guy’s quirky, quirky office
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?
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.
I loved this video, also realized how the configuration for 3 circle is 14, first 3 digits of pie. 🙌
Thanks for teaching us how to draw unique venn diagrams
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.
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).
Neil Sloane (is that his name?) has the mind for math and the voice for story telling !
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.
4:35 ASMR
@Wardhouse I tried looking it up, but there was a condemned energy behind every link
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.
I love the UNIX book behind Mr. Sloane :)
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
"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!
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?
There's a pretty clear upper bound here:
You can make an injection from one configuration of circles to a function from the power set of {1,2,..n} to {True, False}.
The rule is that some subset yields True iff there is a point contained in only the circles whose numbers are in that subset.
So, the Venn Diagram yields {}->True, {1}->True, {2}->True, {1,2}->True.
Notice that {} must yield True, and at least one of the singletons must yield True.
Now represent as a bit string of length 2^n: the Venn Diagram yields 1111.
This is, the first bit must be 1. and at least one of the next n bits must be 1.
The number of configurations of n circles is bounded above by the bit strings of length 2^n-1 such that there is a 1 in the first n bits.
This is 2^(2^n-1)-2^(2^n-1-n)=2^((2^n-1)/(2^n-1-n)).
Hope Numberphile sees this.
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
“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) -
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'
A weak lower bound for 6 circles will 33902 where all 16951 combinations for 5 circles can be drawn inside a circle and can have a circle besides then. A weak upper bound will be 2^2^6 or 2^64
3:06 neil you're not the only one laughing 😂
A video featuring the very celebrated Neil Sloane himself. Gold!
I wanna see that full circle animation already!
I submit the unhelpful upper bound for the arrangements of n circles as the number of arrangements of possible combinations of up to n elements: 2^(2^n)
This can be trivially narrowed further such as by removing all combinations that do not contain all n elements, but should provide a rough sense of scale for any attempt at brute forcing solutions for a given n.
This gives an upper bound for 6 of 2^(2^6)=2^64 ~= 10^19 or roughly an exobyte of data.
4:20-4:45 when no one but you understands your doodling
can relate
Not even I understand my doodling.
For n circles with number of overlap configurations f(n), the lower bound of overlaps for n+1 circles, f(n+1), is 2 * f(n). Trivially, there are always two sets of overlap patterns when you add one more circle: the new circle is not connected to any circle in the smaller pattern, the new circle completely encircles the smaller pattern. You can't say more than that because of the possibility of symmetrical/equivalent patterns.
The third set when n=2 (the new circle is connected to exactly one other circle (and does not encircle anything itself) in the smaller pattern) doesn't hold as unique for greater n. You can see when going from 2 to 3, in the diagram in the video, pattern 7 for three circles fits both "adding to an existing pattern" and "attaching to an existing pattern". This will hold for all n going forward: there will be a chain of connected circles of length n, and there will be a chain of length n-1 with a lone circle; connecting a circle to the second chain, and adding a lone circle to the first chain will result in identical patterns counted twice, so not a lower bound.
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.
4:35 my man sure was busting one with those circles 😳
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)
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)
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.
Triangles are quite different, as you then also have to take rotation into account. Circles have an infinite rotational symmetry...
this was so nice, just a guy sharing his fascination with the world
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.
The circle overlap configurations remind me of electron orbitals, of course the orbits of electrons aren't all strictly circular, but it got me thinking of elements
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?
When I saw the title in my feed I thought, "Oh yeah, another Neil Sloane feature!" I love these.
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
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 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 😂
He says we don't have an upper bound but the truth tables give one. There are 2^(2^n) possible configurations of intersections so this is an upper bound. This bound disregards drawability, treats the circles as distinct and allows combinations of presence and absence of intersections which don't make logical sense (e.g. A⋂B⋂C present but A⋂B not present). There are some obvious multiple-countings in this number so the bound can be tightened quite easily. It might not be great but its still an upper bound.
An animation of these cycling through positions would make a very satisfying loading screen.
Technically; the lower bound, for 6 circles, is 16951. It’s definitely more than that; since we can take any and all 5-circle-configurations, and draw a circle next to them, or around them, etc.
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!
4:52 Of course we have a lower bound. 16,951 configurations of 5 circles, each of which can be encircled themselves, OR each of which can have a circle placed adjacent that touches none of them. That instantly gives 33,902 as a lower bound, though an unreasonably low one.
There is no proof that that combinations(n) will always be greater than combinations(n+k) where k is any non zero positive integer. The intuition tells us it should hold but no rigorous proof.
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?
I've been subscribed for years now because I truly believe that it is important that this channel exists. That said, I always struggle to accept the assertions that are made in the first several minutes of the video due to the complete lack of rationale or context as to why these assertions are applicable to what I'm about to digest.
Without a doubt, the video always culminates in an interesting and thought provoking conclusion; I, however, am always waiting for the other foot to fall. The introduction of rules/assertions that must be accepted on, well... basically "faith" from the onset makes it difficult for me to process the information I am receiving. To me it is analogous to explaining the rules of baseball to a child before acknowledging that you are about to play a game. Being a mathematician myself, I never accept an imposed condition until it as proven as valid.
In conclusion, I am sorry for the tirade. I love this channel and want to see it prosper. I have to accept the idea that your channel has proven this style/format is the most successful; in which case, keep doing what you are doing. Critical math should be supported and proliferated as ubiquitouslly as possible
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
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 TH-cam video of this in 1.5 months or so when I'm done; it'll be more clear.
I wonder if this problem is easier for other shapes, like squares
I think it is equally hard with ( regular quadrilateral )
Now they have sides
I said squares not rectangles.
@@ComposingGloves maybe have a try then
Now assign a note to each of the ABCDE intersections, start on a point on a circle and trace a path, playing the notes of the intersections. Use this to define a new way to describe music, store data and revolutionize math.
I mean, I can't do it, but this is the kind of way that really cool advances in human understanding come about.
It also explains dubstep.
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"
One has to find a suitable invariant of these n overlapping circles.
A seemingly impossible for practical application approach looks like this:
1. We have 2-dimensional infinite plane
with discrete Cartesian coordinate system, with all its attributes - origin O(0, 0), x-axis, y-axis, points with only integer coordinates P(x, y). The Oxy plane is infinite, because in this way we can cover all the mutual positions of the circles with all possible sets of radii. Here we do not brake one of the rules of the problem (to draw the circles on affine plane, not on the projective one), because the radii of the circles and the distances between the circles are finite, also the scale doesn't affect our evaluation of a particular set of n circles.
2. First of all, we have to choose n points on the discrete 2-dimensional plane in such way that we have to discard all mirror images, rotations, transpositions, translations (but not scaling!) of these n points.
3. For every unique set of n points we have to assign an unique set of integer radii (or, maybe, geometrically more suitable case, with radii, defined as distance between any two points with integer coordinates; in this case radii might be also irrational numbers).
4. For every such unique n-tuple of circles we have to evaluate how they interact and to classify their interactions (as if p.2 and p.3 are not difficult enough). This implies inventing a language which fully describes these interactions.
5. For every n-tuple of centers of the circles with their coordinates we vary their radii in n-dimensional space.
We have to exclude all forbidden interactions and to find condition that terminates further increment of each one of those n radii.
6. Thus, for just one n-tuple of points on the 2-dimensional plane we derive all possible configurations of those n circles.
7. We have to repeat all steps for the next unique n-tuple of points and to find another type of condition that terminates varying of the n-tuples themselves (That's why we have to exclude scaling from p.2 - because we are risking to miss out one or more types of configurations, since we explore only limited set of radii).
8. At the end we have overall number of distinct configurations, described by our language of interactions.
As it turns out, this deceptively simple problem is time consuming nightmare to describe, program, calculate and solve. However, it's possible that more elegant and simple approach exists, but complexity of the problem is seemingly irreducible and quite visible with this approach, I think.
0:58 **Super Smash Bros theme gets increasingly louder*
Andrew P. Roberts circles in smash 👀
The "no kissing" rule bothers me. What is the reason for it?
If this problem is focused on circles, then osculating (kissing) circles and coinciding (having same center and radius) circles should be included.
If the problem is focused on topology (dividing the plane into pieces), than osculating and coinciding circles should also be allowed, since kissing circles can separate space differently. Consider three circles, two equal in size and kissing, and one twice the size circumscribing them and kissing. When arranged horizontally, the upper portion in the larger circle is separated from the lower portion by the kissing.
If the problem is focused on graph theory (counting intersections or nodes where the circles meet), then certainly osculating circles must be included. I might concede to let coinciding circles slide on this point.
I cannot think of a viewpoint where the "no kissing" rule is justified.
What is the sequence if you allow kissing? 1 for 1 circle and 5 for 2 circles (not counting coincident circles). I count 60 for 3 circles, but am not sure that I did not overlook any. How far is this known? So, 1, 5, 60(?), ...
4:16 it looks like Futurama Alienese
For 3 circles, I feel like there’s one missing that is possible. Start with a Venn diagram, then the third circle encloses one of the circles, and intersects the other circle. Isn’t that possible? I don’t see it at 3:35
did you mean configuration #11?
Would be interesting to see a 3d version using spheres, kind of reminds me of the orbital configurations of molecules...
I feel like we could get somewhere by graphing the middle points of those minimum possible circle size "intersection cases" to see which configuration of points are possible.
Music Professor?😲 Maths is truly for anyone.
Music is math.
I have a kind of upper bound. For six circles the number is less than 1.844674407371e19. For n circles, I believe there is less than 2^(2^n) configurations.