# Tagged Questions

for challenges involving combinatorics.

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]...
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 ...
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 ...
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 ...
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 ...
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 ...
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 + ...
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,...
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 ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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. ...
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): ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 | |____|____|____|____| | | | | | |...
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] =...