Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
42 votes
64 answers
9k 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 ...
user avatar
  • 7,672
40 votes
54 answers
7k views

Catalan Numbers

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics. The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as ...
user avatar
27 votes
17 answers
3k 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 ...
user avatar
  • 4,087
23 votes
28 answers
3k views

Code-Golf: Permutations

Write a function that takes as input a set of integers (can be a list, array or any other container with distinct numbers), and outputs the list of all its permutations. Python (95 chars): ...
user avatar
  • 341
26 votes
23 answers
2k views

Case Permutation

Who needs to compare things case insensitively when you're able to generate every permutation of uppercase and lowercase? No one! That's the answer. No one does. Your task is to achieve this feat; ...
user avatar
  • 3,145
27 votes
45 answers
4k views

Shortest power set implementation

Problem definition Print out the powerset of a given set. For example: [1, 2, 3] => [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] Each element is to ...
user avatar
26 votes
6 answers
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 ...
user avatar
  • 42.2k
11 votes
25 answers
3k 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 ...
user avatar
  • 437
50 votes
47 answers
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 ...
user avatar
  • 138k
31 votes
15 answers
3k 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 ...
user avatar
  • 38.8k
22 votes
18 answers
2k views

Calculate the partitions of N

Your challenge is simple: GIven an integer N, ouput every list of positive integers that sums to N. For example, if the input was 5, you should output ...
user avatar
  • 57.4k
16 votes
31 answers
2k views

Mathematical Combination

Write a program that takes an input such as: n,k which then computes: $$\binom n k = \frac {n!} {k!(n-k)!}$$ and then prints the result. A numerical example: ...
user avatar
  • 285
26 votes
8 answers
2k views

Generate the shortest De Bruijn

A De Bruijn sequence is interesting: It is the shortest, cyclic sequence that contains all possible sequences of a given alphabet of a given length. For example, if we were considering the alphabet A,...
user avatar
2 votes
8 answers
1k views

Compute the number of ways how you can express a number as a sum [closed]

For a given natural number n, compute the number of ways how one can express n as a sum of positive natural numbers. For example,...
user avatar
  • 4,342
14 votes
2 answers
773 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 ...
user avatar
  • 8,117
22 votes
6 answers
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 ...
user avatar
20 votes
2 answers
524 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 ...
user avatar
  • 20.6k
9 votes
6 answers
915 views

Permutation Numbering

The Challenge For a given set of n integers, write a program which will output its lexicographic index. The Rules The input must only be a set of unique non-negative integers separated by spaces. ...
user avatar
13 votes
14 answers
2k views

Generate all combinations of given list of elements, sorted

Make a code that takes a list and a number as input, and generates all possible combinations with the length of the number. For example, with the list {0,1} and the number 2: ...
user avatar
  • 535
3 votes
7 answers
3k views

Generating combinations without recursion [closed]

Given a list of strings and a length, give all combinations of that list with the given length. The problem is: your code must not be recursive. Yes, it can be done. I have done it myself, when I had ...
user avatar
  • 4,224
21 votes
20 answers
6k views

A penny saved is a penny

...counted! You will pass your program a variable which represents a quantity of money in dollars and/or cents and an array of coin values. Your challenge is to output the number of possible ...
user avatar
19 votes
11 answers
2k views

Random Golf of the Day #3: Integer Partitions

About the Series First off, you may treat this like any other code golf challenge, and answer it without worrying about the series at all. However, there is a leaderboard across all challenges. You ...
user avatar
18 votes
11 answers
3k views

Decompose a permutation into cycles

There is a well-known theorem that any permutation can be decomposed into a set of cycles. Your job is to write the shortest possible program to do so. Input: Two lines. The first contains a ...
user avatar
11 votes
10 answers
2k views

Fibonacci domino tiling

There's classic combinatorial result that the number of ways to tile a 2*n strip by 1*2 dominoes is the nth Fibonacci number. ...
user avatar
  • 138k
51 votes
2 answers
2k views

Extending OEIS: Counting Diamond Tilings

