Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
14 votes
3 answers
826 views

Sniff out biased random permutations

The brilliant engineers at <enter company you love to hate> have struck again. This time they've "revolutionised" the generation of random permutations. "Every great invention is ...
user avatar
  • 5,600
23 votes
9 answers
870 views

Generate all groupings

Let's define a grouping as a flat list, which is either: just 0 2 groupings followed by the literal integer 2 3 groupings ...
user avatar
  • 18.2k
21 votes
14 answers
1k views

Verify a Superpowerset

A superpowerset (analogous to superpermutation) on \$n\$ symbols is a string over the alphabet \$\{1,2,...,n\}\$ such that every subset of \$\{1,2,...,n\}\$ appears as a substring (in some order). For ...
user avatar
  • 311
15 votes
4 answers
518 views

Output a Steiner quadruple system

A Steiner quadruple system \$SQS(n)\$ is a collection of subsets (blocks) of size 4 of a set \$S\$ of size \$n\$ such that every subset of \$S\$ of size 3 is in exactly one block. It is easy to show ...
user avatar
16 votes
13 answers
1k views

Square-free words of a length

A square-free word is a word consisting of arbitrary symbols where the pattern \$XX\$ (for an arbitrary non-empty word \$X\$) does not appear. This pattern is termed a "square". For example, ...
user avatar
31 votes
14 answers
2k views

Iterate your way to a fraction

I recently learned from a comment by MathOverflow user pregunton that it is possible to enumerate all rational numbers using iterated maps of the form \$f(x) = x+1\$ or \$\displaystyle g(x) = -\frac ...
user avatar
  • 8,097
16 votes
13 answers
997 views

Number of complete rhyme schemes

A rhyme scheme is the pattern of rhymes at the end of the lines in a poem. They are typically represented using letters, like ABAB. We consider two rhyme schemes ...
user avatar
  • 18.2k
5 votes
0 answers
122 views

Matching fuzzies [closed]

Introduction Congratulations! You've been selected to do research a a newly discovered animal called a fuzzy, a docile, simple creature that strongly resembles a cotton ball. Fuzzies love to be near ...
user avatar
  • 3,196
18 votes
2 answers
583 views

Counting universal n-ary logic gates

Background A classical logic gate is an idealized electronic device implementing a Boolean function, i.e. one that takes a certain number of Boolean inputs and outputs a Boolean. We only consider two-...
user avatar
  • 62.1k
28 votes
25 answers
2k views

Converge to a number

