# Questions tagged [combinatorics]

For challenges involving combinatorics.

90 questions
Filter by
Sorted by
Tagged with
47answers
6k 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 ...
16answers
2k 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 ...
47answers
6k 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 ...
23answers
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; ...
25answers
2k 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): ...
8answers
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,...
42answers
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 ...
15answers
1k 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 ...
5answers
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 ...
39answers
3k views

### Shortest power set implementation

Problem definition Print out the powerset of a given set. For example: [1, 2, 3] => [[], , , , [1, 2], [1, 3], [2, 3], [1, 2, 3]] Each element is to ...
6answers
1k 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,...
4answers
1k 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 ...
15answers
1k 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 ...
6answers
794 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. ...
26answers
2k views

### Mathematical Combination

Write a program that takes an input such as: n,k which then computes: and then prints the result. A numerical example: Input: ...
7answers
2k 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 ...
20answers
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 ...
11answers
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 ...
6answers
2k 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 ...
10answers
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. ...
22answers
2k 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 ...
2answers
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 ...
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 ...
6answers
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 ...
7answers
1k views

### Finding sum-free partitions

Executive summary Given input k, find a partition of integers 1 to n into ...
20answers
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 ...
8answers
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 ...
16answers
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 ...
6answers
874 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. ...
11answers
1k 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 ...
2answers
962 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 ...
3answers
471 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 ...
3answers
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, ...
10answers
550 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 ...
14answers
1k 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: ...
5answers
787 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-...
8answers
4k 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 ...
3answers
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 ...
4answers
776 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 ...
1answer
964 views

### Find Diffy Games

A fun game to play if you are bored is the Diffy Game. It is a one player game that is pretty simple and can consume a good deal of your time. The Diffy game works like as follows: You start with a ...
17answers
741 views

### Compress a maximal discrepancy-2 sequence

Output this binary sequence of length 1160: ...
3answers
975 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 ...
1answer
2k views

### Android Lock Screen

Intro You are sitting in a board room at the end of a long table. You look around and see Tim Cook, the Apple Board of Directors, the ghost of Steve Jobs, and Jack Donaghy. Apple has called this ...
1answer
2k views

### Figure Out the Android Lock Pattern

Lets say you saw your friend enter his or her password into their Android phone. You don't remember how they made the pattern but you remember what the pattern looks like. Being the concerned friend ...
6answers
829 views

### Partial factorisations of a positive integer

A collection of positive integers d_1 d_2 ... d_k is a factorisation of a positive integer n if ...
2answers
765 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}, ...
0answers
509 views

### Maximal discrepancy-2 sequence with minimal entropy

Background As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties ...
34answers
2k 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 ...
3answers
473 views

### Permutation group operation

There is a well-known bijection between the permutations of n elements and the numbers 0 to n!-1 such that the lexicographic ordering of the permutations and the corresponding numbers is the same. For ...
22answers
2k views

### Generate the Stöhr sequence

I am learning Ruby and wrote my first nontrivial code to solve this problem. The challenge is to generate the first n elements of the Stöhr sequence, S, which is defined as follows: S = 1 ...