for challenges involving combinatorics.

learn more… | top users | synonyms

12
votes
15answers
476 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 [1, 1, 1, 1, 1] [1, 1, 1, 2] [1, 1, 3] [1, 2, 2]...
4
votes
11answers
738 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 ...
10
votes
3answers
260 views

Ways to get to the number

Given the input of the first number and the second number (both positive integers, zero exluded), determine in how many ways could you make the second out of the first, using following actions: +1,+2 ...
2
votes
29answers
4k views

The handshake problem

The handshake problem is the classic problem that for n people in a room, if they all shake hands, what's the total number of handshakes that occur. You code should take an input of any number and ...
11
votes
3answers
325 views

Generalized Birthday Problem

Tonight, my fiancée took me out to dinner to celebrate my birthday. While we were out, I heard Happy Birthday sung to 5 different guests (including myself), in a restaurant full of 50 people. This got ...
35
votes
16answers
3k views

Has My Pie Been Bisected?

Write a program or function that takes in a nonempty list of positive integers. You may assume it is input in a reasonable convenient format such as "1 2 3 4" or [1, 2, 3, 4]. The numbers in the ...
7
votes
7answers
253 views

Largest Distinctly Sum-Free Partition

related and inspired by -- Finding sum-free partitions A set A is defined here as being distinctly sum-free if 1) it consists of at least three elements, |A| ≥ 3, and 2) its distinct self-sum A + ...
5
votes
3answers
131 views

Find the number of ways to choose `n` objects from `r` objects with repetition so that every object has a matching neighbour

For example, if n is 5 and r is 2, it would mean the number of lists below: [1,1,1,1,1] [1,1,1,2,2] [1,1,2,2,2] [2,2,1,1,1] [2,2,2,1,1] [2,2,2,2,2] which is 6. If n is 4 and r is 3: [1,1,1,1] [1,...
11
votes
10answers
595 views

Permutations with Indistinguishable Items

Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each group of indistinguishable numbers has ...
8
votes
8answers
334 views

m-nomial coefficient

While binomial coefficient is the coefficient of (1+x)**n, m-nomial coefficient is the coefficient of (1+x+x**2+...+x**(m-1))**n. For example, m(3,5,6) is the coefficient of x**6 in the expansion of (...
10
votes
2answers
364 views

Tic-tac-toe with only crosses as quick as possible

As per Luke's request and Peter Taylor's addition to this challenge. Introduction Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only ...
27
votes
3answers
824 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 rectangle will be the input. The output must be a list of height strings ...
10
votes
12answers
756 views

Generate combinations with replacement

List all of the combinations with replacement (or combinations with repetition) of size k from a set of n elements. A combination with replacement is an unordered multiset that every element in it ...
11
votes
20answers
2k views

Output the Military Order [duplicate]

In almost every row nowadays, the people tends to order themselves as militaries would do. Challenge Suppose 4 people where: person 1 has priority against person 2, 3 and 4, person 2 has priority ...
16
votes
5answers
1k views

Chocolate numbers

Given an m by n chocolate bar, m,n positive, output the number of ways to break the bar into mn 1 by 1 pieces where each break occurs on a gridline. Order is important. Pieces are also ...
15
votes
1answer
363 views

Same-color arithmetic progressions

Van der Waerden's theorem says that For any given positive integers r and k, there is some number N such that if the integers {1, 2, ..., N} are colored, each with one of r different colors, ...
20
votes
18answers
1k 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. ...
24
votes
6answers
730 views

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
742 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-...
21
votes
11answers
853 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
73 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
427 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
741 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
671 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
505 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 ...
31
votes
32answers
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
16answers
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 ...
34
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
253 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 ...
16
votes
6answers
289 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
675 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 self-...
17
votes
2answers
651 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
106 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 ...
15
votes
4answers
748 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
294 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
400 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
469 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 ...
11
votes
0answers
217 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
1k 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 ...
31
votes
2answers
994 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
876 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
931 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
516 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
384 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
264 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] =...