Questions tagged [combinatorics]
For challenges involving combinatorics.
288
questions
5
votes
0answers
102 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 ...
20
votes
18answers
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 ...
8
votes
11answers
738 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
2answers
401 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
5answers
583 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 ...
16
votes
1answer
187 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 ...
8
votes
3answers
362 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 ...
9
votes
1answer
191 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. ...
6
votes
1answer
300 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 ...
19
votes
2answers
323 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 ...
20
votes
14answers
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 ...
17
votes
0answers
326 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 ...
10
votes
18answers
927 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
2answers
359 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
4answers
427 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\$ ...
18
votes
4answers
451 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 ...
17
votes
20answers
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 ...
10
votes
1answer
160 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 ...
14
votes
6answers
614 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 ...
19
votes
15answers
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
41answers
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 ...
17
votes
1answer
631 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 ...
15
votes
12answers
435 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 ...
3
votes
1answer
244 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 ...
21
votes
17answers
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
16answers
1k 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
18answers
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
9answers
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
19answers
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 ...
7
votes
1answer
524 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
0answers
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 ...
20
votes
21answers
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 ...
13
votes
7answers
521 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
4answers
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 ...
6
votes
1answer
599 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 ...
18
votes
15answers
3k views
Stack Exchange Answerer
Oof! You've been coding the whole day and you even had no time for Stack Exchange!
Now, you just want to rest and answer some questions. You have T minutes of free time. You enter the site and see N ...
14
votes
1answer
527 views
Circular robot instructions
This challenge is based on Project Euler problem 208. Also related to my Math Stack Exchange question, Non-self-intersecting "Robot Walks".
You have a robot that moves in arcs which are \$1/...
15
votes
8answers
558 views
Decorate Pascal's Triangle
Although what is a Pascal's triangle is well-known and we already can generate it, the task is now different:
Output \$n\$ first lines of the Pascal's triangle as colored bricks.
Color number is ...
24
votes
16answers
3k views
Triangular domino tiling of an almost regular hexagon
Background
An almost regular hexagon is a hexagon where
all of its internal angles are 120 degrees, and
pairs of the opposite sides are parallel and have equal lengths (i.e. a zonogon).
The ...
16
votes
1answer
382 views
Counting symmetric grid chains
Notation and definitions
Let \$[n] = \{1, 2, ..., n\}\$ denote the set of the first \$n\$ positive integers.
A polygonal chain is a collection of connected line segments.
The corner set of a ...
15
votes
6answers
492 views
Roman Numeral Counting
Roman numerals can be (mostly) written in a one column format, because each letter intersects the top and the bottom of the line. For example: I, or 1 intersects ...
8
votes
3answers
219 views
Multigraphs with a given degree sequence
This challenge will give you an input of a degree sequence in the form of a partition of an even number. Your goal will be to write a program that will output the number of loop-free labeled ...
17
votes
2answers
639 views
Number of distinct tilings of an n X n square with free n-polyominoes
The newest "nice" OEIS sequence, A328020, was just published a few minutes ago.
Number of distinct tilings of an n X n square with free n-polyominoes.
This sequence counts tilings up to ...
18
votes
14answers
1k views
Permutations in Disguise
Given a \$n\$-dimensional vector \$v\$ with real entries, find a closest permutation \$p\$ of \$(1,2,...,n)\$ with respect to the \$l_1\$-distance.
Details
If it is more convenient, you can use ...
22
votes
10answers
2k views
Count the number of shortest paths to n
This code challenge will have you compute the number of ways to reach \$n\$ starting from \$2\$ using maps of the form \$x \mapsto x + x^j\$ (with \$j\$ a non-negative integer), and doing so in the ...
33
votes
23answers
4k views
Brute-force the switchboard
The other day, our team went to an escape room. One of the puzzles involved a board of six mechanical switches where you had to find the correct combination of on and off in order to unlock a box, ...
10
votes
1answer
217 views
Compute my Sacred Geometry [closed]
In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use ...
0
votes
3answers
237 views
Find all a, b, c, d, e, such that a + b + c + d + e = 1000 with no more than 3 loops [closed]
The rule is:
a, b, c, d, e is an integer from 0 to 1000, no relation between ...
13
votes
2answers
655 views
Counting generalized polyominoes
This challenge will have you count pseudo-polyforms on the snub square tiling.
I think that this sequence does not yet exist on the OEIS, so this challenge exists to compute as many terms as possible ...
4
votes
1answer
221 views
Multiplication in the Steenrod Algebra
Here's yet another Steenrod algebra question. Summary of the algorithm: I have a procedure that replaces a list of positive integers with a list of lists of positive integers. You need to repeatedly ...
