0
$\begingroup$

Let's suppose I have Big Cube of x cm by y cm by z cm, simmilar to this one: enter image description here

This big cube is made of tiny little cubes of t cm.

All of this little cubes are transparent, but some of them are red

How many arrangements of little red cubes is it possible to do?

I think this is a permutations with repetition problem, and so far, this is the equation I came with:

$$ a= ( \sum_{n=0}^{A} P_{A}^{A-n,n} )^Z $$

Where:

$ a= $ Number of possible arrangements

$ Z= $ Value of the number of layers equal to $z/t$

$ A= $ Area of each layer equal to $(x/t)(y/t)$

$ P_n^{n_1,...,n_r}=$ Notation for Permutations with Repetition

So, for example, if it is used the values of the example, it is obtained this:

$$ a = ( \sum_{n=1}^{64} P_{64}^{64-n,n} )^8 = (18,446,744,073,709,551,616)^8 $$

But my problem is: How many arragenments of little cubes can I do, so that the all the red cubes touch each other, so that there is no isolated geometries?

For example, this one is valid, it is only one geometry:

enter image description here

This one is not valid, there are two shapes separated:

enter image description here

I suppose that the orginal formula, must have a term that gets rid of the cases with Isolated Shapes

$$ ( \sum_{n=0}^{A} P_{A}^{A-n,n} ) ^Z - (IsolatedShapes) $$

What's the value of that "IsolatedShapes" Term?, Could you give some ideas of how to tackle this problem?

Improve this question
$\endgroup$
4
  • $\begingroup$ Exact enumeration of connected shapes is a challenge. You might liken it to graph enumeration of graphs of bounded degree, with additional properties like being bipartite and connected (let vertices be cube centers, with an edge between adjacent cubes). There should be tables of earlier attempts on the web. Gerhard "Is Confronting Other Challenges Presently" Paseman, 2020.05.09. $\endgroup$
    – Gerhard Paseman
    Commented May 9, 2020 at 18:59
  • $\begingroup$ But at least, Do you know if my formula for the General Case is correct? $\endgroup$
    – Nau
    Commented May 9, 2020 at 22:00
  • $\begingroup$ I am unsure about your formula, as I do not understand it. One has an upper bound of 2^(Z^3) by considering subsets of cubes, but this assumes no symmetry collapse (e.g. there are Z^3 many figures, each with exactly one cube, in a different positions) and counts disconnected arrangements. You might find counting connected arrangements in a layer just as challenging, but then you could use that for tighter approximations. Gerhard "Go Ahead: Try A Slice" Paseman, 2020.05.09. $\endgroup$
    – Gerhard Paseman
    Commented May 10, 2020 at 0:41
  • $\begingroup$ This reminds me a lot of the enumeration of LEGO structures, a famously difficult problem. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented May 12, 2020 at 9:12

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .