Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
23
votes
9answers
3k views

The square root of the square root of the square root of the…

This code-golf challenge will give you an integer n, and ask you to count the number of positive integer sequences \$S = (a_1, a_2, \dots, a_t)\$ such that \$a_1 + ...
10
votes
0answers
110 views

Polygons in a cube

Inspired in part by this Mathologer video on gorgeous visual "shrink" proofs, and my general interest in the topic, this challenge will have you count regular polygons with integer ...
8
votes
2answers
314 views
+200

Arranging Fenceposts

If you want to build a fence and have different length boards available, there are many different ways to set up your posts. So, given a minimum and maximum board length, a number of boards, and the ...
15
votes
11answers
1k views

Rectangles in rectangles

This code-golf challenge will give you two positive integers n and k as inputs and have you count the number of rectangles with ...
28
votes
14answers
2k 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 ...
21
votes
19answers
951 views

Sequences of distinct positive integers

The goal of this challenge is to take a positive integer n and output (in lexicographic order) all sequences \$S = [a_1, a_2, ..., a_t]\$ of distinct positive ...
18
votes
16answers
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 ...
19
votes
2answers
622 views

Cut a triangle into equal-sized parts!

Similar in spirit to Number of distinct tilings of an n X n square with free n-polyominoes and Partition a square grid into parts of equal area, this challenge will have you count ways of partitioning ...
27
votes
4answers
915 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 ...
12
votes
14answers
1k views

How many ways to write numbers as sums of squares?

Task Given two integers \$d\$ and \$n\$, find the number of ways to express \$n\$ as a sum of \$d\$ squares. That is, \$n = r_1^2 + r_2^2 + ... + r_d^2\$, such that \$r_m\$ is an integer for all ...
25
votes
14answers
3k views

Reuse your code!

In this challenge we try to solve two important problems at once. They are: Given integers \$a\$ and \$b\$, tell if \$a^b-1\$ is a prime number. Given integers \$a\$ and \$b\$, return \$a\choose b\$. ...
6
votes
8answers
392 views

m-nomial coefficient

While the binomial coefficient are the coefficients of \$(1+x)^n\$, m-nomial coefficients are the coefficients of \$(1+x+x^2+...+x^{m-1})^n\$. For example, \$m(3,5,6)\$ is the coefficient of \$x^6\$ ...
22
votes
2answers
726 views

Extend the most recent “nice” OEIS sequence: stepping stone puzzle on a grid

Today Neil Sloane of the OEIS sent out an email asking for a confirmation of the current terms, and computation of some larger terms of the latest OEIS sequence A337663 with the keyword "nice&...
50
votes
47answers
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 ...
18
votes
13answers
633 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\$ positive integer parts,...
11
votes
23answers
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 ...
22
votes
35answers
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 ...
35
votes
56answers
7k 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
4answers
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 ...
21
votes
19answers
2k views

Verify a Superpermutation

A superpermutation on n symbols is a string which contains every permutation of n symbols in its body. For instance, 123121321 is a superpermutation on three ...
35
votes
49answers
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 ...
21
votes
2answers
1k 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 ...
14
votes
6answers
533 views

Maximal saturated domino covering of a rectangle

Inspired by this OEIS entry. Background A saturated domino covering is a placement of dominoes over an area such that the dominoes are completely inside the area, the dominoes entirely cover the ...
29
votes
13answers
3k 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. The Sidi polynomials have several interesting properties, but so do their coefficients. The ...
13
votes
6answers
2k views

How many ways to write N as a product of M integers?

Given an integer N, count how many ways it can be expressed as a product of M integers > 1. Input is simply N and M, and output is the total count of distinct integer groups. Meaning you can use an ...
19
votes
2answers
595 views

Tiling a staircase with staircases

Background A staircase polyomino is a polyomino made of unit squares whose shape resembles a staircase. More formally, a staircase polyomino of size \$n\$ is defined as follows: A staircase polyomino ...
13
votes
7answers
919 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 ...
17
votes
7answers
630 views

Combinatorial Decomposition

In the body of this challenge, \$\begin{pmatrix}n\\k\end{pmatrix}\$ is used to represent the number of combinations of \$k\$ elements of \$n\$, also written as \$\frac{n!}{k!(n-k)!}\$ or \$n\mathrm{C}...
22
votes
17answers
2k views

Concentric rings on a snub square tiling

