# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

513 questions
Filter by
Sorted by
Tagged with
206 views

### lower bound for Renyi–Ulam Game with lies

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ). Game : $A$ chooses an element in {1,2....,n} $B$ tries to ...
91 views

### Sum collision from two lists of numbers

Suppose you have two large lists of integers of length $N$, and you want to find two pairs $(a_1, b_1)$, $(a_2, b_2)$ from the lists such that $a_1 + b_1 = a_2 + b_2$ (modulo the integer width). Say ...
90 views

### Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux. But, since every permutation has a unique Young's tableau, there seems no reason as ...
36 views

### A+B Problem $o(n^2)$ solution? [duplicate]

Does this problem have a solution with $o(n^2)$ time complexity? If so, what would be an example of such a solution? Given $N$ integers in the range $[−50\ 000,\ 50\ 000]$, how many ways are ...
68 views

376 views

### Counting Total Number of Non-Equivalent Configurations in a 2-D Grid

This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both. Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ ...
32 views

### Is there a skippable, countable generator for unique permutations up to some symmetry?

Is there a good algorithm for generating all and only the unique permutations of a finite set respecting some kind of symmetry? For example, in Klondike solitaire, the two black suits are ...
79 views

29 views

113 views

152 views

### How to encode each possible b-tree of a sequence of n numbers?

Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
(I've recently started studying satisfiability problems. I've tried to be as clear as possible, but I'm not sure if all of the terminology used is correct.) Consider a collection of $n$ Boolean ...