for challenges involving combinatorics.

learn more… | top users | synonyms

7
votes
7answers
220 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
129 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] ...
11
votes
10answers
585 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
331 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
353 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
812 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
11answers
721 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
359 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
17answers
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
723 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
737 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
11answers
840 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
425 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
732 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
668 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
485 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
251 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
288 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
657 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
617 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
702 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
289 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
395 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
467 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 ...
10
votes
0answers
210 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
995 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
972 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
861 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
929 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
511 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
383 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
260 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
378 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
188 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
339 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
424 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
306 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 ...
14
votes
1answer
488 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 ...