I promise, this will be my last challenge about diamong tilings (for a while, anyway). On the bright side, this challenge doesn't have anything to do with ASCII art, and is not a code golf either, so ...
user avatar
39 votes
10 answers
5k views

The Urinal Protocol

Background The so-called "Urinal Protocol", describing the order in which individual urinals are picked in a men's bathroom, has been discussed in multiple places. One version is given in this xkcd ...
user avatar
  • 2,919
32 votes
6 answers
2k views

Tic-tac-toe with only crosses

Introduction Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only going to use crosses. The first person who places three crosses in a row ...
user avatar
  • 43.4k
17 votes
2 answers
866 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 ...
user avatar
  • 8,117
17 votes
7 answers
3k views

Finding sum-free partitions

Executive summary Given input k, find a partition of integers 1 to n into ...
user avatar
  • 42.8k
27 votes
21 answers
1k views

Number of Straight-Chain Alk*nes of given length

A straight-chain alk*ne is defined as a sequence of carbon atoms connected by single (alkane), double (alkene), or triple bonds (alkyne), (implicit hydrogens are used.) Carbon atoms can only form 4 ...
user avatar
  • 5,992
21 votes
2 answers
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). ...
user avatar
  • 64.8k
19 votes
8 answers
4k views

Building a long chain of words

This challenge is to find the longest chain of English words where the first 3 characters of the next word match the last 3 characters of the last word. You will use an common dictionary available in ...
user avatar
  • 6,732
19 votes
21 answers
2k views

How many partitions do I have?

The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the ...
user avatar
12 votes
6 answers
1k views

Chess960 position generator

Context Chess960 (or Fischer Random Chess) is a variant of chess invented and advocated by former World Chess Champion Bobby Fischer, publicly announced on June 19, 1996 in Buenos Aires, Argentina. ...
user avatar
  • 1,683
6 votes
11 answers
2k views

Recursion bracketed; or Dyck words generation

We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy… A ...
user avatar
  • 179
23 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
  • 22.2k
22 votes
3 answers
1k 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 ...
user avatar
  • 8,117
15 votes
16 answers
2k 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 ...
user avatar
  • 13.8k
13 votes
12 answers
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 ...
user avatar
  • 22.2k
13 votes
2 answers
1k views

Count how many distance sequences are far from all others

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. Let P be a binary string of ...
user avatar
11 votes
3 answers
537 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 ...
user avatar
10 votes
3 answers
338 views

Domino Recurrence Generator

Challenge We once had a challenge to count domino tilings of m by n grid, and we all know that, for any fixed number of rows, the number of domino tilings by columns forms a linear recurrence. Then ...
user avatar
  • 64.8k
6 votes
3 answers
2k views

The making of "Spot It!": Finding almost unique sets

Puzzle: Find a deck of c cards, each containing p pictures, such that no two pictures match on a given card, and exactly 1 picture on each card matches exactly 1 picture on each of the other cards, ...
user avatar
21 votes
41 answers
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 ...
user avatar
  • 13.8k
13 votes
10 answers
597 views

Counting Fibonacci Orbits

If we define a Fibonacci-like sequence as fk(n) = (fk(n-1) + fk(n-2)) % k, for some integer k (where % is the modulo operator), the sequence will necessarily be cyclic, because there are only k2 ...
user avatar
7 votes
5 answers
805 views

Hypercube sides

Your goal is to output all the "sides" (corners, edges, faces, etc.) of an N-dimensional unit hypercube, where N is non-negative. A "side" is defined as any (N-M)-dimension surface embedded in N-...
user avatar
29 votes
4 answers
1k 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 ...
user avatar
  • 8,117
47 votes
8 answers
5k views

Determine if a coin system is Canonical

The Cashier's Algorithm is an algorithm for making change in the minimal number of coins that works quite well for most currency systems. However like most greedy algorithms it is not without its ...
user avatar
  • 89.4k
28 votes
3 answers
1k views

Stuffing primes in a box

Your task is write a program or function that can fill a given rectangle with prime numbers. The width and height of the ...
user avatar
  • 6,732
35 votes
21 answers
8k 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 ...
user avatar