A Math Problem
Permutation: “one of the ways in which a number of things can be ordered or arranged.”
Collins English Dictionary
Update: WOW- Thank you everyone!
This math problem was an order of magnitude larger than I imagined, thank you everyone for sharing your time and expertise. To all of you who participated, I’ll be in touch soon. If you haev any more updates to the problem, please comment below! Thank you, again!
Ever since introducing Mini Pans back in 2017, I’ve been amazed at the many different ways Pocket Palette owners have been customizing their palettes using our stainless steel watercolor pans. After scratching our heads about this around the shop, we’d really like to know–how many permutations of our four sizes of pans are possible in our standard Pocket Palette?
We’ll give the first three people who show us proof–or at least a good enough argument to convince us–a free Essential Colors Pocket Palette and a water brush.
Rules and guidelines:
- Any combination of our four pan sizes is allowed, so long as there are no empty spaces left over.
- Different arrangements that use the same combination of sizes should be included (such as left-handed and right-handed variations), as they offer distinct experiences.
- The Pocket Palette fits 28 mini pans in a 4×7 grid.
- 1 Standard Pan = 2 Mini Pans.
- 1 Double Pan = 2 Standard Pans side-by-side, or 4 Mini Pans in a square.
- 1 Large Pan = 2 Double Pans, 4 Standard Pans, or 8 Mini Pans as pictured below.
Happy calculating!
41 Responses to “A Math Problem”
Kat
Infinite. No matter how you arrange the pans, of which there are numerous ways, you can always rearrange and change the colors in said pans. This, as you stated, creates a new unique experience. With all the variations in shades, you could be creating new palettes for the rest of your life.
Martha
The question is : “…how many permutations of our four sizes of pans are possible in our standard Pocket Palette?” The question doesn’t involve changing colors… they either remain the same colors or they’re empty.
Patricia
Brings to mind a rubix cube.
Kat
Though, I suppose if you’re looking for a mathematical proof, we can break out the factorials 28! + 14! + 6! + 3!, not sure about the other bits…it’s been awhile since math class. That would be 3.0488834e+29 at least.
Carl
Kat,
I think you are over counting. 28! would reflect the number of ways you can arrange 28 unique 1×1 pans, but I believe that the intent of the question is to consider each 1×1 pan identical.
So, I think you need to count the number of different combinations that could fill the pan from:
28 1x1s = one arrangement
26 1x1s, 1 1×2 = 21 + 24 = 35 arrangements
….
…
3 2x4s, 2 1x2s = at least 14 arrangements
xavier
Oh this is tricky.
I tried first to think like that. Ok lets have 3 mixing pans and a remaining column.
The column can be 4 minis, 2 standards or 2 minins and 1 sandards with 3 alternate positions . So 5 different rows.
The mixing pan and rows can be arranged ten ways (accounting for vertical, horizontal, and switching positions of the row and vertical mixing pan.
So we already have 10×5= 50 possibilities.
Then you can start to replace 1 mixing pan with doubles (3 ways because 3 pans). Or 2 mixing pans with doubles (also three ways. Or 3 mixing pans with doubles 1 way. Total 7 possibilities.
50×7=350.
Little problem. Some of those combinations are identical. But let’s forget about that for a while.
then we can continue and switch doubles with standard. Some of them. and combine. Then we get an extra 30000 combinations or so, added to the 350 previous (trust me, with care).
And then we continue by switching the standard with minis. Eventualy come cases will be identical if we branch out but who cares.
This step probably give us two more orders of grandeur on the total so I am guessing that we have close to 3 000 000 possibilities.
And this does not account for standard and doubles being able to be in between rows. And in between columns.
So you probably have to add a couple of millions of possibility for that.
I will guess 5.
That’s it, i wont be able to sleep now.
One way to solve this would be to the same reasoning but program this, so that for each solution found, the computer can keep track if it is already present through one other branch. Should be feasible.
My head is smoking now.
Maria
Oh, wow! I’m fascinated. This is bigger than I expected!
Carl
If you want to sell pre-made *sets* of pans that will fill the palette, you will need 116 SKUs to cover every possible configuration. Then it will be up to the purchaser to figure out how they want to arrange their sets. I haven’t figured out a reasonable way to compute all the different ways of packing the different configurations.
Xavier JULLIA
This Problem is facinating. :).
Ok I still don’t knlw how to calculate how many combinaison there is but at least i found a way to calculate what it can’t be above.
If you separate lines and columns.
A combinaison in lines can be for example 1+1+1+4 or 2+2+1+2 since it must add up to seven.
seen all combinations of 1 2 and 4s and adding order you end up at max 31x31x31x31 (because 4 lines with 31 combinations each).
Doind the same for colums of 4s you get 6x6x6x6x6x6x6 (because 7 colums with 6 combinations each.
In the end if you multiply the two number you get 923521×279936
which is 258 526 774 656 variations.
And this is way over the possibilities of the real problem. Since all combinations of 1 2 and 4s are not independent. They depend on the shape of the pans. Even number of combinations row to row and colums to colums are much more limited. So it’s probably safe to say that you can divide by 10 or more.
Terica
There are 116 possible combinations of sizes, however there is no way I’m aware of to calculate the various left/right/top/bottom/diagonal options available.
Susan
It won’t be infinite, as we are only looking at combinations of pans and not taking different colours into consideration.
And the minimum is four, for just using one type of pan in the palette. I’ll have to go think about this one a bit more.
xavier
line 1 you can have mini, std vertical or horizontal, multi and mixing vertical or horizontal. Combining carefully that makes 1704 possibilities for line 1.
line 2 and three you now can exclude vertical mixing pans. So we end up with 964 possibilities on each of those lines.
Line 4 you can exclude also multi and vertical std and horizontal mixing. So only 21 ways left.
1704x964x964x21 gives
33 253 928 064 possibilities.
Of course this is a maximum possible number. A lot of possibilities have to be excluded. for example if you have a multi or any vertical on a row the possibilities for the next row are affected. So maybe as much as half the cases are invalid.
Getting closer. :)
Arnaldo
Minimum pans on the palette with no empty spaces left over is 5 (3large + 2std)
Maximum permutation for a large pan equivalent size is 10 (1 large + 2double + 1double/2std + 1double/1std/2mini + 1double/4mini + 4std + 3std/2mini + 2std/4mini + 1std/6mini + 8mini).
Maximum permutation for 2 standard pan equivalent size is 3 (2std + 1std/2mini + 4mini).
Maximum permutations possible of the four sizes of pans in a standard Pocket Palette is therefore 3000 (10x10x10x3).
I think.
Arnaldo
Ooops, I did not read well the rules!
Different arrangements that use the same combination of sizes multiply the number of possible permutations…
Arnaldo
4194304
Considering different arrangements that use the same combination of sizes we have 64 possible permutations for a large pan equivalent size.
We can have 3 large pans, therefore 64x64x64=262144
The remaining half large pan equivalent size can have 4 possible combinations multiplied 4 possible raw positions (right, center-right, center-left, left), that is 16 variations.
262144×16=4194304
Hopefully…
David Jinkins
Hi Maria, very cool combinatorics problem, also one which, like many combinatorics problems is difficult and tedious to solve. I can give you a surprisingly high lower bound, though. First, let’s only consider the “dominos”, the 2×1 pieces, and the “singletons”, the 1×1 pieces. There is a really cool and surprising formula involving cos and pi for counting the number of domino tilings on a given rectangle (http://math.uchicago.edu/~may/REU2015/REUPapers/Borys.pdf). For your 7 x 4 rectangle, it turns out there are 781 domino tilings. Without double counting we can replace each of the fourteen dominos with singletons in each of the tilings to get 781 * 14 = 10934 more permutations. Continuing with this method, we can replace any two dominos (14 choose 2 = 91 ways), but we have to be careful to avoid double counting, since two adjacent vertical and two adjacent horizontal dominos will be replaced the same way by singletons. To get a conservative lower bound, we can divide by two, yielding 781 * 91 / 2 = 35,535 more permutations. Continuing with replacing three dominos with singletons, to avoid double counting we can get a lower bound by dividing by three. This gives us an additional 364 * 781 / 3 = 94,761 more permutations. Continuing with 4 dominos, I get a lower bound of 1001 * 781 / 5 = 156,356 We could keep going, but I get less confident about the right number to divide by to avoid double counting. In addition to this method, we can go the other way and place a single domino (with everything else singletons) in 45 different ways. If we place two dominos, we need cases. Following the method described here for a chess board (https://math.stackexchange.com/questions/2555783/chessboard-8-times8-and-domino-1-times2), we get (41 * 8 + 40 * 10 + 39 * 14 + 38 * 13) / 2 = 884 more permutations. Of course you could keep this counting going, but you can see it is going to get tedious fast. Adding together all the numbers here, you have a lower bound of more than 250,000 permutations just with the singletons and dominos, and I guess the actual number is one order of magnitude larger.
Maria
Wow! Thanks for breaking that down so clearly
Arnaldo
NO WAIT! It is the double of that… I was considering only rows.
There are still 4 possible combinations of the half large pan equivalent size!
Those are splitted to the sides of a couple of horizontally positioned large pans, either with the remaining large pan to the right or to the left.
That means the possbile positions of the half pan equivalent area are not 4 but 8, which multiplied by the 4 possible combinations results 32.
Therefore 262144×32=8388608
I hope this is my last post… :-)
Maria
Thank you so much for all of your ideas and calculations!
Arnaldo
OK, it was not my last post: I admit I’m haunted by this… :-)
There is still a combination missing in my previous calculations, and it is when 2 of the large pans are horizontally placed.
In this case we have valid permutations (no duplicates) only when one of the two large pans area is filled with a large pan (and this happens only twice), as soon as we split it, we start getting duplicates (relative to the vertically positioned large pans), so we have to add to the previous calculation a
64 x 64 x 2 = 8192
(I think we have some duplicates even if the two horizontally positioned large pans are offsett, but only when we come to a much higher split rate, AND it’s hard to calculate those)
Anyway these 8192 permutations need to be multiplied for the possible positions of the two standard pans equivalent area, which in the case of two horizontal pans is 3.
Therefore 8192 x 3 = 24576
Which added to the previous makes a total of
8388608 + 24576 = 8413184
…minus the aforementioned duplicates…
Sigh!
Diana
This is beautiful. The exquisite little video is beautiful- how the big pans entering the palette do so in time with the music and then the visual delight of the pans arranging and changing. Imagining my friends (Darin and Maria and Nika) sitting around puzzling with it in gorgeous Port Townsend under Northwest Winter skies that are so beautiful in my mind, and hopefully, somewhere in there, warm ceramic cups of coffee and tea, held by hands I love. And finally, the math challenge. The beauty of the number challenge itself and the attempts at formulas, the flaws of the formulas, the math-just-for-fun-ness of it all. The jolt of pure human curiosity I feel and share with other humans, and all of it on Valentine’s Day. Beautiful. Just beautiful.
Maria
Sending you love, Diana!
Deane
I really like Carl’s entrepreneurd answer of 116 SKUs.
This gets out of hand fast, so I’ll try starting with the easy part. Here are the numbers of combos that could fit in each of the pans (including the pan of that size itself).
1 = 1×1
2 = 2×1
8 = 2×2
81 = 4×2
The 4x2s are a bit tricky. There are 8 kinds of 2x2s, and each can stack on each to form a 4×2, so that’s 64. But there are also 4 kinds of 4x2s with a 2×2 in the middle, and there are 4 kinds of 2x2s with at least half the middle horizontal unsplit, so that’s an additional 16. Plus a single 4×2 by itself, of course. So that’s:
81 = 64 + 16 + 1
How many full kit arrangements include three 4x2s? There are 10 with a full-height column 1 wide, and 4 with half-columns 1 wide. There are 5 ways to organize a full 1-wide column and 4 ways for a 1-wide column split in the middle, so that’s:
66 = (10 x 5) + (4 x 4)
So, the total kit arrangements so far are:
4 x 10^7 = 66 * 81^3
An argument could be made that I should now add up the number of kit arrangements which include at most two 4x2s (i.e., a third 4×2 won’t fit due to the placement of the 2x1s), and multiply that by 81^2. Then do the same for the kit arrangements which include at most 1 4×2 and multiply by 81, and then add those in which not a single 4×2 will fit. However, I should also subtract duplicates from the set with three 4x2s, e.g., everything with adjacent vertical 4x2s that contain only squares will have a duplicate when the 4x2s are rotated 90 degrees.
But, those adjustments won’t change the highest order exponent in the calculation. Therefore they won’t change the order of magnitude of the answer or even the significant figure.
Maria
Hi Deane!
Thanks for chiming in. Ok, so 66 * 81^3= 35,075,106! Wow, this is an order of magnitude more than I was imagining when we started to think about this little problem.
Maria
And I just can’t stop laughing at
“entrepreneurd” 😆
Mali
We’re just counting EMPTY pans right? cause with colours….*brain explodie*
Maria
Yes, just empty. I think there’s infinite possibilities with colors!
Arnaldo
Well… unless there are infinite colors there are not infinite possibilities, only very very very high…
Oliver
A fascinating problem, indeed, and as a software developer I’ve tried to approach it with the tools of my trade.
Unless there is an error in my reasoning or a bug in the final program, we are looking at about 40,800,000 possible combinations.
I have manually verified the algorithm for a hypothetical 2×3 “Tiny Palette” which allows for 26 permutations (using only Mini, Standard, and Double Pans, as a Large Pan would not fit), but will have to perform a few more tests to be sure.
For the 4×3 Demi Palette, by the way, the result is only a “meager” 1,135 possible combinations. That seems very low compared to almost 41 million for the Pocket Palette, but that’s the way exponential problems behave.
I will send a private message with the exact number and an explanation of the algorithm once I’m confident in the numbers. :)
Maria
Thanks for exploring this problem! 30,000,000-50,000,000 has come up a few times, now I’ll be interested in your explanation! Good to know for the Demi Palette! 1,135 is a number I can wrap my head around. 😆
Kelly Darpinian
My son wrote a program to calculate it here: https://james.darpinian.com/pocket-palette.html. It’s a VERY large number!!!
Maria
Wow, so cool! We’ll review it and let you know if we have any questions!
Oliver
Now, with the cat out of the bag, I can confirm the number calculated by Kelly’s son. My approach is similar, yet somewhat less elegant.
The Python script can be found (and run) at
https://pyfiddle.io/fiddle/81d3cab6-02c1-4b9f-85c5-26a67d07bd68/?i=true
It is currently configured for the Demi Palette (see first line) to get a reasonable runtime.
Calculating the value for the Full Palette took my development machine about 30 minutes and is not possible on the web interpreter, probably due to artificial restrictions to prevent people from using too much computing power.
Xavier
Well done to the computer solutions! :)
I am still trying to find an analytical solution to this. I think i am going crazy. I basically barricade myself this weekend.
An approach i find would be ta catalogue how you can complete smaller parts of the pavement.
For example how many combinations for a column of width 1. (5). How many combinations for a 2 by two square (9.including double pans.
So 2 by 4 colums can be made of 9×9 combinations plus a double pan. so 82.
Naxt step would be colums of 4.
4×4. Since we already catalogued 2 by 4s. then we have 82×82 and we would have to acount for rotation so 82x82x2.
so now we can reduce part of the problem. we only have to get combinations of variations of columsof 1, colums of 2 and colums of 4. in a line of 7.Which is really doable.
Then we still have to catalogue all the imperfect line. When a pan is between two lines. The thing with this type of arrangements is that we already cared about the vertical cases in the previous catalogging. so we only need to do the horizontal overlapp cases. They will have complementary forms. but each complementary for will have variants.
the minipans cannot overlapp.
possible overlaps: standars, standards and doubles will involve 3 columns.
Etc. Hard to explain without paper.
Anyway. this will create blocks of 3 by 4, 4 by 4 up to 7 by 4 for mixing pans, where all the variants are really possible to catalogue and find.Then we need to combine them in the grid of 7 by 4 as done above for perfect rows. Which is verry very tedious but still doable.
But there is still a last animal i cannot really dompt. we might have a multitude of horizontal overlaps. For example, the catalogging above still does not account for a pavement of overlapping horizontal standards. I guess there is a way to find a general way to catalogue and combine basic overlap forms in grids of 3, 4, 5, 6 or 7.
And then complete the remaining spaces with perfect lines.
Now i will take some time off work. I cannot rest until i find paper solution to this.
The computer brute force solutions were very well done though. Congrats :)
Arnaldo
A 2 by 2 square hosts only 8 permutations INCLUDING the double pan:
1) 1 double (2×2)
2) 2 std (2×1) vertical
3) 1 std vertical + 2 mini (1×1) on the left
4) 1 std vertical + 2 mini on the right
5) 2 std (2×1) horizontal
6) 1 std horizontal + 2 mini on the upper
7) 1 std horizontal + 2 mini on the lower
8) 4 mini (they are squares, horizontal or vertical does not matter)
HOWEVER a 2 a by 4 area hosts 64 permutations (8 x 8), INCLUDING 2 double pans (since a double pan is already in the 2 by 2 area count of 8) but PLUS 1 large pan, hence 65…
So I have to redo all my calculations! :-((
Luis
Hello María
I just wanted to know how long will be open the “competition” since the longer we study it, the more complex becomes, and we need some time to do a proper approach and try to solve it properly.
That’s all. Nice problem and nice palettes.
All the best
Luis
Astrid J Beyleveld
Yeah there are way too many for me to even imagine but I could imagine playing with designs by using the pans of colors as mosaic blocks and making designs like you did the heart. No that would be fun. Math hmm that is why I married my hubby. I take all the math things to him and say honey I need this to do this. He often worked out skirt patterns to suit my cloth or even how much fabric I needed for the quilt. Those sort of things. Me I would spend days playing with which colors to put into it.
Martha
It’s really simple.. lol
The size of the tins doesn’t matter.. The answer is 43! (43 factorial), which is equal to : 6.0415263063374E+52
Martha
Ignore my answer.. I didn’t read the question close enough!
Vikki
I’ve just found this and you are all wrong. It’s 42. Why? Because 42 is the answer to life, the universe and everything (ref Douglas Adams) 😉
Maria
Ha! Thanks for sharing, Vikki. 😘