Pentominoes and other Polyominoes - Numberphile

[@numberphile]

See brilliant.org/numberphile for Brilliant and 20% off their premium service & 30-day trial (episode sponsor).

[@NekuraCa]

Why did you remove all comments with links to OEIS?

[@greensombrero3641]

I could solve it - but it's the holiday season and I had some Christmas wine, and I never drink and derive.

[@andreperlbach8324]

Said fermat

[@coaster1235]

Ok

[@ikocheratcr]

At least you did not run out of paper; so we might assume when you are back you will solve it, right?

[@Lolium-The-Atom]

Use paper left after opening presents if necessary

[@Uncl3M3at]

I have a truly marvelous proof of this, but this christmas vacation is much too narrow to contain it

[@nightshadefns]

What a lucky day to remember that Numberphile exists to be greeted with a fresh new video!

[@aukeholic1]

I would argue, that in 2-D, reflections are different because 'hands-on' you can only go from one to the other by going through the 3rd dimension

[@IceMetalPunk]

Not true: you can slide all the squares to the left of the vertical center right, and all the squares to the right of the vertical center left. It's pure math: the squares don't collide with anything because they're concepts, not physical objects, so they can just slide through each other 🙂

[@zmaj12321]

In that case, two triangles in 2D with the same side lengths should not be considered congruent if you must reflect one to get the other.

[@juliangilbey3924]

You're welcome to call reflections distinct or equal - as Sophie says about free/fixed, we have a free choice over this, and it gives rise to different numbers of polyominoes for n>3. Another question is whether polyominoes can have holes - first possible for n=7.

[@juliangilbey3924]

​@@zmaj12321 Whether they are or not is context dependent.

[@h-Films]

​@@IceMetalPunkthat breaks the polyomino up

[@theadamabrams]

Just in case anyone was confused at 6:21, the limit "C" is not the "c" from cλⁿ/n. In fact, it's exactly λ. So we do know for sure that there is a number λ such that lim_(n→0) Aₙ¹ᐟⁿ = λ, but from that fact alone Aₙ might asymptotically be cλⁿ/n or might be λⁿ/n² or λⁿ/log(n) or any number of other formulas that would still have the same limit for Aₙ¹ᐟⁿ, and we don't know which more detailed formula for Aₙ is correct.

[@hammerth1421]

This kind of problem reminds me of the chemistry problem of finding all the valid isomers of an organic compound. That quickly becomes a pointless exercise though as the number of options grows very quickly.

[@slowbro6871]

There is a boardgame called BLOCKUS that uses these, and its very fun

[@mathguy37]

omg i have that and a variation with triangles

[@jwolfe01234]

In Blokus, each player has one of each polyomino of size 5 or less. The video calls these free polyominoes because rotations and reflections are considered the same. As physical pieces, the polyominoes in Blokus can be rotated and reflected as desired before being placed on the board.

[@richardl6751]

Search for the puzzle "Hexed" from the 1960s.

[@PhilBagels]

Blokus, which uses polyominoes, up to 5, and Blokus Trigon, which uses polyamonds (made of equilateral triangles) up to 6. And there are other similar games. One was originally called "Rumis" but is now sold under the name "Blokus 3-D", and uses polycubes (up to n=4).

[@haukenot3345]

1:32 Am I the only one who needed this video to realize that this is why Tetris is called Tetris?

[@thekingoffailure9967]

Yes

[@haukenot3345]

@thekingoffailure9967 We both got two likes so far, so apparently neither am I the only one who didn't make the connection, nor are you the only one who did make it. Nevertheless, congratulations to you!

[@wayfinder1882]

what you called the "f" is called the r-pentomino in the game of life, where it is the smallest methusalem (ie a pattern with an uncommonly large lifespan)

[@livedandletdie]

Well it is known as the F pentomino, because all of the Pentominoes have a Letter associated with them. The I-Pentomino, the L-Pentomino, the V-Pentomino, the T-Pentomino, the P-Pentomino, the W-Pentomino, the X-Pentomino, the S-Pentomino, the F-Pentomino, the N-Pentomino, the Y-Pentomino, and the U-Pentomino Although I do agree that the F-pentomino does resemble a cursive r. But also so does the X-Pentomino... Especially if it's the lowercase r in the Sütterlin style of cursive. Or it's predecessor, Kurrent. Both of which are very rare to be able to read outside of Germany.

