# Questions tagged [counting]

The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.

171 questions
Filter by
Sorted by
Tagged with
14 views

### Counting all subsequences constrained to a condition

I was trying to find all subsequences constrained to the following conditions: remove element from the end. remove element from the beginning. remove element from both sides. For example, given the ...
19 views

### Count number of permutation under certain condition [closed]

I am new to this community and don't know well how to ask questions. Please give any comments if I made a mistake The question is how many permutations of input numbers exist under certain. K is any ...
26 views

### Determining the number of reachable vertices from every vertex in a directed acyclic graph

Let $G = (V, E)$ be a directed acyclic graph, which is quite sparse (in the examples I have in mind, $|E| \approx 10|V|$ or so). For each vertex $v \in V$, let $f(v)$ be the number of vertices ...
34 views

### How many functions require precisely $n^2$ gates?

I'm trying to determine an asymptotic bound on the cardinality of the following set of functions. It is the functions with $n$-bit inputs, $\{0,1\}$ output, and requires precisely $n^2$ NAND gates. I'...
45 views

19 views

### Calculating Time Complexity of Algorithm Using Incrementor Variable [duplicate]

I am trying to calculate the time complexity of an algorithm using n in the code below. I have a working solution to a coding challenge to sort a stack using only ...
313 views

### Number of ways painting graph in two colors, such that two nodes of same color are linked by edge

We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must ...
126 views

### Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems

I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an ...
55 views

### Estimation of the number of solutions by Counting

This is a question from a quantum computation textbook. Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
474 views

### How to find the Big-O for finding combinations of balanced parentheses?

Given n pairs of parentheses, a function which returns the total number of all combinations well-formed parentheses could be: ...
170 views

### Prove that this language is NP-Hard

Given $$\mathrm{\#3SAT} = \{ (w, y) \mid w\text{ is a \mathrm{3SAT} instance with at least y satisfying assignments}\}\,,$$ prove that $\mathrm{\#3SAT}$ is NP-Hard. I am currently stuck with ...
67 views

### Why does not valiant's reduction show NP=RP?

Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\#SAT$. We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in ...
I am reading CLRS relating to perfect hashing. When computing the $$\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]$$ where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...