# Questions tagged [combinatorics]

For challenges involving combinatorics.

353 questions
Filter by
Sorted by
Tagged with
1k views

### Centerless Polygons

A centered polygonal number is a positive integer given by the number of vertices when a point is surrounded by (increasingly larger) polygons with the same number of sides, as shown below. For ...
132 views

### Dobble Double Challenge [closed]

I have a problem, which I haven't found a solution for. Solutions to the first part are well documented, but I have yet to find anyone who has solved the second part. I call this the "Dobble"...
484 views

1k views

### Rectangles in rectangles

This code-golf challenge will give you two positive integers n and k as inputs and have you count the number of rectangles with ...
1k views

### Sequences of distinct positive integers

The goal of this challenge is to take a positive integer n and output (in lexicographic order) all sequences $S = [a_1, a_2, ..., a_t]$ of distinct positive ...
2k views

### Extend the most recent "nice" OEIS sequence: stepping stone puzzle on a grid

Today Neil Sloane of the OEIS sent out an email asking for a confirmation of the current terms, and computation of some larger terms of the latest OEIS sequence A337663 with the keyword "nice&...
599 views

### Maximal saturated domino covering of a rectangle

Inspired by this OEIS entry. Background A saturated domino covering is a placement of dominoes over an area such that the dominoes are completely inside the area, the dominoes entirely cover the ...
651 views

### Tiling a staircase with staircases

Background A staircase polyomino is a polyomino made of unit squares whose shape resembles a staircase. More formally, a staircase polyomino of size $n$ is defined as follows: A staircase polyomino ...
900 views

### Cut a triangle into equal-sized parts!

Similar in spirit to Number of distinct tilings of an n X n square with free n-polyominoes and Partition a square grid into parts of equal area, this challenge will have you count ways of partitioning ...
In the body of this challenge, $\begin{pmatrix}n\\k\end{pmatrix}$ is used to represent the number of combinations of $k$ elements of $n$, also written as $\frac{n!}{k!(n-k)!}$ or n\mathrm{C}... 27 votes 4 answers 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 ... 10 votes 3 answers 338 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 ... 22 votes 20 answers 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 ... 10 votes 11 answers 807 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 ... 17 votes 2 answers 436 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 ... 14 votes 5 answers 656 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 ... 18 votes 1 answer 448 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 ... 11 votes 3 answers 522 views ### Triangles in a tetrahedron The goal of this challenge is to extend the OEIS sequence A334581. Number of ways to choose3$points that form an equilateral triangle from the$\binom{n+2}{3}$points in a regular tetrahedral ... 11 votes 1 answer 219 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. ... 10 votes 1 answer 522 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 ... 20 votes 2 answers 370 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 ... 21 votes 15 answers 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 ... 19 votes 1 answer 649 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 ... 13 votes 22 answers 1k 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 ... 11 votes 2 answers 411 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$... 12 votes 4 answers 506 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$... 20 votes 5 answers 514 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 ... 18 votes 20 answers 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 ... 11 votes 1 answer 198 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 ... 15 votes 6 answers 748 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 ... 20 votes 15 answers 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,... 21 votes 41 answers 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 ... 22 votes 3 answers 1k 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 ... 16 votes 12 answers 656 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 ... 2 votes 1 answer 257 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 ... 22 votes 18 answers 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, ... 15 votes 16 answers 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 ... 14 votes 18 answers 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 ... 22 votes 9 answers 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 ... 20 votes 19 answers 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 ... 5 votes 1 answer 592 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 ... 2 votes 0 answers 57 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 ... 20 votes 21 answers 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 ... 14 votes 7 answers 570 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 ... 13 votes 4 answers 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 ... 5 votes 1 answer 697 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 ... 