This challenge takes place on the snub square tiling. Start by choosing any triangle, and color it \$c_1\$. Next, find all tiles which touch this triangle at any vertex, and color them \$c_2\$. Next, ...
7
votes
3answers
207 views

Domino Recurrence Generator

Challenge We once had a challenge to count domino tilings of m by n grid, and we all know that, for any fixed number of rows, the number of domino tilings by columns forms a linear recurrence. Then ...
39
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 ...
9
votes
11answers
764 views

Counting King's Hamiltonian Paths through 3-by-N grid

Background A Hamiltonian path is a path on a graph that steps through its vertices exactly once. On a grid, this means stepping through every cell exactly once. On a square grid, a Chess King can move ...
12
votes
29answers
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: ...
17
votes
2answers
407 views

What is the fastest safe way down a mountain?

Intro Help! I'm stuck on a snow-covered mountain and I need to get down as fast as possible, preferably without dying. I have a map showing how high each part of the mountain is above the normal ...
14
votes
5answers
595 views

Placing Dominoes On A Chequerboard

How many ways can one place (unlabelled) dominoes on a square chequerboard such that the number placed horizontally is equal to the number placed vertically? The dominoes must align with, and may not ...
20
votes
14answers
1k views

Penney-Conway odds

Background Penney's game is a two-player game about coin tossing. Player A announces a sequence of heads and tails of length \$n\$, then player B selects a different sequence of same length. The ...
10
votes
21answers
1k views

Generate ordered combinations with repetition

Given a string of different characters, and a number n, generate all the ordered combinations with repetition, of length 1 to n, using those characters. Another way to define it is to see the given ...
29
votes
4answers
920 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 ...
15
votes
16answers
2k views

Computing a specific coefficient in a product of polynomials

Generator functions This gives the context for why this challenge came to life. Feel free to ignore. Generator functions are a nice way of encoding the solution to a problem of combinatorics. You ...
16
votes
1answer
199 views

Rubik's Snakes! (Part 1)

The Rubik's Snake (or Rubik's Twist) is a toy consisting of several triangular prisms strung together in a line in such a way that the pieces can be rotated about one another in 90 degree turns. Any ...
9
votes
3answers
390 views

Triangles in a tetrahedron

The goal of this challenge is to extend the OEIS sequence A334581. Number of ways to choose \$3\$ points that form an equilateral triangle from the \$\binom{n+2}{3}\$ points in a regular tetrahedral ...
9
votes
1answer
199 views

Counting hypercube Tetris pieces

Consider the Tetris pieces, but made out of some number of (hyper)cubes instead of four squares, where two blocks are considered the same if one is a rotation, reflection, or translation of another. ...
17
votes
0answers
366 views

Acyclic orientations of an n-dimensional cube

The goal of this challenge is to check and extend the OEIS sequence A334248: Number of distinct acyclic orientations of the edges of an n-dimensional cube. Take an n-dimensional cube (if n=1, this is ...
8
votes
1answer
355 views

Infinite Snake game

Infinite Snake is just like the video game Snake, except for that the snake is infinitely long, there are no items to eat, and the Snake needs to move in a repeating ...
19
votes
2answers
328 views

Exactly N in a line

Given a number N from 2 to 8, place any nonzero number of queens on a grid of any size so that every queen has exactly N queens (counting itself) in each of its row, column, and each diagonal. This ...
10
votes
18answers
929 views

How Many Ways To Empty The Glove Box?

Inspired by this glove-themed 538 Riddler Express Puzzle. Task You are given a positive integer n, and a list ...
21
votes
6answers
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 ...
2
votes
1answer
259 views

count number of valid, unique sequences for moving on a 1xn board [closed]

There's a board with n squares in a horizontal row. You start in the leftmost square, and roll a 3-faced dice. 3 possible outcomes for a single roll of the die: Left: you move 1 step to the left, ...
11
votes
2answers
366 views

Spanning paths in a tournament on n nodes

The goal of this challenge is to extend the On-Line Encyclopedia of Integer Sequences (OEIS) sequence A038375. Maximal number of spanning paths in tournament on n nodes. A tournament on \$n\$ ...
14
votes
6answers
635 views

Calculate the average longest common substring exactly

[Question inspired by Can you calculate the average Levenshtein distance exactly? . Thank you Anush. ] The longest common substring between two strings is the longest substring which is common to ...

1
2 3 4 5 6