[@tolstoj_]

that depends on the nomenclature. There are multiple versions. F is correct, as is r.

[@AexisRai]

That's because Conway himself came up with those different names for certain pentominos (F I L N -> R O Q S) so the whole set now spans the end of the alphabet contiguously.

[@Lolium-The-Atom]

*presses f to pay respect*

[@wayfinder1882]

@@tolstoj_ very apropos profile picture!

[@Gipfer]

I learned about pentominoes from another book: "Imperial Earth" from Arthur C. Clarke. I didn't know there were multiple books that mention them.

[@OrangeC7]

Pentominoes are all the rage in works of literature, it seems

[@tolstoj_]

You might want to look at "Polyominoes: Puzzles, Patterns, Problems, and Packings" by Solomon W. Golomb

[@vinjarvederhus7678]

For me it was from yet another book - "Chasing Vermeer"

[@Gipfer]

@@tolstoj_ I have that book!

[@zanedobler]

@@vinjarvederhus7678 Same!

[@SolinoOruki]

This is so random but I love how she holds the marker writing - never seen anyone hold a pen/marker like that when writing

[@toolebukk]

This video is a gift! One year or so ago I dabbled with thisnexact thing, and never got anywhere and put it away and forgot about it! Thank you Soph!

[@MichaelPiz]

I immediately started thinking of the Soma cube. In a class years ago, I had to write a program to solve for the number of unique, non-rotated solutions to it. Fun!

[@summerlovinxx]

this honestly reminds me of the art gallery problem. it's hard to predict how a previous change might affect a future state, given the limitations on where each section can exist without repetition. I limited myself to using square cells, and the pattern Sophie showed popped up! repetitions aren't great, but reflections and rotations are the worst offenders lol. I'm personally partial to free form; the change in frame of reference is on the viewer, not the pieces themselves. we abritrarily determine what we think they look like, so it keeps the full list concise and readable.

[@adityakhanna113]

Sophieeeeeee. She's great. More of her thanks

[@adityakhanna113]

3:45 shouldn't there be something between fixed and free which considers rotations as equivalent but flips as different a la tetris? my dumbass commenting before the video

[@columbus8myhw]

Yes there should. The eight reflections and rotations form something called a "group", and the four rotations form a "subgroup." In theory you could ask this question for any subgroup. For instance, suppose we allow horizontal reflection and nothing else. Or just horizontal and vertical reflections, and the combination of these two reflections (a 180 degree rotation). Or just diagonal reflections and the combination (again the combination is a 180 degree rotation). These subgroups have size 2, 4, and 4 respectively (I'm counting the "do-nothing" action).

[@NekuraCa]

There is, they are called 1-sided polyominoes.

[@stechuskaktus8318]

Thank you, now I feel a lot better about not getting anywhere when I tried my hand at a Ponder This puzzle involving polyminos.

[@allthepeoplehere7524]

This made me think of chemistry and molecule formation. I wonder what sort of answer chemist might have.

[@sly1024]

They use quantum computing now to find molecules. 😂

[@owensthethird]

Chemist here. You could find some interesting results by defining some activation energies for combining two poly-ominoes. The "boltzman" constant for such a system may even be derived from the c, C and lambda introduced in this video. Very interesting thought there!

[@JeffDayPoppy]

Thank you for finally doing this video!!! I've been waiting 25 years to learn more about this.

[@Wald246]

1:22 It never occurred to me that the name "domino" comes from the same family of words!

[@neiltarrant7253]

I think the causation is kinda the reverse; dominos were named, and later it was interpreted as di-omino, thus suggesting triomominos, Pentominos, etc, but the actual etymology of domino doesn’t relate to the fact that there are two squares.

[@rosiefay7283]

Good question. As well as free (all rotations and reflections count as the same) and fixed (all rotations and reflections count as different), there is one-sided (think of the shape as having a front and a back; rotations count as the same but you are not allowed to reflect because that would put it back to front). You could also regard the unit as being not a square but an oblong (180° turns and horizontal and vertical reflections are allowed, but 90° turns and diagonal reflections aren't) or a rhombus (180° turns and diagonal reflections are allowed, but 90° turns and horizontal and vertical reflections aren't).

[@themasterofthemansion3809]

This video gave a really inspiring perspective for those exciting pieces and made me want to learn more about them.

[@MindstabThrull]

My first impression when I saw the number sequence thought maybe Fibonacci was involved somehow. No clue of course but the two 1's starting that way gave me that impression initially.

[@adityakhanna113]

Well kinda. If you only consider the family of free polyominoes where you can either have a column or width 1 or 2, those are counted by Fibonacci

[@przemysawkwiatkowski2674]

Do we allow for holes inside of the n-mino? For example "O"- shaped 8-mino? 🤔

[@Archanfel]

Yes, there are 369 octominoes, and "O"- shaped is one of them.

[@kingbirdy23]

Pentominoes are also a key part of the YA book "Chasing Vermeer", which is where I first learned about them

[@InclusiveDriving]

This reminds me of when my chemistry teacher challenged the class to find a formula to find the number of isomers of alkanes of the form C(n)H(2n+2)

[@BrendanGuildea]

That marker grip!

[@AlliSong-ux3hq]

Merry Christmas!

[@DarkAlgae]

because i'm a biologist, i associate the reflections with chirality and consider them different... but for some reason I consider the rotations all the same (possibly because Tetris allows rotation of the tetrominos). from a maths standpoint, am i right in thinking that this would be an arbitrary bias? or is there a mathematical hierarchy between reflection and rotation?

[@jsagovicj]

My first thought seeing the thumbnail was "Is this a Blokus video!?" You should do a Blokus video

[@HaraldHein]

Sophie's third drawing has an extra square :) Love the video, though, never stop Brady! Sophie's also great, have her on lots, please! :)

