# Questions tagged [combinatorics]

For challenges involving combinatorics.

374 questions
Filter by
Sorted by
Tagged with
1k views

### How many ways can you make change?

The "third type of Euler Transform" takes an integer sequence that gives the number of objects of a given weight and outputs a sequences that gives the number of multisets of objects that ...
• 8,811
1k views

### Ways to paint a backbone on a tree

Say I have some unlabelled tree graph: I'll define a "backbone" as a path on a graph that can't be extended - both its ends are at terminal vertices. There are three ways to overlay a ...
• 41.6k
311 views

### Dishonest dungeon staff

This is a joint post with https://puzzling.stackexchange.com/questions/126255/dishonest-dungeon-staff You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal ...
• 151
2k views

### Avoiding Loops!

Given a collection of coloured laces, what would be the probability, $P$, that Alice won't create any loops if, until impossible, they tie two uniformly chosen, free lace ends of differing colours ...
• 109k
1k views

### Counting rankings

There is a competition with $n$ participants in total. Alice is one of the participants. The outcome of the competition is given as a ranking per participant with a possibility of ties; e.g. there ...
• 78.2k
645 views

### Robinson Schensted correspondence

[The explanations of the algorithm come from here. I recommend reading it for a beautiful description of the algorithm.] This challenge is to implement the Robinson Schensted correspondence. Input A ...
• 3,153
1k views

### Expected number of rounds for this labeling scheme

Task Here is an interesting math problem: Let's say that there are $n$ indistinguishable unlabeled objects in a bin. For every "round", pull $k$ objects randomly out of the bin with ...
• 14k
591 views

### List all words following a pattern

This challenge is to list out all possible words which are built from a pattern of syllables. Words are composed by joining syllables together. Syllables are composed of a number of vowels with some ...
• 1,215
2k views

• 50.1k
868 views

### Sniff out biased random permutations

The brilliant engineers at <enter company you love to hate> have struck again. This time they've "revolutionised" the generation of random permutations. "Every great invention is ...
• 16.7k
1k views

### Generate all groupings

Let's define a grouping as a flat list, which is either: just 0 2 groupings followed by the literal integer 2 3 groupings ...
• 24.2k
1k views

### Verify a Superpowerset

A superpowerset (analogous to superpermutation) on $n$ symbols is a string over the alphabet $\{1,2,...,n\}$ such that every subset of $\{1,2,...,n\}$ appears as a substring (in some order). For ...
• 311
618 views

### Output a Steiner quadruple system

A Steiner quadruple system $SQS(n)$ is a collection of subsets (blocks) of size 4 of a set $S$ of size $n$ such that every subset of $S$ of size 3 is in exactly one block. It is easy to show ...
• 3,935
1k views

### Square-free words of a length

A square-free word is a word consisting of arbitrary symbols where the pattern $XX$ (for an arbitrary non-empty word $X$) does not appear. This pattern is termed a "square". For example, ...
• 50.1k
2k views

• 41.6k
2k views

• 50.1k