Questions tagged [counting]

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

Filter by
Sorted by
Tagged with
9
votes
2answers
820 views

Counting islands in Boolean matrices

Given an $n \times m$ Boolean matrix $\mathrm X$, let $0$ entries represent the sea and $1$ entries represent land. Define an island as vertically or horizontally (but not diagonally) adjacent $1$ ...
3
votes
1answer
107 views

Number of states in an AND-OR DAG

Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND ...
8
votes
2answers
841 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
2
votes
3answers
156 views

Count arrays with size n, sum k and largest element m

I'm trying to solve pretty complex problem with combinatorics. Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K ...
0
votes
0answers
38 views

Count submatrices with only zeros for each element of the matrix

Let's say we have given matrix of size $N \cdot M$, only with zeros and ones. For each element in the matrix, we want to count subrectangles that are covering this element and are made only of zeros. ...