Questions tagged [combinatorics]
For challenges involving combinatorics.
342
questions
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 ...
- 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 ...
- 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 ...
- 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 ...
- 753
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, ...
- 46.7k
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 ...
- 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 ...
- 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 ...
- 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-...
- 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(...
- 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^...
- 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 ...
- 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 ...
user7467
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 ...
- 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). ...
- 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 ...
- 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\}, \{...
- 46.7k
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 ...
- 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 ...
- 46.7k
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 ...
- 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 ...
- 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 \\ \...
- 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 ...
- 131
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 ...
user7467
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....
- 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 ...
- 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^...
- 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 ...
- 90.8k
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 ...
- 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 ...
- 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 ...
- 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 ...
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 ...
- 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 [...] ...
- 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 ...
- 785
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 ...
- 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 ...
- 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\...
- 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.
...
- 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 ...
- 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"...
- 121
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\...
- 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 ...
- 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 ...
- 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 + ...
- 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 ...
- 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 ...
- 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&...
- 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 ...
- 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 ...
- 62.1k