# Questions tagged [combinatorics]

For challenges involving combinatorics.

274 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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,...
382 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$ ...
2k views

### Random ASCII Art of the Day #5: Diamond Tilings

Mash Up Time! This is instalment #5 of both my Random Golf of the Day and Optimizer's ASCII Art of the Day series. Your submission(s) in this challenge will count towards both leaderboards (which you ...
522 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 ...
426 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 ...
3k views

### Shortest power set implementation

Problem definition Print out the powerset of a given set. For example: [1, 2, 3] => [[], , , , [1, 2], [1, 3], [2, 3], [1, 2, 3]] Each element is to ...
142 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 ...
633 views

### Find the Odd odds

Given an unordered collection of positive integers by any reasonable input method, return all of the sub-collections that have an odd number of odd elements (i.e. have an odd total). This is code-...
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 ...
568 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 ...
741 views

### Maximal discrepancy-2 sequence with minimal entropy

Background As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties ...
869 views

### Compress a maximal discrepancy-2 sequence

Output this binary sequence of length 1160: ...
867 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 ...
540 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 ...
318 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 ...
228 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 ...
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,...
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 ...
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 ...
506 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 ...
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 ...
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 ...
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 ...
507 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 ...
4k views

### Count sums of two squares

Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers ...
2k views

### The Coin Problem

Background The official currency of the imaginary nation of Golfenistan is the foo, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos. One can see that it's not ...
52 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 ...
579 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 ...
429 views

### Counting polystrips

Polystrips are a subset of polyominoes conforming to the following rules: each piece consist of 1 or more cells no cell can have more than two neighbours the cells should not enclose a hole Free ...
659 views

### Chess960 position lookup

This is a follow-up to Chess960 position generator. In Chess960, there are 960 possible starting positions that can be enumerated from 0 to 959 (or, at your choice, from 1 to 960). The enumeration ...
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 ...
2k views

### Rearranging the sequence

Introduction Let's observe the following sequence (non-negative integers): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... For example, let's take the ...
498 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 ...
7k views

### Generate Pascal's triangle

Pascal's triangle is generated by starting with a 1 on the first row. On subsequent rows, the number is determined by the sum of the two numbers directly above it to the left and right. To ...
2k views

### Compute the multinomial coefficient

Time for another easy challenge in which all can participate! The multinomial theorem states: The expression in parentheses is the multinomial coefficient, defined as: Allowing the terms ki to ...
1k views

### List all multiplicative partitions of n

Given a positive number n, output all distinct multiplicative partitions of n in any convenient format. A multiplicative partition of n is a set of integers, all greater than one, such that their ...
3k views

### Vampire Compatibility

A little known fact about vampires is that they must drink the blood of victim that has a compatible donor blood type. The compatibility matrix for vampires is the same as the regular red blood cell ...
815 views

### Calculate a Pedigree

A little genetics lesson When you only have access to someone's visible traits or phenotype, a pedigree of their family history is often used to figure out the actual genetic information or, genotype ...
373 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 ...
420 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 ...
462 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 ...
213 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 ...
621 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 ...
634 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 ...
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 ...