# Questions tagged [combinatorics]

For challenges involving combinatorics.

298 questions
Filter by
Sorted by
Tagged with
76 views

### Polygons in a cube

Inspired in part by this Mathologer video on gorgeous visual "shrink" proofs, and my general interest in the topic, this challenge will have you count regular polygons with integer ...
3k views

2k views

### Never trust a mastermind

You probably know the game mastermind: The player tries to guess a code of 4 slots, with 8 possible colors - no duplicates this time. Let's call those colors A through H, so possible solutions could ...
206 views

### Domino Recurrence Generator

Challenge We once had a challenge to count domino tilings of m by n grid, and we all know that, for any fixed number of rows, the number of domino tilings by columns forms a linear recurrence. Then ...
2k views

### Verify a Superpermutation

A superpermutation on n symbols is a string which contains every permutation of n symbols in its body. For instance, 123121321 is a superpermutation on three ...
763 views

### Counting King's Hamiltonian Paths through 3-by-N grid

Background A Hamiltonian path is a path on a graph that steps through its vertices exactly once. On a grid, this means stepping through every cell exactly once. On a square grid, a Chess King can move ...
407 views

### What is the fastest safe way down a mountain?

Intro Help! I'm stuck on a snow-covered mountain and I need to get down as fast as possible, preferably without dying. I have a map showing how high each part of the mountain is above the normal ...
595 views

### Placing Dominoes On A Chequerboard

How many ways can one place (unlabelled) dominoes on a square chequerboard such that the number placed horizontally is equal to the number placed vertically? The dominoes must align with, and may not ...
199 views

### Rubik's Snakes! (Part 1)

The Rubik's Snake (or Rubik's Twist) is a toy consisting of several triangular prisms strung together in a line in such a way that the pieces can be rotated about one another in 90 degree turns. Any ...
389 views

### Triangles in a tetrahedron

The goal of this challenge is to extend the OEIS sequence A334581. Number of ways to choose $3$ points that form an equilateral triangle from the $\binom{n+2}{3}$ points in a regular tetrahedral ...
199 views

### Counting hypercube Tetris pieces

Consider the Tetris pieces, but made out of some number of (hyper)cubes instead of four squares, where two blocks are considered the same if one is a rotation, reflection, or translation of another. ...
353 views

### Infinite Snake game

Infinite Snake is just like the video game Snake, except for that the snake is infinitely long, there are no items to eat, and the Snake needs to move in a repeating ...
327 views

### Exactly N in a line

Given a number N from 2 to 8, place any nonzero number of queens on a grid of any size so that every queen has exactly N queens (counting itself) in each of its row, column, and each diagonal. This ...
1k views

### Penney-Conway odds

Background Penney's game is a two-player game about coin tossing. Player A announces a sequence of heads and tails of length $n$, then player B selects a different sequence of same length. The ...
366 views

### Acyclic orientations of an n-dimensional cube

