Questions tagged [combinatorics]
For challenges involving combinatorics.
308
questions
22
votes
0answers
384 views
Topologically distinct ways of dissecting a square into rectangles
I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021.
Would be super great to get a couple more terms for [...] A049021. Kind of thing [...] ...
6
votes
11answers
431 views
Constrained integer partition
Challenge
In this challenge, all numbers are in \$\mathbb{N}_0\$.
Create a function or program that, when given a number \$N\$ and a tuple of \$k\$ numbers \$(n_i)\$ (all ≤ \$N\$), returns the number ...
17
votes
5answers
889 views
Count all binary relations
A binary relation on a set \$X\$ is simply a subset \$S \subseteq X \times X\$; in other words, a relation is a collection of pairs \$(x,y)\$ such that both \$x\$ and \$y\$ are in \$X\$. The number of ...
16
votes
2answers
392 views
Count unrooted, unlabeled binary trees of n nodes
An unrooted binary tree is an unrooted tree (a graph that has single connected component and contains no cycles) where each vertex has exactly one or three neighbors. It is used in bioinformatics to ...
20
votes
5answers
751 views
The Caged Circles
This problem will have you analyzing circles drawn on the grid, with the gridlines drawn at integer values of \$x\$ and \$y\$.
Let \$\varepsilon\$ be a very small number (think, \$\varepsilon = 0.0001\...
4
votes
2answers
377 views
Minimal Pairing
Your program should take two lists, where each entry (a positive integer) represents the number of members of some group, as input. These lists will have the same sum but may have different lengths.
...
16
votes
14answers
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 ...
2
votes
0answers
116 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"...
14
votes
1answer
401 views
Total resistance from unit resistors
This problem is based on, A337517, the most recent OEIS sequence with the keyword "nice".
\$a(n)\$ is the number of distinct resistances that can be produced from a circuit with exactly \$n\...
10
votes
1answer
256 views
Gluing tetrahedra together
(This challenge exists to extend sequence A267272 in the On-Line Encyclopedia of Integer Sequences, and perhaps create a new OEIS sequence1.)
This is a code-challenge, which will have you write code ...
14
votes
1answer
255 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 ...
24
votes
9answers
3k views
The square root of the square root of the square root of the…
This code-golf challenge will give you an integer n, and ask you to count the number of positive integer sequences \$S = (a_1, a_2, \dots, a_t)\$ such that
\$a_1 + ...
15
votes
12answers
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 ...
21
votes
20answers
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 ...
23
votes
2answers
867 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&...
14
votes
6answers
554 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 ...
19
votes
2answers
625 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 ...
21
votes
2answers
821 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 ...
17
votes
7answers
677 views
Combinatorial Decomposition
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
4answers
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 ...
8
votes
3answers
277 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 ...
21
votes
19answers
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 ...
9
votes
11answers
782 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
416 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
605 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
229 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 ...
10
votes
3answers
469 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
206 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. ...
8
votes
1answer
414 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
336 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
15answers
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
432 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
22answers
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
2answers
385 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
455 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\$ ...
19
votes
5answers
490 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
179 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
689 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 ...
22
votes
3answers
913 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
594 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
250 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
18answers
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
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
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
550 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 ...
