Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
4
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
68 views

Sum of k smallest values of affine functions

Assume we have a fixed number of $n$ one-dimensional affine functions of the form $f_i(x) = a_i x + b_i$ for $i \in N = \{1,\ldots,n\}$. Consider some fixed value $k \in \{0,\ldots,n\}$. Let $S_k : \...
2
votes
1answer
261 views

Approaches to the size constrained weighted set cover problem

I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$. Assuming this is a pretty straight-forward variation of weighted set cover I ended ...
1
vote
0answers
94 views

Algorithm better than Greedy for Dominating set

I just want to know that whether there is an algorithm better than the Greedy Algorithm for Dominating set. I know that Greedy gives $O(\log(\Delta))-approx$ and we can not do something better than $...
3
votes
1answer
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$ ...
2
votes
0answers
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 ...
0
votes
0answers
79 views

no of ways to fill a row (1xN grid) with a set of 1D bars with some constraints?

Given a row of length N, and a set of 1D bars having lengths A[1...M], how many ways I can fill the row? A is an integer array, the bars are having dimensions $\{1\times A_1,1\times A_1,1\times A_1,....
3
votes
3answers
261 views

Contained optimal combination of inputs

I have 100 football (soccer) players, each with an "expected score" (higher is better) and price (e.g. 4300 dollars). I want to select the optimal combination of players with the highest combined ...
0
votes
1answer
384 views

A nim game variant with pass move

This variant is almost similar to the normal nim game which states - Two players take turns to remove one or more items from a single, non-empty pile. The player who removes the last item from the ...
1
vote
1answer
51 views

Count combinations differing by fixed number of elements

I'll try to formulate my problem through an example. Lets suppose we have a collection of items of type a,b,c,d,e,f. a1, a5, a7 b2, b3 c5, c6, c7, c8 d4, d5 e1, e2, e3 f3, f7, f8 If we take one ...
3
votes
1answer
726 views

Suitable choice for moderate-size square matrix multiplication?

The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, ...
2
votes
1answer
198 views

How to find subset of vectors whose sum has certain characteristics

Let's say you have list of $n$ vectors with entries from $\{0,1,x\}$ and $x$ is > $n$: $$ \begin{align*} L_0 &= [1,0,x] \\ L_1 &= [1,1,1] \\ L_2 &= [1,0,0] \\ L_3 &= [x,1,0] \\ L_4 &...
5
votes
1answer
175 views

Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$

How many matrices satisfy the following constraints? $n$ rows $n$ columns Cell values are either $0$ or $1$ Sum of any row is at most $m$ sum of any column is at most $m$ Is there a formula or an ...
2
votes
1answer
81 views

Prove that every undirected connected graph with $|V | > 2$ results in a connected graph if two vertices removed.. [duplicate]

How do I go about proving this? Prove that every undirected connected graph with $|V | > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the ...
8
votes
3answers
168 views

Upper bound of of fib(n+2)

I have a homework problem that is perplexing me because the math is beyond what I have done, although we were told that it was unnecessary to solve this mathematically. Just provide a close upper ...
1
vote
3answers
402 views

Combinatorics approach to staircase problem

There are $n$ stairs and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs every time. What is the total number of ways they can reach the top? ...
0
votes
1answer
60 views

Finding alternative way of combinatorial counting

The question is related to databases: There is a relation $R(A_1,A_2,...,A_n)$. Every $(n-2)$ attributes of $R$ forms candidate key. Number of superkeys of $R$ are? I thought if any one of the $(n-...
0
votes
1answer
153 views

Number of combinations to put n items into 2 bags [closed]

I’m currently working on a finger exercise for mit6.00.2x, a MOOC in computaional thinking, and was having some issues. First of all: don’t worry, I don’t need you to do my homework for me, I just ...
3
votes
1answer
928 views

Counting the number of squares in a graph

Given an undirected graph, how would one go about calculating the number of squares in the graph? That is, a square is a cycle of length 4. I know that it is possible to count the number of ...
3
votes
2answers
520 views

Deriving the average number of inversions across all permutations

In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation: $$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \...
0
votes
2answers
369 views

Prove that the set of recursive languages is infinite

I know that set of all deciders is countable. I am wondering whether it is infinite.In other words can we prove that the set of recursive languages is infinite ? Edit : The above question has small ...
3
votes
0answers
37 views

Scheduling problem of average sums with condition

Take a multiset $S=\{s_1,\ldots,s_n\} \subset \mathbb{N}$ and some $k \in \mathbb{N}$. Take $T$ to be the set of all sequences of the form $s_{\pi(1)},\ldots,s_{\pi(i)}$, such that $\sum_{j=1}^{i-1} ...
3
votes
1answer
29 views

Constructing a list of functions/formulas which describes a set of grid points in a 3D matrix

Given a 3D matrix of size $N \times N \times N$, let $\mathcal{S}$ be a set of points in the Matrix and $\mathcal{S}'$ be the complement of $\mathcal{S}$. Can we find a set of equations of the form: $...
4
votes
1answer
330 views

Finding a maximum-weight base of a a matroid, in reverse

Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm: Start with an empty set (by definition of matroid, it is independent). Add ...
2
votes
1answer
73 views

Compact, reversible mapping from set partitions of length k to integers

Given a set $S$ of length $n$, I'm looking to map all the $k$-length partitions of $S$ onto the set of integers such that these integers are as close to 0 as possible. Ideally the range would be $\...
2
votes
1answer
113 views

Minimum number of transpositions

Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \...
2
votes
1answer
105 views

Big Theta for finding combinations of arbitrarily sized subsets from n total elements

Given n elements, where the n elements are grouped into arbitrarily sized subsets, what is the Big Theta (tight bounds) of outputting all permutations of items from each subset? Assume the elements ...
7
votes
2answers
626 views

Finding a fixed-size set whose members are contained by the largest number of other sets

I've been thinking about a problem, inspired by meeting a beginner-level foreign language professor at the Goethe-Institut who learned the five most common languages spoken by students in order to ...
5
votes
1answer
313 views

How to find greatest set intersection of at least a given cardinality?

While dealing with a problem, I uncovered this subproblem: Input: A set of sets $S = \{S_1,...,S_r\}$ where $\mid$ $S_1$ $\cup$ ... $\cup$ $S_r$$\mid = n$, as well as a number $k<n$. Output: A ...
1
vote
1answer
64 views

Faster way of calculating how many ways can $2n$ elements be paired?

So the problem is in how many ways $2n$ elements can be paired, my approach was multiply all odd numbers less then $2n$. $(2n-1)*(2n-3)*...*1$ but my professor claimed it can be done much faster in ...
1
vote
1answer
61 views

Probability distribution of runs given k bits set in an n-bit circular buffer

Imagine you have a circular buffer holding n bits. You (uniformly) randomly set k of those n ...
0
votes
2answers
115 views

Describe an algorithm for painting cards in the following game

It's my first question out here, so please don't judge me too strictly. I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) ...
7
votes
1answer
865 views

Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
3
votes
2answers
175 views

How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?

More specifically, I want to: $^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$ I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j. The answer it gives is correct ...
0
votes
1answer
314 views

What is the cardinality of the set of regular grammars?

What is the cardinality of the set of regular grammars? The caveat is that I'm only interested in grammars which are 'structurally' different. Sorry I don't know how to talk about this in a formal ...
5
votes
1answer
365 views

How much data could I store on a Rubik's Cube?

Google tells me that a standard 3x3x3 Rubik's Cube has 43,252,003,274,489,856,000 permutations. If I wanted to store data on that Rubik's Cube, how much could I store? The only way I see to store ...
2
votes
1answer
195 views

is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance! Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( ...
1
vote
0answers
128 views

Counting the number of non-overlapping squares and cubes in a string

Given a string S of length n that contains exactly $\lceil\frac{n}{3}\rceil$ b's and $\lceil\frac{2n}{3}\rceil$ a's: Suppose the charge is 2 for each non-overlapping occurrence of aaa, and 1 for each ...
1
vote
1answer
662 views

Convert integer of mixed radix to standard positional numeral system and vice versa

I have multiple numbers (e.g. [1, 4, 2]) where each number can be one of a specified range of numbers (e.g. [0-1, 0-5, 0-3]). I ...
1
vote
2answers
317 views

How Is a Computer Able to Store and Quickly Manipulate All the Data Required For A Computer Display?

I did some quick math on how much data is contained on a screen at any given instant and I ended up with a number well beyond what I thought was possible. 256 colors for Red, Green, and Blue each ...
1
vote
1answer
477 views

Letter Combinations of a Phone Number

I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem). Problem statement – Letter Combinations of a ...
0
votes
2answers
27 views

Find k compatible objects with minimum total penalty

Assume we have a set of $n$ objects $X=\{x_1,x_2,\ldots,x_n\}$, where each object $x_i$ has a penalty $p_i$. Additionally, we have a set of incompatibility constraints $C=\{(x_i,x_j),\ldots\}$, where ...
0
votes
0answers
86 views

Get all possible combinations of distributing x*n balls into n boxes

I'm trying to figure out how to get all combinations of putting x*n balls into n boxes. ...
9
votes
0answers
183 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
1
vote
0answers
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 ...
3
votes
1answer
8k views

How many number of different binary trees are possible for a given postorder (or preorder) traversal

I came across the problem: What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C? Now 3 being small number I was quick to draw all possible ...
1
vote
1answer
106 views

Upper bound for #Monotone k-SAT

(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 ...