A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [combinatorics]

For challenges involving combinatorics.

259 questions
Filter by
Sorted by
Tagged with
390 views
+50

### 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 ...
46 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 ...
448 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 ...
1k 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 ...
504 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 ...
3k views

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 ...
430 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/n$ of a ...
501 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 ...
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 ...
365 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 ...
432 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 ...
205 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 ...
578 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 symmetries ...
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 ...
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 ...
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, ...
200 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 ...
229 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 ...
558 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 ...
216 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 ...
1k views

### Generate basis elements of the Steenrod algebra

The Steenrod algebra is an important algebra that comes up in algebraic topology. The Steenrod algebra is generated by operators called "Steenrod squares," one exists for each positive integer i. ...
87 views

### Finding row wise sum of transpose of hv-convex binary matrix [closed]

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m). ...
6k views

### Amount of permutations on an NxNxN Rubik's Cube

Introduction: A 3x3x3 Rubik's Cube has $43,252,003,274,489,856,000$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually ...
370 views

### Counting the number of restricted forests on the Möbius ladder of length n

OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn. The Challenge The challenge is to write a program that takes an integer as an input ...
840 views

### Cycles on the torus

Challenge This challenge will have you write a program that takes in two integers n and m and outputs the number non-...
305 views

### Buy the most appropriate items

A store is having a big sale. If your price reaches $199 or more, you can reduce it by$100. You can buy each product only once. Here's an example list of products: (in order to simplify, the names of ...
687 views

### Check if all vowels exist in pairs of strings [closed]

Your program should find the number of string pairs (pairs of 2) that contain all vowels (a e i o u), when given an integer N and ...
319 views

### Unique Brick Tilings Within A Rectangle

I was browsing Stackoverflow and saw this question about tiling an MxN rectangle, and I thought it would be great for golfing. Here is the task. Given the dimension M and N, write a program that ...
315 views

### Generate the k-ary necklaces of length n

The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers ...
310 views

### Partition a square grid into parts of equal area

This challenge is based on the following puzzle: You are given an n by n grid with n cells ...
726 views

### Number of $n$-carbon alkanes

Given a positive number $n$, find the number of alkanes with $n$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with $n$ nodes, such that every node has ...
2k views

### Partitioning the grid into triangles

Goal The goal of this challenge is to produce a function of n which computes the number of ways to partition the n X 1 grid ...
455 views

### Arbitrary Randomness (Speed edition)

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
3k views

### Arbitrary Randomness

Randomness is fun. Challenges with no point are fun. Write a function that, given integer input n, will output a set (unordered, unique) of exactly ...
308 views

### Find arrays with distinct subarray sums

Consider an array A of length n. The array contains only integers in the range 1 to ...
832 views

### Count arrays that are really unique

This is a follow up to Count arrays that make unique sets . The significant difference is the definition of uniqueness. Consider an array A of length ...
486 views

### Fastest algorithm to output array containing all integers in range excluding duplicate digits

Input is a single integer in ascending digit order. The only valid inputs are: 12 123 1234 ...
157 views

### Seeking Substantial Subcollections

(thanks to @JonathanFrech for the title) Challenge Write a program or function that, given a collection of positive integers $S$ and a positive integer $n$, finds as many non-overlapping ...
483 views

### Count arrays that make unique sets

This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals. Consider an array A of length ...
1k views

### Different combinations possible

Problem Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0). There musn't be white spaces between slopes and also the mountain musn't descend below the x axis. ...
401 views

### Removing points from a triangular array without losing triangles

I have a combinatorics problem that I'd like to put on the OEIS—the problem is that I don't have enough terms. This code challenge is to help me compute more terms, and the winner will be the user ...
2k views

### Socket - Plug compatibility

Traveling with electronics is always fun, especially when you need an adapter to charge them. Your challenge is to make planning a trip a little easier by checking if a given plug will be compatible ...
831 views

### Smallest region of the plane that contains all free n-ominoes

On Math Stack Exchange, I asked a question about the smallest region that can contain all free n-ominos. I'd like to add this sequence to the On-Line Encyclopedia of Integer Sequences once I have ...
1k views

### Fun with strings and numbers

Here's a programming puzzle for you: Given a list of pairs of strings and corresponding numbers, for example, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]...
3k views

### The Unique Padlock PIN List!

Introduction In a private chat, a friend of mine apparently recently stumbled across a security system which has the following two restrictions on its valid pins: Each digit must be unique (that is "...
2k views

### Cartesian product of a list with itself n times

When given a a list of values and a positive integer n, your code should output the cartesian product of the list with itself n ...
2k views

### Sign-Swapping Sums

Given a nonempty list of positive integers $(x, y, z, \dots)$, your job is to determine the number of unique values of $\pm x \pm y \pm z \pm \dots$ For example, consider the list $(1, 2, 2)$. ...