# Questions tagged [combinatorics]

For challenges involving combinatorics.

266 questions
Filter by
Sorted by
Tagged with
847 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 ...
2k views

### Fun with strings and numbers

Here's a programming puzzle for you: Given a list of pairs of strings and corresponding numbers, for example, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]...
3k views

### The Unique Padlock PIN List!

Introduction In a private chat, a friend of mine apparently recently stumbled across a security system which has the following two restrictions on its valid pins: Each digit must be unique (that is "...
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 ...
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)$. ...
517 views

### Count the number of ways of putting balls into bins

In this task you are given an odd number of white balls and the same number of black balls. The task is to count all the ways of putting the balls into bins so that in each bin there is an odd number ...
342 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 ...
76 views

### Count stacking sequences [duplicate]

Given a list of stack heights, calculate the number of ways those heights could have been arrived at by stacking blocks one at a time. Shortest code wins. Test cases: ...
420 views

### Counting polystrips

Polystrips are a subset of polyominoes conforming to the following rules: each piece consist of 1 or more cells no cell can have more than two neighbours the cells should not enclose a hole Free ...
837 views

### Sum of combinations with repetition

Write the shortest code you can solving the following problem: Input: An integer X with 2 <= X and X <= 100 Output: ...
859 views

### Conjugate permutations

A permutation of size n is a reordering of the first n positive integers. (meaning each integer appears once and exactly once). Permutations can be treated like functions that change the order of a ...
461 views

### Deranged Rearrangements

Your task is to write a computer program such that when it is cut up into lines (split on the newline character) every arrangement of the lines will output a different number between 1 and n! (where n ...
428 views

### Alice's Tea Party

There are n places set around a circular table. Alice is sat on one of them. At each place, there's a cake. Alice eats her cake, but it doesn't taste very nice. Then the Mad Hatter comes in. He gives ...
2k views

### Find The Rank Of A Word

Definition The rank of a word is defined as the position of the word when all the possible permutations (or arrangements) of its letters are arranged alphabetically, like in a dictionary, no matter ...
233 views

### Compute number of matrices with appropriate sums

When multiplying monomials in the Milnor basis for the Steenrod algebra, part of the algorithm involves enumerating certain "allowable matrices". Given two lists of nonnegative integers r1, ... ,rm ...
908 views

### Mod 2 Multinomial coefficients

quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2. Given a ...
339 views

### Integer triangles with perimeter less than n

Definition An "integer triangle" is one with integer coordinates. For example the following triangle is an integer triangle: ...
833 views

### ​L​o​o​p​ ​I​t​

Note: The title of this question should be "Loop It", but because title needs to be at least 15 characters, there are some invisible spaces. This note is such that the challenge can be searched for. ...
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 ...
2k views

### Single swaps of an array

Inspired by Taken from a question at Stack Overflow. The challenge Given an integer n>1, output all arrays that can be obtained by swapping exactly two entries ...
499 views

### How many shuffles

A riffle shuffle is a type of shuffle where the deck is split into two partitions and the partitions are then spliced back together to create a new shuffled deck. The cards are spliced together in ...
201 views

### Prefixless Palindromes

Write a program or function that takes N, and S and outputs the number of palindromes of length S you can build using an alphabet of size N such that any prefix of size between 2 and S-1 is not a ...
271 views

### Now we're thinking in n dimensions!

The question: Given an a number n ≥ 2, how many distinct pairs of points on an n-dimensional ...
754 views

### XKCD Calendar Facts

Inspiration. Posted with permission. Print one of the possible XKCD calendar "facts": You can get the raw text and structure from my APL reference implementation or from Explain XKCD's transcript (...
2k views

### Enumerate all possible grids of integers with constraints

Problem Consider a square 3 by 3 grid of non-negative integers. For each row i the sum of the integers is set to be r_i. ...
782 views

### Hand patterns in a card game

A deck of cards is the Cartesian product of S suits and R ranks. Many, though not all, card games use ...
264 views

### Bobby's Booby-Trapped Safe

Bobby's booby-trapped safe requires an n-digit code to unlock it. Alex has a probe which can test combinations without typing them onto the safe. The probe responds Fail if no individual digit is the ...
922 views

### Pick-flatten a list

Consider the process of "picking" a nested list. Picking is defined as follows: If the argument is a list, take an element from the list at random (uniformly), and pick from that. If the argument is ...
565 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 ...
528 views

### Determine How many Wheels There Are

Non-math explanation This is an explanation that is meant to be approachable regardless of your background. It does unfortunately involve some math, but should be understandable to most people with a ...
1k views

### Number of distinct non-empty subsequences of binary expansion

A subsequence is any sequence that you can get from another by deleting any amount of characters. The distinct non-empty subsequences of 100 are ...
194 views

### Those annoying grasshoppers [closed]

The problem #6 of IMO 2009 reads: Let a 1, a 2, a 3, ..., a n, be distinct positive integers and let T be a set of n-1positive integers not containing a 1+a 2+a 3+...+a n, A grasshopper is to ...
364 views

### Distinct Reversible Primitive Binary Necklaces

Introduction - What is a necklace? A necklace is something that OEIS people are obsessed with. The OEIS challenge has like 5 necklace sequences. A binary necklace of length ...
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 ...
704 views

### Restricted Integer Partitions

Pk(n) means the amount of partitions of n into exactly k parts. Given n and ...
863 views

### How many ways can a road cross a river?

Imagine a straight river and a road that goes across the river n times through bridges. The road does not loop on itself and is infinitely long. This road would be considered an open meander. An open ...
1k views

### How many partitions contain only perfect squares?

Given a non-negative integer or a list of digits, determine in how many ways can the number be formed by concatenating square numbers, which may have leading zeroes. Examples ...
443 views

### Maximum number of distinct substrings

Description Given a length n, and an alphabet size k>0, your program must determine the number of strings with those ...
1k views

You might already be familiar with the game: Basketball FRVR in facebook. There are two types of score you can make: A virgin-shot:(we call it so in our country :D) When the ball enters the basket ...
341 views

### Lyndon word factorization

Background A Lyndon word is a non-empty string which is strictly lexicographically smaller than all its other rotations. It is possible to factor any string uniquely as the concatenation of Lyndon ...
842 views

### All non-ordered pairs between the elements of an array

Task: Return an array with all possible pairs between the elements of an array. Example From a=["a", "b", "c", "d"]; return ...
458 views

### Compute OEIS A005434

The task is to compute OEIS A005434 as quickly as possible. Consider a binary string S of length n. Indexing from ...
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 ...
134 views

### Rooting for Trees With the Right Nodes

Background A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent ...
555 views

### Roll to see all sides!

Let's say you have a 20-sided die. You start rolling that die and have to roll it a few dozen times before you finally roll all 20 values. You wonder, how many rolls do I need before I get a 50% ...
1k views

### Finding approximate correlations

Consider a binary string S of length n. Indexing from 1, we can compute the Hamming ...
181 views

### Find Subset Factors

Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example ...
633 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 ...