[@phyarth8082]

6:23 Asymptotically, the Catalan numbers grow as C(n)=4^n/(pi()^1/2*n^3/2)

[@willemvandebeek]

Merry Christmas, Brady & entourage! :)

[@_-KR-_]

this is my jam! tower defense and grid based building games have primed me for this.

[@ben1996123]

why is the camera rotated like 45 degrees from horizontal, it's horrible to watch

[@kdborg]

My father bought a couple pentomino plastic sets and they were fitting into a 6x10 rectangle. My father had a binder with solutions he, and others, had found. It always fascinated me because the package said a computer found 2,339 solutions for the 6x10 rectangle, ignoring rotations and reflections. I don't think we found them all.

[@rngwrldngnr]

3:45 Why are these values different? Wouldn't dividing the fixed polyominos up to n=70 into sets of 8 identical free polyominos be trivial?

[@buster2256]

You only have >up to< 8 rotations and flips. A square for example doesn't have 8. They would all be the same shape, so there's only one variation here. It depends on the symmetries in your shape.

[@GourangaPL]

If you like stuff like that there is a board, or rather card game released in Poland by Piatnik Company named DIGIT, it's pretty simple, 5 sticks on the table and cards with possible shapes on hand, simply move one stick per turn to make shape from your hand to get rid of it. Don't know if there were equivalents of it in other countries, i guess so.

[@ruilopes6638]

I’m glad I’m not the only one that one day thought about that and hit a wall. Seem so simple, but no pattern obviously emerge

[@adityakhanna113]

A lil fun fact about pentominos. The pentominos board game would inspire Tetris. Furthermore, the randomization used in NES Tetris is a Fibonacci linear shift register. Both of these were developed by Solomon Golomb

[@awebmate]

I looked it up on OEIS and it got the first 29 terms (including the zeromino).

[@evangonzalez2245]

Zeromino is probably correct, but I think I like non-omino better 😁

[@awebmate]