The goal of this challenge is to check and extend the OEIS sequence A334248: Number of distinct acyclic orientations of the edges of an n-dimensional cube. Take an n-dimensional cube (if n=1, this is ...
929 views

### How Many Ways To Empty The Glove Box?

Inspired by this glove-themed 538 Riddler Express Puzzle. Task You are given a positive integer n, and a list ...
366 views

### Spanning paths in a tournament on n nodes

The goal of this challenge is to extend the On-Line Encyclopedia of Integer Sequences (OEIS) sequence A038375. Maximal number of spanning paths in tournament on n nodes. A tournament on $n$ ...
432 views

### Solving the water bucket riddle!

Context The water buckets riddle or the water jugs riddle is a simple riddle that can be enunciated in a rather general form as: Given $n > 0$ positive integers $a_1, a_2, \cdots, a_n$ ...
462 views

### What can you see on a hexagonal spiral?

This code-golf challenge will have you computing OEIS sequence A300154. Consider a spiral on an infinite hexagonal grid. a(n) is the number of cells in the part of the spiral from 1st to n-th cell ...
2k views

### All aboard the factorial train

The system Assume the Earth is flat and that it extends infinitely in all directions. Now assume we have one infinitely long train railway and n trains in that ...
170 views

### Counting polyominoes on (hyper-)cubes

This challenge like some of my previous challenges will have you counting free polyforms, which are generalizations of Tetris pieces. This code-golf challenge will have you count polyomino-like ...
635 views

### Calculate the average longest common substring exactly

[Question inspired by Can you calculate the average Levenshtein distance exactly? . Thank you Anush. ] The longest common substring between two strings is the longest substring which is common to ...
1k views

### (RGS 5/5) Computing the set of all set partitions with fixed sizes

Task Given a set of n unique elements and a multiset l of positive numbers that add up to n,...
2k views

### (RGS 2/5) How many strings can you count within these character classes?

Task Given a string composed of ASCII printable characters, return how many strings could fit the given pattern with character literals and regex-like ranges. Pattern string The pattern string ...
665 views

### Impress Donald Knuth by counting polyominoes on the hyperbolic plane

This challenge is inspired by a talk about Schläfli symbols, etc that I gave in a Geometry seminar. While I was putting together this challenge, I saw that Donald Knuth himself was interested in (some ...
487 views

### Combinations of stepwise increasing integers

Working on something in probability theory, I stumbled across another combinatorical exercise. These are always fun to solve, searching for intelligent approaches. Of course, one can use brute force ...
245 views

### Estimate the mean minimum Hamming distance

Task Inputs $b \leq 100$ and $n \geq 2$. Consider $n$ binary strings, each of length $b$ sampled uniformly and independently. We would like to compute the expected minimum Hamming distance ...
2k views

### Concentric rings on a snub square tiling

This challenge takes place on the snub square tiling. Start by choosing any triangle, and color it $c_1$. Next, find all tiles which touch this triangle at any vertex, and color them $c_2$. Next, ...
2k views

### Computing a specific coefficient in a product of polynomials

Generator functions This gives the context for why this challenge came to life. Feel free to ignore. Generator functions are a nice way of encoding the solution to a problem of combinatorics. You ...
2k views

### Given a list of strings, find all elements which are still in the list when any character is deleted

Write a program using the fewest bytes of source code which given a list of strings finds all elements which are still in the list when any character is deleted. For example, given a list of all ...
1k views

### Counts Of Orderings Containing At Most K Of The Kth Class

This challenge is about the number of orderings which contain at most $n$ classes and at most $k$ of the $k^{\text{th}}$ class. One way to represent such an ordering is as a sequence of ...
2k views

### Super permutations

Super permutations Input: A string The program should loop through all lengths of the input (decrementing one each time), generate all combinations with replacement of the string, then make ...
533 views

### Average number of strings with Levenshtein distance up to 4

This is a version of this question which should not have such a straightforward solution and so should be more of an interesting coding challenge. It seems, for example, very likely there is no easy ...
53 views

### Compositional inverse of a power series [duplicate]

If $f(x) = x + \sum_{i>1} a_ix^i$ and $g(x)=x+\sum_{i>1}b_ix^i$ then there is a composite power series $f(g(x))$ also of this form. Given a power series $f$ the goal is to find a ...
5k views

### Largest monetary amount impossible to make with two types of coin

Suppose we have two different types of coin which are worth relatively prime positive integer amounts. In this case, it is possible to make change for all but finitely many quantities. Your job is to ...
526 views

### Make a random drum loop

Do randomly generated drum loops sound good? A drum loop is a $5\times 32$ matrix $A$ of $1$s and $0$s such that $A_{1,1}=A_{1,17}=A_{2,9}=A_{2,25}=1$, for each $i$, the $i$th row has ...
2k views

### Can you calculate the average Levenshtein distance exactly?

The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one. The challenge is to compute ...
608 views

### Average number of strings with Levenshtein distance up to 3

The Levenshtein distance between two strings is the minimum number of single character insertions, deletions, or substitutions to convert one string into the other one. Given a binary string $S$ of ...