# Questions tagged [combinatorics]

For challenges involving combinatorics.

253 questions
Filter by
Sorted by
Tagged with
3k views

Oof! You've been coding the whole day and you even had no time for Stack Exchange! Now, you just want to rest and answer some questions. You have T minutes of free time. You enter the site and see N ...
2k 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 ...
2k 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 ...
416 views

### Circular robot instructions

This challenge is based on Project Euler problem 208. Also related to my Math Stack Exchange question, Non-self-intersecting "Robot Walks". You have a robot that moves in arcs which are $1/n$ of a ...
494 views

### Decorate Pascal's Triangle

Although what is a Pascal's triangle is well-known and we already can generate it, the task is now different: Output $n$ first lines of the Pascal's triangle as colored bricks. Color number is ...
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 ...
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 ...
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 ...
3k 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 ...
3k views

### Triangular domino tiling of an almost regular hexagon

Background An almost regular hexagon is a hexagon where all of its internal angles are 120 degrees, and pairs of the opposite sides are parallel and have equal lengths (i.e. a zonogon). The ...
760 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 ...
363 views

### Counting symmetric grid chains

Notation and definitions Let $[n] = \{1, 2, ..., n\}$ denote the set of the first $n$ positive integers. A polygonal chain is a collection of connected line segments. The corner set of a ...
396 views

### Removing points from a triangular array without losing triangles

I have a combinatorics problem that I'd like to put on the OEIS—the problem is that I don't have enough terms. This code challenge is to help me compute more terms, and the winner will be the user ...
420 views

### Roman Numeral Counting

Roman numerals can be (mostly) written in a one column format, because each letter intersects the top and the bottom of the line. For example: I, or 1 intersects ...
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 ...
203 views

### Multigraphs with a given degree sequence

This challenge will give you an input of a degree sequence in the form of a partition of an even number. Your goal will be to write a program that will output the number of loop-free labeled ...
570 views

### Number of distinct tilings of an n X n square with free n-polyominoes

The newest "nice" OEIS sequence, A328020, was just published a few minutes ago. Number of distinct tilings of an n X n square with free n-polyominoes. This sequence counts tilings up to symmetries ...
553 views

### Counting generalized polyominoes

This challenge will have you count pseudo-polyforms on the snub square tiling. I think that this sequence does not yet exist on the OEIS, so this challenge exists to compute as many terms as possible ...
1k views

### Permutations in Disguise

Given a $n$-dimensional vector $v$ with real entries, find a closest permutation $p$ of $(1,2,...,n)$ with respect to the $l_1$-distance. Details If it is more convenient, you can use ...
2k views

### Count the number of shortest paths to n

This code challenge will have you compute the number of ways to reach $n$ starting from $2$ using maps of the form $x \mapsto x + x^j$ (with $j$ a non-negative integer), and doing so in the ...
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 ...
482 views

### Fastest algorithm to output array containing all integers in range excluding duplicate digits

Input is a single integer in ascending digit order. The only valid inputs are: 12 123 1234 ...
5k 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 ...
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, ...
197 views

### Compute my Sacred Geometry [closed]

In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use ...
228 views

### Find all a, b, c, d, e, such that a + b + c + d + e = 1000 with no more than 3 loops [closed]

The rule is: a, b, c, d, e is an integer from 0 to 1000, no relation between ...
2k views

### Is case sensitivity important?

Tom is going to implement a new programming language of his invention. But before actually starting working on it, he wants to know whether his language should be case sensitive or not. On one hand, ...
1k views

### Generate basis elements of the Steenrod algebra

The Steenrod algebra is an important algebra that comes up in algebraic topology. The Steenrod algebra is generated by operators called "Steenrod squares," one exists for each positive integer i. ...
215 views

### Multiplication in the Steenrod Algebra

Here's yet another Steenrod algebra question. Summary of the algorithm: I have a procedure that replaces a list of positive integers with a list of lists of positive integers. You need to repeatedly ...
87 views

### Finding row wise sum of transpose of hv-convex binary matrix [closed]

I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m). ...
1k views

### Code golf: Distributing the balls (I)

Challenge In this task you have compute the number of ways we can distribute A balls into B cells with with every cell having at-least one ball. The inputs A and B are given in a single ...
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 ...
5k views

### Dobble/SpotIt card generator

Introduction Dobble/SpotIt is a card game, where people have to spot same symbol on pair of cards in shortest time, indicate it and move to next pair. Each card has multiple symbols (8 in normal ...
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: ...
5k 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 ...
1k 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 ...
370 views

### Counting the number of restricted forests on the Möbius ladder of length n

OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn. The Challenge The challenge is to write a program that takes an integer as an input ...
534 views

### Forming Polyominoes with a Chain of Rods

Background Consider a (closed) chain of rods, each of which has integer length. How many distinct hole-free polyominoes can you form with a given chain? Or in other words, how many different non-self-...
826 views

### Cycles on the torus

Challenge This challenge will have you write a program that takes in two integers n and m and outputs the number non-...
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 <...
1k views

### The number of reachable snake orientations

This challenge is not about the game Snake. Imagine a 2d snake formed by drawing a horizontal line of length n. At integer points along its body, this snake can ...
2k views

### Is it a shuffle?

Yesterday I asked this question about riffle shuffles. It seems that yesterdays question was a bit too hard so this question is a related but much easier task. Today you are asked to determine if a ...
642 views

### Check if all vowels exist in pairs of strings [closed]

Your program should find the number of string pairs (pairs of 2) that contain all vowels (a e i o u), when given an integer N and ...
318 views

### Unique Brick Tilings Within A Rectangle

I was browsing Stackoverflow and saw this question about tiling an MxN rectangle, and I thought it would be great for golfing. Here is the task. Given the dimension M and N, write a program that ...
3k 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): ...
298 views

### Buy the most appropriate items

A store is having a big sale. If your price reaches $199 or more, you can reduce it by$100. You can buy each product only once. Here's an example list of products: (in order to simplify, the names of ...
711 views

### Number of $n$-carbon alkanes

Given a positive number $n$, find the number of alkanes with $n$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with $n$ nodes, such that every node has ...
311 views

### Generate the k-ary necklaces of length n

The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers ...