The hottest Combinatorics Substack posts right now

And their main takeaways
Category
Top Science Topics

“Lights Out” on a triangular grid

A Piece of the Pi: mathematics explained • 30 implied HN points • 22 Mar 26
🔬 Science Combinatorics
  1. The triangular Lights Out game reduces to linear algebra over the field with two elements: pressing a button toggles bits mod 2, pressing a button twice cancels, order doesn’t matter, and any solution is a subset of buttons pressed once.
  2. Solvability and uniqueness depend on the kernel of the toggle map: if the kernel is only the empty set (ℓ=0) then every starting state has a unique solution, which occurs for certain side lengths such as 1, 3, 4, 7, 8, 9, 11, 15, 16, 17, 20, and 21.
  3. If the kernel is nontrivial (ℓ>0) there are nonzero button patterns that have no effect and some starting configurations cannot be solved; the kernel is a 2^ℓ-sized vector space over GF(2) and its patterns often form visually striking shapes like the Sierpiński triangle.

Colouring identical cuboids

A Piece of the Pi: mathematics explained • 30 implied HN points • 30 Dec 25
🔬 Science Combinatorics
  1. The number of colours needed depends on the cuboids' sizes and orientations; even with all pieces aligned, some stacks need five colours (2×2×1), others need four (3×1×1) or three (2×1×1).
  2. Letting identical cuboids meet at right angles in the same plane can raise the colour count — for example, 2×1×1 blocks in mixed planar orientations can require five colours.
  3. Allowing arbitrary orientations makes the problem harder: some constructions with 4×1×1 cuboids force at least six colours, there is a proven upper bound of 12 in that case, and it’s unknown whether six is the true maximum overall.

How Researchers found Gods Number[Technique Tuesdays]

Technology Made Simple • 139 implied HN points • 22 Nov 23
🔬 Science Combinatorics
  1. God's Algorithm aims for the fewest moves possible in combinatorial games like Rubik's Cube.
  2. Researchers found God's Number for Rubik's Cube using techniques like partitioning, symmetry, and dropping optimality.
  3. Key strategies used were dividing the problem into smaller parts, leveraging symmetry to reduce work, and focusing on finding solutions within 20 moves instead of the best possible solution.

Why is the Golden Ratio Hiding in the Fibonacci Sequence?

The Palindrome • 4 implied HN points • 30 Jan 26
🚌 Education Combinatorics
  1. The Fibonacci sequence has a simple closed-form (Binet's) formula that uses the golden ratio phi (φ) and its conjugate psi (ψ) to compute Fn directly. It yields exact integers even though φ and ψ are irrational.
  2. Generating functions turn the recurrence into the rational function F(x)=x/(1-x-x^2), and partial fraction decomposition expresses F(x) as a sum of two geometric series, which leads to Binet's formula.
  3. The recurrence can also be encoded by a 2×2 Fibonacci matrix whose eigenvalues are φ and ψ; diagonalizing that matrix and raising it to the nth power gives the same closed-form result, and computing matrix powers is often numerically more stable than directly evaluating Binet's formula.

Chess and the number e

A Piece of the Pi: mathematics explained • 163 implied HN points • 16 Dec 24
🔬 Science Combinatorics
  1. The number e, around 2.718, plays a big role in math, especially in combinatorial problems like derangements. This is when items are arranged so that none are in their original position.
  2. In chess, setting up nonattacking rooks can be related to derangements. The chance that none of them land on the main diagonal equals about 36.8%, which links back to the number e.
  3. Recent studies have also looked at how many safe squares remain on a chessboard when placing random pieces. As more pieces are added, the proportion of safe squares follows certain patterns connected to e.
Get a weekly roundup of the best Substack posts, by hacker news affinity:

What is Bayesian Statistics? The Beginner Math Guide (Part One)

The Software & Data Spectrum • 78 implied HN points • 13 Apr 23
🔬 Science Combinatorics
  1. Bayesian Statistics is used in various fields like Machine Learning, Engineering, Data Science, and more.
  2. Bayesian Thinking involves observing data, holding prior beliefs, forming hypotheses, gathering evidence, and comparing hypotheses.
  3. Probability is a way to measure belief strength, and calculating probabilities involves counting outcomes and using ratios of beliefs.

Counting dimer tilings

A Piece of the Pi: mathematics explained • 36 implied HN points • 21 Feb 25
🔬 Science Combinatorics
  1. Dimer tilings involve arranging domino-shaped pieces on grids, and how many ways you can arrange them can vary based on the layout. For example, on a 3x3 grid with one space empty, there are 18 different arrangements.
  2. If at least one dimension of a rectangle is even, it's possible to cover it completely with dimers. However, if both dimensions are odd, it's impossible to cover them without leaving gaps.
  3. There are mathematical patterns and theorems, like Gomory's Theorem, that help understand how to tile grids with dimers. These principles can show when tiling is possible based on the arrangement and color of squares.

Problem 55:Playlist with Buffer[Apple]

Technology Made Simple • 39 implied HN points • 07 Sep 22
🕹 Technology Combinatorics
  1. The post discusses a problem related to creating a suitable music playlist for a road trip, requiring a certain number of songs and buffer between repeats.
  2. It emphasizes the importance of dynamic programming, logic, and combinatorics in solving the mentioned playlist problem.
  3. The post also includes requests to engage with and share the newsletter, showcasing the value of community support and feedback.

Permutations and combinations

Infinitely More • 17 implied HN points • 17 Nov 24
🚌 Education Combinatorics
  1. A permutation is just a way to rearrange a list of objects. For example, with three letters like 'a', 'b', and 'c', you can arrange them in six different ways.
  2. The factorial of a number shows how many ways you can arrange that many objects. For example, 5! equals 120 because it's 5 times 4 times 3 times 2 times 1.
  3. When choosing items from a group without caring about the order, we use combinations. The formula for this is called 'n choose k', which helps calculate how many ways you can select items.

[Solution]Problem 42: Length of the longest subarray where all its elements are distinct (Microsoft)

Technology Made Simple • 19 implied HN points • 17 Jun 22
🕹 Technology Combinatorics
  1. When faced with a problem involving combinatorics, taking the time to read and analyze the question can provide crucial insights for a more efficient solving approach
  2. In the context of building max heaps from a list of integers, understanding the structure of heaps as complete binary trees allows for simplification of the problem into calculating combinations and values for left and right subtrees
  3. Calculating the values for the left subtree, such as height and number of nodes, can lead to a shift in the coding task complexity from generating heaps to conducting combinatorics

Problem 42: Length of the longest subarray where all its elements are distinct (Microsoft)

Technology Made Simple • 19 implied HN points • 15 Jun 22
🚌 Education Combinatorics
  1. The post discusses a coding interview question about finding the number of distinct ways to create a max heap from a list of integers.
  2. It emphasizes the importance of practicing unique interview questions to prepare for a variety of challenges.
  3. The author shares personal anecdotes and encourages engaging with the content by sharing preferences for future topics.

[Solution]Problem 19: Help Couples sit together [Spotify]

Technology Made Simple • 19 implied HN points • 06 Jan 22
🕹 Technology Combinatorics
  1. Creating a brute force solution can guide towards an optimal solution, but in interviews, it's better to showcase understanding and move on to more effective approaches
  2. Greedy algorithms are straightforward and choose the best option at each step, making them applicable for optimization problems like arranging couples
  3. Optimal algorithms, like the greedy approach, can be efficient because they make choices based on immediate benefit, even though they may overlook long-term gains