Your challenge is to, given a positive integer n, count up to each digit of it, giving the effect of converging on it. Basically, count up to the first digit of n by its place value (\$⌊\log_{10}\left(...
user avatar
  • 26.6k
16 votes
11 answers
2k views

Write a number in overflowed binary

We all know how binary conversion works: the sequence of bits $$ b_1, b_2, ..., b_{n-1}, b_n $$ encodes the number $$ b_1 \times 2^{n-1} + b_2 \times 2^{n-2} + ... + b_{n-1} \times 2^1 + b_n \times 2^...
user avatar
  • 18.2k
16 votes
14 answers
943 views

AoCG2021 Day 5: Balancing sleigh with lots of trunks

Part of Advent of Code Golf 2021 event. See the linked meta post for details. The story continues from AoC2015 Day 24, Part 2. Here's why I'm posting instead of Bubbler To recap: Santa gives you the ...
user avatar
  • 32.6k
9 votes
3 answers
529 views

rank and unrank arrays of integers

Consider all arrays of \$\ell\$ non-negative integers in the range \$0,\dots,m\$. Consider all such arrays whose sum is exactly \$s\$. We can list those in lexicographic order and assign an ...
user avatar
15 votes
7 answers
3k views

Make S + S + ... + S as Large as Possible!

Let \$S \subset \mathbb N_{\geq0}\$ be a subset of the nonnegative integers, and let $$ S^{(k)} = \underbrace{S + S + \dots + S}_{k\ \textrm{times}} = \{ a_1 + a_2 + \dots + a_k : a_i \in S\}. $$ For ...
user avatar
  • 8,097
21 votes
2 answers
679 views

Lean golf: Pascal vs. Fibonacci

The Pascal's triangle and the Fibonacci sequence have an interesting connection: Source: Math is Fun - Pascal's triangle Your job is to prove this property in Lean theorem prover (Lean 3 + mathlib). ...
user avatar
  • 62.1k
24 votes
62 answers
3k views

Implement the hyperfactorial

The objective Given the non-negative integer \$n\$, output the value of the hyperfactorial \$H(n)\$. You don't have to worry about outputs exceeding your language's integer limit. Background The ...
user avatar
  • 349
8 votes
7 answers
422 views

Distinct Subset Sums: Extending A276661

Consider the integer set \$S = \{3, 5, 6, 7\}\$. If we list all \$2^n\$ subsets of \$S\$ (its powerset) and calculate their sums, we get $$ \mathcal{P}(S) = \{\emptyset, \{3\}, \{5\}, \{6\}, \{7\}, \{...
user avatar
15 votes
6 answers
521 views

Counting maximal domino placements

Background A maximal domino placement (MDP) on a rectangular grid is a non-overlapping placement of zero or more dominoes, so that no more dominoes can be added without overlapping some existing ...
user avatar
  • 62.1k
19 votes
19 answers
5k views

What's my PIN number?

My PIN number is 1077, but that's too difficult to remember. I know from muscle memory that it's a digit, followed by a different digit, then followed by two of the same digit, which is different to ...
user avatar
19 votes
3 answers
373 views

A multiple of n in every base!

In November 2019, Alon Ran published a particularly lovely sequence in the OEIS, A329126: \$a(n)\$ is the lexicographically earliest string of digits which yields a multiple of \$n\$ when read in any ...
user avatar
  • 8,097
14 votes
3 answers
304 views

Counting uniquely solvable polylinks

Related: Counting polystrips Background Link-a-Pix is a puzzle on a rectangular grid, where the objective is to reveal the hidden pixel art by the following rules: Connect two cells with number N ...
user avatar
  • 62.1k
21 votes
13 answers
1k views

Generalised multi-dimensional chess knight's moves

Multi-dimensional chess is an extension of normal chess that is played on an 8x8x8x8... "board". In normal 2D chess, a knight's move is a movement by a vector of \$ \begin{bmatrix} \pm 2 \\ \...
user avatar
  • 18.2k
10 votes
7 answers
402 views

Combinatorial Pipes

You're a plumber working on a house, and there's some pipes that must be connected at weird angles. You have 8°, 11.25°, 22.5°, 45°, and 90° fittings at your disposal, and you want to use as few as ...
user avatar
7 votes
1 answer
475 views

Compute the size of intersections of sets

Input A positive integer N representing the size of the problem and four positive integers v, x, y, z. Output This is what your code should compute. Consider a set of N distinct integers and consider ...
user avatar
25 votes
19 answers
1k views

Just Enough Ones

Challenge Given a positive integer \$n\$, count the number of \$n\times n\$ binary matrices (i.e. whose entries are \$0\$ or \$1\$) with exactly two \$1\$'s in each rows and two \$1\$'s in each column....
user avatar
  • 6,216
13 votes
5 answers
304 views

No More Jockeys - CodeGolf Version

This challenge is inspired by the game No More Jockeys. The input is a list of tuples of natural numbers (potentially including 0), in some appropriate input format. Starting with player 0 and ...
user avatar
  • 2,997
15 votes
2 answers
379 views

Connecting the Dots: Counting n²-gons in the n×n Grid

The recent volume of MAA's Mathematics Magazine had an article "Connecting the Dots: Maximal Polygons on a Square Grid" by Sam Chow, Ayla Gafni, and Paul Gafni about making (very convex) \$n^...
user avatar
  • 8,097
13 votes
8 answers
1k views

How often will this test fail?

Preamble There was a unit test in our codebase which was shuffling a string of length \$52\$ formed from the set of letters \$[A-Z]+[A-Z]\$ and then using the first \$20\$ characters of that shuffled ...
user avatar
22 votes
3 answers
528 views

Sticky polyhexes

Background A polyhex of size \$n\$ is a contiguous shape made from joining \$n\$ unit regular hexagons side-by-side. As an example, the following image (from Wikipedia) contains all 7 distinct ...
user avatar
  • 62.1k
8 votes
3 answers
379 views

Patterns in Permutations

This fastest-code challenge is based partly on this MSE question and exists to extend some OEIS sequences, and create others. If I extend or create sequences based on this challenge, I'll link to this ...
user avatar
  • 8,097
9 votes
2 answers
280 views

Counting polydominoes

Background A polyomino of size \$n\$ is a contiguous shape made from joining \$n\$ unit squares side by side. A domino is a size-2 polyomino. A polydomino of size \$2n\$ is defined as a polyomino of ...
user avatar
  • 62.1k
2 votes
0 answers
80 views

Find the number of parenthesis combinations [duplicate]

For example, given 3 sets of parenthesis, you have: ()()() ((())) ()(()) (())() (()()) = 5 possible combinations. Challenge Program must: • Take 1 number as an ...
user avatar
18 votes
7 answers
1k views

Matching ABACABA-type patterns

(This challenge is related to the challenge "Generate the Abacaba sequence.") Zimin words (also called "sesquipowers") are an important idea in the subject of "combinatorics ...
user avatar
  • 8,097
39 votes
0 answers
1k 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 [...] ...
user avatar
  • 8,097
7 votes
11 answers
486 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 ...
user avatar
18 votes
5 answers
953 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 ...
user avatar
  • 8,097
16 votes
2 answers
489 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 ...
user avatar
  • 62.1k
20 votes
5 answers
788 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\...
user avatar
  • 8,097
4 votes
2 answers
399 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. ...
user avatar
  • 2,997
16 votes
14 answers
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 ...
user avatar
  • 8,097
2 votes
0 answers
132 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"...
user avatar
16 votes
1 answer
480 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\...
user avatar
  • 8,097
16 votes
1 answer
362 views

Gluing tetrahedra together

(This challenge exists to extend sequence A276272 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 ...
user avatar
  • 8,097
15 votes
1 answer
278 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 ...
user avatar
  • 8,097
26 votes
10 answers
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 + ...
user avatar
  • 8,097
16 votes
12 answers
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 ...
user avatar
  • 8,097
23 votes
20 answers
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 ...
user avatar
  • 8,097
25 votes
2 answers
1k 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&...
user avatar
  • 8,097
15 votes
6 answers
596 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 ...
user avatar
  • 62.1k
19 votes
2 answers
650 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 ...
user avatar
  • 62.1k

1
2 3 4 5
7