@@evangonzalez2245 non-omino it is then ;) i have no idea what the correct name is. Edit: I just realized that a nonomino is a 9-omino. Sorry :(

[@tubatim]

I’d strongly argue that chirality matters with these. Therefore at 2:57 there are only two shapes: the top left is the same as the bottom right, and the top right is different from the top left.

[@PhilBagels]

I've been fascinated with polyominos, and related shapes, since reading a few books by Martin Gardner as a child. I estimate I was about 11 or so. I even came up with my own counting/numbering scheme for all sorts of shapes like this. I'm not going to say it's too big to fit in this comment section, but it would be difficult to describe it using only text. It needs visuals. Maybe one day, I'll get around to making a video about it.

[@GARDENER43]

12 = 2x2x3 , raised its prime factors with the number being factored and sum them up then we got 2^12 + 2^ 12 + 3^12 is a prime. Is there other number with such property?

[@ErixTheRed]

If you've ever played the board game Blokus, you're very familiar with these

[@brenatevi]

There was another book which wasn't in the video or Arthur C. Clarke's book. The book I'm thinking about said that there were only 3 (?) ways for the pentominoes to fill up a 6X10 grid. I actually tried to map all of them using pentominoes made of legos.

[@rosiefay7283]

Quite an underestimate. There are 2339.

[@ceptimus]

Only two ways to fill a 3x20 rectangle using the twelve pentominoes.

[@petrospaulos7736]

This girl is amazing!!!

[@polyaddict]

I love biblically accurate tetris

[@lykhq496]

I think I have some way to count it manually, I tried it with 6 and the result was 33. It counts on resting the pattern while fixing some blocks in initial positions with the following conditions. You can not stack blocked more than the fix number of blocks. And you can not fix less than half of total of number of blocked or it will repeat. After that you can draw them and find it Manuel. Please reach me if further explanation is needed.

[@alvi9372]

would a sequence like 2, 3, 4, 7 or 2, 3, 4, 8 generate the same shape from the same starting square as the given sequence of 2, 4, 7, 13 ?

[@WombatSlug]

I also discovered pentominoes in a work of fiction, but it was Imperial Earth by Arthur C. Clarke.

[@davidteague2982]

Just realized where the name of the game Tetris comes from now. Mind blown

[@OfisAV]

just trued to find all the free hexominos and got to 25 shapes. idk im preaty sure 25 is the max of of free hexominos but im not 100% sure. but if so, the series is now 1, 1, 2, 5, 12, 25. do with it what you will

[@NekuraCa]

There are 35 hexominoes.

[@OfisAV]

@@NekuraCa then the search continues

[@adipy8912]

I hope Cracking the Cryptic does more pentomino puzzles. It's been ages

[@B.M.0.]

According to Wofram Alpha sequence solver this is the sequence (I haven't checked): 0, 0, 1, 1, 2, 5, 12, 34, 130, 525, 2472, 12400, 65619, 357504, 1992985, 11284042, 64719885, 375126827, 2194439398, 12941995397, 76890024027, 459873914230, 2767364341936, 16747182732792, ...

[@livedandletdie]

Seems very erratic.

[@evangonzalez2245]

Also where'd your zeroes come from? 1 way to make a non-omino, 1 way to make a monomino, 1 to make a domino...

[@B.M.0.]

@@evangonzalez2245 I understand I literally did not check anything just plugged and chugged so the next person had something else to go off. I noticed the zeros after posting and looked to see if someone posted the 6th-omino yet hoping it was 34. I did not generate the sequence, wolfram alpha (math resource) did, as I gave the credit in the first comment.

[@themasterofthemansion3809]

What are those leading zeros? I am afraid that you got you should check OEIS.

[@wiseSYW]

at least we know the highest upper bound is the number of ways you could place n squares in a n^2 grid

[@spindoctor6385]

It does not seem to make sense to me to count rotations as different shapes. If you do then why are only rotations of ninety degrees counted? I can rotate it 1 degree or 73 or 3.14159 degrees or any arbitrary number. The reflections make more sense when they have a chirality.

[@msolec2000]

She skipped about One-sided polyonminoes, which count reflections as different, and rotations as the same. That's how you get the seven Tetris pieces, for instance.

[@awebmate]

Nothing is being rotated, there is a number of ways to combine the blocks, and some of these combinations corresponds to rotations in units of 90 degrees. It doesn't matter if you count them as different shapes or not, it is just two different ways look at it, with two different results.

[@spindoctor6385]

@awebmate She literally calls them rotations in the video.

[@ernestoyepez5103]

She said 11 years ago y was 15... 11 years ago I was watching Numberphile, I am old.

[@mytube001]

If you think about these shapes as objects in a 3D space (which my brain seems particularly determined to do), i.e. squares (or cubes) attached together, then reflections are just rotations "in the plane", and rotations are the same shapes even in 2D. And by "same shapes", I mean that they don't have to be distorted or disassembled/reassembled to change, but remain rigid objects throughout.

[@Lolium-The-Atom]

What about infinite dimensional version of polyominos? (lets call them polyomegos) despite having infinite choice of dimensions your cubes may be, for finite polyomegos (eg monoomegos, doomegos, triomegos, tetraomegos, pentaomegos) you have finite amount of cubes in total and thenfore you have finite amount of free polyomegos due to n-omegos being able to fit in (n-1) dimensional space

[@mytube001]

@@Lolium-The-Atom My brain only works up to three spatial dimenions. Your mileage may vary.

[@Lolium-The-Atom]

@@mytube001 I'd like to recommend you dimensional stack that might help as a fuel in your miladge. its basically a method where you fit higher dimensions onto lower dimensions space. For us 3 dimensional creatures seeing in 2 dimensions we can fully see dimensions with 1 dimensional or 2 dimensional stacking where 2 dimensional stacking is preferred. You may imagine smth like Minecraft building tutorial. You want to rebuild some structure 1 to 1. what do you do? you show them 2 dimensional slices of your building ofc. to visualize 3x3x3 (27 cells in total) cube you draw this ooo l ooo l ooo ooo l ooo l ooo ooo l ooo l ooo each square represents one slice. you can also label coordinates for the cube representations like this: 1 2 3 ____________________ 123 123 123 1 ooo l 1 ooo l 1 ooo 2 ooo l 2 ooo l 2 ooo 3 ooo l 3 ooo l 3 ooo here i labeled each dimension: x axis labeling rows, y labeling columns and z axis labeling squares great... but what about 4 dimensions? lets try to visualize 3x3x3x3 (81 cells in total) terrasect (cube but 4d): ooo l ooo l ooo ooo l ooo l ooo ooo l ooo l ooo _______________ ooo l ooo l ooo ooo l ooo l ooo ooo l ooo l ooo _______________ ooo l ooo l ooo ooo l ooo l ooo ooo l ooo l ooo its the same as one before but insead of having 2d slices of 3d object we now have 3d slices of 4d object. Here the 3d slices are stacket on top of each other. This is because we are doing 2 dimensional stacking and so we exhangedly use rows and columns to place higher dimensional slices. for 1d stacking we would just use rows and for 3d stacking we your use rows, columns and depth exhangedly here is labeled 3x3x3x3 terrasect: l 1 2 3 l 123 123 123 l 1 ooo l 1 ooo l 1 ooo 1 l 2 ooo l 2 ooo l 2 ooo l 3 ooo l 3 ooo l 3 ooo l _____________________ l 1 2 3 | 123 123 123 l 1 ooo l 1 ooo l 1 ooo 2 l 2 ooo l 2 ooo l 2 ooo l 3 ooo l 3 ooo l 3 ooo l _____________________ l 1 2 3 l 123 123 123 l 1 ooo l 1 ooo l 1 ooo 3 l 2 ooo l 2 ooo l 2 ooo l 3 ooo l 3 ooo l 3 ooo to do 5d you just make copies and place them in a row, to 6d place copies in a column again ect ect Thanks for coming to my TedTalk

[@LimeGreenTeknii]

You say free vs fixed, but I know Tetris considers reflections of tetrominoes as different but not rotations, since you can rotate pieces in game but not reflect them.

[@mimasweets]

Shoutouts to The Crimson Binome.

[@Niramlshortsman]

Amazing work

[@carterwegler9205]

I love her and Ayliean!

[@DeathSugar]

But what about lower bound? Is it bigger than e? sqrt 2? phi?

[@andrewkepert923]

The formula at the end can be used to get various lower bounds. For example A_{5n+k} >= 12ⁿ A_k

[@DeathSugar]

@andrewkepert923 and your example would be greater than the upper bound at many points

[@firdacz]

2:02 "what are they?" so poorly communicated that I did not even get the problem (and I won school competition in 1997 demanding to arrange them in a rectangle... by finding "slicing" that can be rotated, thus multiplying the number for the lack of propper definition and understanding of the problem by the teacher)

[@Matthew-bu7fg]

If we're unsure about our reflection in the mirror, is it known as the pentomino effect?

[@eternaldoorman5228]

1:25 So they're the same when they're flipped upside-down. Otherwise there would be two L-shaped ones. ... 2:46 oh, you spotted it too.

[@lovefanye]

2:10 the L piece has 6 squares...

[@toonkrijthe7565]

The answer is "we don't know" --> quest unlocked.

[@mygills3050]

I think Jan Misali did something vaguely related to this. Not sure where or what though. Maybe i'm misremembering it.

[@AlliSong-ux3hq]

So the number of 10 sided polyominoes is going to be huge

[@98.11Deet]

I always felt rotations are the same, reflections are not. I played Tetris.

[@ShawnHCorey]

The way to solve it is to find a way of generating only unique n+1 nominoes from n nominoes. That is, the same nominoes is never generated twice.

[@timfulford9395]

OEIS.... Compare A125761 (triangles) with A00105 (polyominoes).... I don't have my computer, but they look similar in various places ... could be a link.....

[@HenriFaust]

0:53 It's a cursive, uppercase "F" BTW.

[@yuGesreveR]

I have solved it. I have discovered a truly marvelous formula of this, which this margin is too narrow to contain 😂

[@TheDentrassi]

Is this also a packing problem?

[@WriteWordsMakeMagic]

I have a truly marvelous function that calculates the number of free n-ominos that this comment section is too narrow to contain

[@FLPhotoCatcher]

Proof, or it didn't happen.

[@rtpoe]

OUT!!!! -------------------->

[@crazydog1750]

So interested to have some more insight into the mathematics of the game “Blokus.”

[@wtfpwnz0red]

I wonder why mirror versions (opposite chirality) don't count as unique entries in these lists

[@Bthehill]

Wouldn't it be possible to at least estimate the number of 6 square polyominoes based off of the unfoldings of a hypercube? It should be equal to or (probably) less than the number of 6 cube unfoldings, since they are essentially polyominoes in 3D.

[@nekogod]

Which is why tetris is called tetris, because it's all tetronimoes

[@Chrisuan]

I will never not click a Sophie video

[@mal2ksc]

"Kinda looks like an F, maybe". Look at the headstock of a Fender guitar, or the badge on the grill of an amplifier. You'll see the characteristic "backward F".

[@InfiniteWithout]

Arrangements of n nodes

[@AlliSong-ux3hq]

It's so interesting

[@incription]

I like the old thumbnail more

[@Timebug22]

Hell yeah, Pento!

[@VectorMonz]

Makes me think of "group theory".

[@VerucaPumpkin]

Thought this video was going to be about BLOCKUS (fun game you'd like it).

[@sdspivey]

I can solve it, but I don't want to ruin your chances to discover it yourself.

[@zmaj12321]

Everyone always says the f pentomino doesn't look like an f... but it looks pretty close to a lowercase f in my opinion.

[@nilsbottjer7129]

I haven't tried brilliant, but somehow the adverts always look like a mix between a bad mobile game and content childrens learning content 😂

[@zmaj12321]

As someone who used to use it a lot, I do genuinely believe it's quite nice. The questions they ask you aren't softballs! But I stopped using it after they stopped posting weekly community problems some years ago.

[@SS-pq9ci]

cool stuff

[@k5555-b4f]

no Gameboy in that one - what has the world come to

[@sly1024]

You can tell she's a mathematician because she used bottom-left and upper-right. A computer scientist would have used top-left and bottom-right. 😊

[@gabor6259]

Now take this problem to 3D.

[@deltalima6703]

Pro tip: If you make a game out of these, dont call it "pentis"

[@themasterofthemansion3809]

I can see that t dropping...

[@iTeerRex]

Yey some Tetris maths 👍

[@IceMetalPunk]

"When I was 14/15, I read about this geometric concept in a book, and quickly started trying to generalize, until I asked my teacher about it." And that's what we call a born mathematician! (Not to be confused with a Bourne Mathematician, which is what happens when Matt Damon teaches high school.)