Comment by f154hfds | Hacker News Reader

Comment by f154hfds | Hacker News Reader

I have a duplo/lego question - is there a name for the combinatorics problem of how many structures can be built with N 1XM legos? I have spent a fair bit of time thinking about this problem and I'm unaware if it's been posed elsewhere.

Any piece able to freely rotate is considered the same structure. For example, for 2 1X2 legos the arrangement count is 2: top connected to bottom with both nubs, top connected to bottom with one nub because if you analyze legos you will find that such an arrangement can freely rotate over 270 degrees, and left vs right nubs result in the same structure when taking rotational symmetry into account.

For the problem I assume an 'ideal' lego with 0 manufacturing tolerance, no illegal building techniques are allowed.

Is there a name for the above combinatorics question? Is it well-posed?

Is there a closed-form solution? If not is there a generator program?

I should say that with a high enough N any generator would be very complex - imagine how degrees of rotational freedom give rise to the possibility of further structures hidden from other rotational orientations.

Look into the work of Søren Eilers

https://arxiv.org/abs/math/0504039

https://www.tandfonline.com/doi/abs/10.4169/amer.math.monthl...

(for the latter: use sci-hub)

Then there is also work for the 2D case by Tricia Muldoon Brown:

https://www.sciencedirect.com/science/article/pii/S0012365X1...

https://arxiv.org/abs/1608.01562

as well as by Alexander M. Haupt:

https://arxiv.org/abs/1810.10428

For questions like this one I like to check the: https://oeis.org/ Compute the first numbers in the sequence by hand and then see if they're already in the database.

I like to do the same kind of experimental mathematics:

1. Write a Python script to brute force the first values of the sequence.

2. Search oeis for that sequence.

3. If (2) fails, simplify the problem and repeat.

Sometimes you get a completely unexpected connection that you would never have come up with yourself just by thinking.

For your first question, I don't know for sure but we called these "counting problems" when I worked with lattice models in protein structure prediction. See https://en.wikipedia.org/wiki/Lattice_protein for context and we spent a lot of time eliminating solutions that were identical after rotation, and self-intersections (there's a suprising amount of exciting math associated with determining if a chain specified using local angles intersects with itself in absolute 3-space.

I'll be up front and admit I failed combinatorics once (by far my least-strong math), but I'd start researching in the chemical compound enumeration space.

It's a similar problem (restricted attachment points, 3d double-counting).

E.g. https://math.stackexchange.com/questions/237998/p%C3%B3lya-s...

I have no useful answer for you, but when you allow continuous rotations, doesn't it stop being combinatorics?

You've got it backwards: in this case, if a piece can rotate, all of its possible positions count as the same configuration. In other words, the problem is posed in such a way that we can ignore the fact that pieces can (sometimes) have the freedom to rotate.

It's that last paragraph that makes me wonder:

> imagine how degrees of rotational freedom give rise to the possibility of further structures hidden from other rotational orientations.

That sounds like a basically continuous question, not discrete. But maybe I misunderstood.

If we only allow the pieces to mate in the official manner, at right angles, then it’s still a combinatorics problem with an finite integer answer. There’s an extensive tradition of picking out discrete subfamilies out of continuous things and studying them with discrete tools—symmetries of polygons, tilings, regular polyhedra, crystalline lattices, etc., are all in that group (no pun intended).

On the other hand, just because your problem sounds discrete doesn’t mean that the continuous toolkit isn’t going to be useful for it, as the inordinate utility of generating functions[1] (closely related to Fourier transforms) shows. The other way around also works, with the theory of smooth symmetries (Lie groups) making good use of the discrete things I mentioned above.

It’s all a single field, as Bourbaki wanted to point out by ungrammatically naming their course Éléments de mathémathique (not -es). Even if they omitted some significant parts of that fields that they didn’t know properly or weren’t well-developed yet (e.g. logic counts as some of both).

[1] https://www2.math.upenn.edu/~wilf/DownldGF.html

I did a little python script some time ago to solve just problems like this. It is meant to be more educative than fast, though, and doesn't handle non-right angles (like pytaghorean triangles). It turns out that eliminating duplicates is a little tricky: https://github.com/filipezf/BrickEnumeration/blob/main/brick...

There is a display about the case of 6 1x4 bricks at Lego House in Billund.

It's beside a machine molding 1x4 bricks and packing 6 of them into a bag which you can take for free.

That's quite neat! For anyone else who's interested, I found a video of this online[1]

1: https://www.youtube.com/shorts/iKs_zr6_qMg

I love this

You could use this sort of stack of lego bricks to physically-encode low-entropy passwords.

Huh. You can't rewind/fast-forward/seek these "shorts" videos. (Well, I can't, with my particular browser/os/county/screen-dimensions/etc combo.)

Reply on news.ycombinator.com