Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5 6