for challenges involving combinatorics.

learn more… | top users | synonyms

20
votes
17answers
948 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 first three numbers. These are 0, 1, 2. ...
16
votes
2answers
347 views
+100

Enumerate rhyme schemes

A "rhyme scheme" is a string of letters a to z, such that the first occurrences of the characters are in ascending order (without gaps), starting from a. For example (with first occurrences marked): ...
7
votes
5answers
689 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 ...
21
votes
10answers
774 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 ...
0
votes
0answers
69 views

How many ways are there to achieve a winning score in American Football? [duplicate]

[I decided to salvage Ben Reich's question How many unique ways are there to achieve a score in Football? but it ended up being so different that it's only suitable as its own question not spliced ...
31
votes
6answers
1k 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 ...
17
votes
9answers
406 views

Counting Fountains

A fountain is arrangement of coins in rows so that each coin touches two coins in the row below it, or is in the bottom row, and the bottom row is connected. Here's a 21 coin fountain: Your ...
17
votes
9answers
707 views

Sums of prime factors

2013 has the prime factorization 3*11*61. 2014 has the prime factorization 2*19*53. An interesting property regarding these factorizations is that there exist distinct primes in the factorizations of ...
26
votes
13answers
2k views

Motzkin Numbers

The nth Motzkin Number is the number of paths from (0, 0) to (n, 0) where each step is of the form (1, -1), (1, 0) or (1, 1), and the path never goes below y = 0. Here's an illustration of these ...
15
votes
8answers
644 views

Minimum number of numbers to sum to exactly n

First question here, don't yell at me if this is a duplicate or a bad challenge. Introduction I thought of this challenge myself, and it seems to be a good basic puzzle for beginner code-golfers. It ...
15
votes
11answers
468 views

Find the sets of sums

I've enjoyed reading this site; this is my first question. Edits are welcome. Given positive integers n and m, compute all ordered partitions of m into exactly n parts positive integer parts, and ...
29
votes
31answers
4k 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 ...
18
votes
15answers
3k views

Bernoulli Numbers

The Bernoulli numbers (specifically, the second Bernoulli numbers) are defined by the following recursive definition: Where denotes a combination. Given a nonnegative integer m as input, output ...
33
votes
36answers
3k 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 n == a^2 + b^2 (OEIS A004018). Note that a and b can be positive, negative, or zero, and ...
9
votes
4answers
240 views

Rearrangement Inequality

Background The Rearrangement Inequality is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x0, x1, x2...xn-1 and y0, y1, y2...yn-1 of the same ...
15
votes
6answers
256 views

Enumerating N-Dimensional Vectors

Given a positive integer k > 1 and a non-negative integer i, generate a k-tuple (or k-dimensional vector) of non-negative integers. For every k, the map from ℕ to ℕk, must be bijective. That is, ...
17
votes
7answers
580 views

Finding sum-free partitions

Executive summary Given input k, find a partition of integers 1 to n into k sum-free subsets for the largest n you can within 10 minutes. Background: Schur numbers A set A is sum-free if its ...
16
votes
2answers
430 views

The Combinatorics of Transistor

The video game Transistor features a very interesting ability system. You collect 16 "Functions" which you can use in 16 different slots. What's interesting is that there are 3 types of slots and ...
0
votes
2answers
98 views

Generate ordered binary combinations without repetitions [closed]

Challenge Write the shortest program that receives two signed integers n and i and for each i between 1 and 2^n - 1 returns the next ordered permutation based on the binary representation of the ...
14
votes
4answers
684 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 ...
11
votes
2answers
276 views

Count the trees

A tree is a connected, undirected graph with no cycles. Your task is to count how many distinct trees there are with a given number of vertices. Two trees are considered distinct if they are not ...
8
votes
4answers
354 views

Number of domino tilings

Write a program or function that given positive n and m calculates the number of valid distinct domino tilings you can fit in a n by m rectangle. This is sequence A099390 in the Online Encyclopedia of ...
-1
votes
1answer
140 views

join lists by common elements [closed]

You have N lists A = [5, 6, 10, 15] B = [3, 0, 7, 4] C = [49, 59, 29] D = [19, 29, 39] E = [9, 15, 3, 10] You have to combine them such that: Two lists which have a common elements they should be ...
29
votes
7answers
4k views

Which Friends characters were really the best friends?

The six main cast members of the American sitcom Friends all agreed that they would be paid the same salary throughout the run of the series (after season 2, at least). But that doesn't mean that they ...
9
votes
4answers
452 views

Too many pawns on a chess board

Given an integer 2n, find the number of possible ways in which 2n^2 black pawns and 2n^2 white pawns can be arranged on a 2n by 2n chess board such that no pawn attack another. A black pawn can ...
9
votes
0answers
193 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 ...
12
votes
16answers
980 views

Print all colorings of a 3x3 grid

You have a 3x3 grid. Each cell can be colored black or white. Display all 512 of these colorings. Fewest bytes wins. You can display the grids in any formation as long as they are visually separated ...
9
votes
4answers
1k views

Calculate a probability exactly

This task is about writing code to compute a probability exactly. The output should be a precise probability written as a fraction in its most reduced form. That is it should never output 4/8 but ...
29
votes
2answers
781 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 ...
16
votes
4answers
761 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 ...
22
votes
8answers
921 views

Hook length product

A Young diagram is an arrangement of boxes in left-justified rows and top-justified columns. For each box, all the spaces above it and to its left are occupied. XXXXX XXX XXX X The hook length of a ...
9
votes
3answers
501 views

Supersonic domino tilings

Task Write a program that reads three integers m, n either from STDIN or as command-line arguments, prints all possible tilings of a rectangle of dimensions m × n by 2 × 1 and 1 × 2 dominos and ...
13
votes
5answers
377 views

Permutations of the Fifteen Puzzle

The Challenge Consider the following diagram of the Fifteen Puzzle in its solved state: _____________________ | | | | | | 1 | 2 | 3 | 4 | |____|____|____|____| | | | | | ...
7
votes
3answers
250 views

Number of ways to sum [1..n] with [n+1..2n] such that each sum is prime

Let n > 0. Let X = [1..n] and Y = [n+1 .. 2n]. Define a(n) as the number of permutations p of Y such that every element of X + p(Y) is prime. For example: n = 2 X = [1,2] Y = [3,4] p0(Y) = [3,4] ...
17
votes
2answers
364 views

Finding the Deadlock

Finding the Deadlock When programming a multithreading application one must take good care to avoid deadlocking the various threads when accessing shared resources. A deadlock occurs when a thread ...
5
votes
1answer
187 views

Plus one sheep minus one sheep

Once upon a time long long ago...when there was no money or stocks yet, people were trading sheep. Even before (but close to) the invention of abacus, the great-grandfather of Warren Buffet decided it ...
10
votes
3answers
321 views

Count balanced binary strings matching any of a set of masks

A binary string is a string which contains only characters drawn from 01. A balanced binary string is a binary string which contains exactly as many 0​s as 1​s. You are given a positive ...
14
votes
4answers
419 views

Order 40 sticks

We have 40 sticks of same widths but different heights. How many arrangements are there possible to put them next to each other so that when we look from right we see 10 sticks and when we look from ...
10
votes
6answers
299 views

Maximum Concatenated Product

We are given a list of integers p1, ..., pk (not necessarily distinct) where each has a value between 1 and 9, inclusive. Using each of the p1, ..., pk exactly once, we can form concatenations of ...
13
votes
1answer
450 views

Twelve-coin problem

Background The twelve-coin problem is a classic balance puzzle commonly used in job interviews. The puzzle first appeared in 1945 and was posed to my father by my grandfather when he asked to marry ...
22
votes
2answers
556 views

Can you cast the spell?

In Magic: the Gathering, mages (known as "planeswalkers") battle each other by casting spells. Spells cost mana. Five colors of mana exist: White, Blue, Black, Red, and Green, represented as {W}, {U}, ...
7
votes
3answers
638 views

Matrix property X revisited (or the Joy of X)

This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge. A T matrix is fully specified by its first row r and first column c. ...
9
votes
1answer
178 views

Number of unique outputs by substituting variables

Given a set of formulas like this: bacb bcab cbba abbc Give an algorithm that finds the number of unique results you can get when each variable is substituted for either "0" or "1" in every ...
10
votes
3answers
557 views

Count the number of Hankelable matrices

Background A binary Hankel matrix is a matrix with constant skew-diagonals (positive sloping diagonals) containing only 0s and 1s. E.g. a 5x5 binary Hankel matrix looks like a b c d e b c d e f c d ...
26
votes
19answers
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 ...
36
votes
10answers
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 ...
16
votes
6answers
546 views

Sorted Lexical Partition of a Number

The challenge is really simple: given a number, you split its digits into an array of smaller numbers such that the resulting numbers are non-decreasing. The catch is that you have to split it such ...
6
votes
3answers
376 views

Latin Word Judgment

Because I can't concentrate on any task for more than about 5 seconds, I often find myself breaking up words into a sub-strings, each of which is a different length and doesn't contain any repeated ...
9
votes
2answers
171 views

Count Maximal Fence Arrangements

Background I want to build a fence. For that, I have collected a bunch of poles, and stuck them to the ground. I have also collected lots of boards that I'll nail to the poles to make the actual ...
12
votes
10answers
617 views

Generate the set of prepend-append permutations in lexicographically sorted order

Define a prepend-append sequence of length n to be a permutation of the numbers 1, 2, ..., n that can be generated by the following procedure: Start with the number 1. For each number from 2 to n, ...