# Questions tagged [combinatorics]

For challenges involving combinatorics.

353 questions
Filter by
Sorted by
Tagged with
139 views

### Generate a Kirkman triple system

Given a universe of $v$ elements, a Kirkman triple system is a set of $(v-1)/2$ classes each having $v/3$ blocks each having three elements, so that every pair of elements appears in exactly ...
1k views

### Cryptic Multiplications

Given two non-negative integers e.g. 27, 96 their multiplication expression would be 27 x 96 = 2592. If now each digits is ...
260 views

1k views

### Enumerate all pure sets

In set theory, a set is an unordered group of unique elements. A pure set is either the empty set $\{\}$ or a set containing only pure sets, like $\{\{\},\{\{\}\}\}$. Your challenge is to write a ...
3k views

### Consecutive coin flips

This is a cross-post of a problem I posted to anarchy golf: http://golf.shinh.org/p.rb?tails Given two integers $n$ and $k$ $(0 \le k \le n)$, count the number of combinations of $n$ ...
244 views

### Sort my Cups︎︎︎︎︎︎︎︎︎︎ [closed]

I have a set of colored plastic cups. They come in four colors: green, yellow, pink, and blue. When I put them on my shelf, I like to stack them in a certain pattern. Your job is, given a list of any ...
645 views

### Increasing permutation trees

For this challenge a "binary tree" is a rooted tree where each node has 0 children (leaf) or 2. The children of a node are unordered, meaning that while you might draw the tree with left ...
724 views

### Count alternating permutations

An alternating permutation is a permutation of the first $n$ integers $\{ 1 ... n \}$, such that adjacent pairs of values in the permutation alternate between increasing and decreasing (or ...
217 views

### Find run ascending lists faster

In this question I asked you to determine if a run ascending list could be made. It was code-golf so naturally most the answers are very slow. But what if we want it to be fast. In this challenge I ...
1k views

956 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 ...
538 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 ... 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 ...
775 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). ...
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 ...
462 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\}, \{...
523 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 ...
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 ...
377 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 ...
304 views

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 ...
1k views

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 ...
542 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 ...
388 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 ...
283 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 ...
81 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 ...
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 ...
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 [...] ...
489 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 ...
955 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 ...
515 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 ...
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\...