Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
15
votes
15answers
3k views

Stack Exchange Answerer

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 ...
20
votes
5answers
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 ...
23
votes
27answers
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 ...
13
votes
1answer
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 ...
12
votes
8answers
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 ...
35
votes
52answers
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 ...
27
votes
17answers
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 ...
28
votes
14answers
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 ...
28
votes
20answers
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 ...
22
votes
15answers
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 ...
22
votes
2answers
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 ...
15
votes
1answer
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 ...
17
votes
3answers
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 ...
14
votes
6answers
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 ...
22
votes
42answers
3k 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 ...
6
votes
3answers
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 ...
17
votes
2answers
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 ...
12
votes
2answers
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 ...
17
votes
14answers
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 ...
21
votes
10answers
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 ...
38
votes
45answers
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 ...
0
votes
5answers
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 ...
23
votes
25answers
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 ...
32
votes
23answers
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, ...
8
votes
1answer
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 ...
-1
votes
3answers
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 ...
13
votes
11answers
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, ...
16
votes
11answers
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. ...
3
votes
1answer
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 ...
1
vote
0answers
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). ...
11
votes
12answers
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 ...
30
votes
17answers
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
3answers
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 ...
11
votes
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: ...
35
votes
21answers
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 ...
27
votes
18answers
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 ...
13
votes
3answers
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 ...
20
votes
2answers
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-...
20
votes
8answers
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-...
43
votes
19answers
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 <...
11
votes
2answers
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 ...
19
votes
14answers
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 ...
6
votes
2answers
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 ...
13
votes
6answers
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 ...
21
votes
25answers
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): ...
6
votes
2answers
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 ...
16
votes
4answers
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 ...
6
votes
5answers
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 ...
16
votes
1answer
325 views

Permutations such that no k+2 points fall on any polynomial of degree k

Description Let a permutation of the integers {1, 2, ..., n} be called minimally interpolable if no set of k+2 points (together ...
17
votes
1answer
291 views

Partition a square grid into parts of equal area

This challenge is based on the following puzzle: You are given an n by n grid with n cells ...