# Questions tagged [combinatorics]

For challenges involving combinatorics.

372 questions
Filter by
Sorted by
Tagged with
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 ...
• 197k
4k 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 ...
• 145k
6k 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 ...
• 98.8k
10k 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 ...
• 7,732
8k 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 <...
• 11.2k
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 <...
• 89.8k
2k views

### Topologically distinct ways of dissecting a square into rectangles

I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021. Would be super great to get a couple more terms for [...] A049021. Kind of thing [...] ...
• 8,689
6k views

### Every word from babab to zyzyz

Your task is to write a program that will output a readable list of every five letter words with the structure: consonant - vowel - consonant - vowel - consonant The output should be sorted ...
• 501
3k views

### Lazy battleship placement

Imagine the following scenario: you are playing battleships with a friend but decide to cheat. Rather than moving a ship after he shoots where your ship used to be, you decide not to place any ships ...
• 9,492
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 ...
• 2,959
10k views

### Amount of permutations on an NxNxN Rubik's Cube

Introduction: A 3x3x3 Rubik's Cube has $43,252,003,274,489,856,000$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually ...
• 127k
4k views

### Brute-force the switchboard

The other day, our team went to an escape room. One of the puzzles involved a board of six mechanical switches where you had to find the correct combination of on and off in order to unlock a box, ...
2k views

• 8,689
3k 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 ...
• 39.1k
4k views

### Absolute Sums of Sidi Polynomial Coefficients

Background The Sidi polynomial of degree $n$ – or the $(n + 1)$th Sidi polynomial – is defined as follows. $$S_n(x) = \sum^n_{k=0}s_{n;k}x^n \text{ where } s_{n;k} = (-1)^k\binom n k (k+1)^n$$ The ...
• 210k
1k 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 ...
• 8,689
3k views

### Deranged !Combinatorics: Compute the Subfactorial

The subfactorial or rencontres numbers (A000166) are a sequence of numbers similar to the factorial numbers which show up in the combinatorics of permutations. In particular the nth subfactorial !n ...
• 197k
7k views

### Don't repeat yourself in Rock-Paper-Scissors

Upon the rumor that Codegolf will have a Rock-Paper-Scissors tournament you look into the topic of square-free words. A word made of the letters R, ...
• 1,737
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 ...
• 89.8k
4k 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 ...
• 72.1k
947 views

### Arranging Bubbles

Note, challenge copied from question asked at math.stackexchange. Recently, I attained quite some skill at blowing bubbles. At first I would blow bubbles like this: But then things started getting ...
• 11.6k
4k views

### Shortest power set implementation

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

### Never trust a mastermind

You probably know the game mastermind: The player tries to guess a code of 4 slots, with 8 possible colors - no duplicates this time. Let's call those colors A through H, so possible solutions could ...
3k 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 ...
• 98.8k
2k views

### Sign-Swapping Sums

Given a nonempty list of positive integers $(x, y, z, \dots)$, your job is to determine the number of unique values of $\pm x \pm y \pm z \pm \dots$ For example, consider the list $(1, 2, 2)$. ...
• 15.4k
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 ...
• 6,132
3k views

### Compute the multinomial coefficient

Time for another easy challenge in which all can participate! The multinomial theorem states: (x_1 + x_2 + \cdots + x_m)^n = \sum_{k_1 + k_2 + \cdots + k_m = n} \binom n {k_1, k_2, \dots, k_m} \...
• 4,138
2k 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 ...
• 7,387
1k 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. ...
• 145k
2k 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,...
• 14.5k
1k 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 ...
• 98.8k
3k views

• 6,266