All Questions
Tagged with enumerative-combinatorics algorithms
12 questions
8
votes
0
answers
260
views
Efficient listing of ASMs
Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is ...
- 17k
2
votes
1
answer
482
views
Counting $n$-edge directed graphs
I would like to count the $n$-edge directed graphs. The graphs might contain self-loops (edges connecting a vertex to itself) and multiple edges (multiple edges connecting the same pair of vertices). ...
- 21
0
votes
1
answer
116
views
Enumerating (i.e. generating one by one) matrices of given rank over a finite field
Let be given positive integers $m,n,r$, with $r \leq \min(m, n)$, and a finite field of $q$ elements $\mathbb{F}_q$.
I'm looking for an efficient algorithm to enumerate (i.e., generate one by one) all ...
- 43
1
vote
3
answers
176
views
Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
let $\boldsymbol{X}_1,\,\dots,\,\boldsymbol{X}_n$ be well-ordered sets of positive values and $\mathcal{R}:=\lbrace\left(x_1,\,\dots,\,x_n\right)\rbrace = \boldsymbol{X}_1\times\,\dots\,\times\...
- 13.2k
2
votes
0
answers
50
views
Calculating permanents via Branch and Bound
Permanents can be interpreted as counting directed cycle covers of an asymmetric graph with unit cost edge weights.
That interpretation leads to a branch and bound algorithm for calculating the ...
- 13.2k
5
votes
1
answer
196
views
Enumerating antichains modulo permutation
I encountered the following combinatorics problem in my research, and I'd like to know if there is a reference or an easy solution for such a problem.
Given a partially ordered set $\mathscr P$, an ...
- 903
1
vote
1
answer
94
views
Calculating the values of a generalization of binomials to permutations
let $$\Pi\binom{n}{k}:=\mathrm{card}\left( \left\lbrace \lbrace \Pi_1^n\,\cdots\,\Pi_k^n\rbrace\,|\,0\leq \pi_{r,c}\in\sum_{i=1}^k\Pi_i^n\ni\pi_{r,c}\leq 1\right\rbrace\right)$$ be the number of sets ...
- 13.2k
4
votes
2
answers
748
views
Estimate size of graph by taking random walks
Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is:
...
- 523
19
votes
3
answers
2k
views
A generalization of the triangle counting problem for simple weighted graphs
One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...
- 3,463
0
votes
2
answers
318
views
Enumerating m-tuples of Integers Subject to Implication Constraints [closed]
How do I enumerate all $m$-tuples of positive integers $(a_1,...,a_m)$ subject to the following constraints?
For each $i$ in $\{ 1,\ldots,m \}$, there is a number $n_i \geq 0$ such that $a_i \leq n_i$...
- 11
36
votes
3
answers
7k
views
Distinct numbers in multiplication table
Consider the multiplication table for the numbers $1,2,\dots, n$. How many different numbers are there? That is, how many different numbers of the form $ij$ with $1 \le i, j \le n$ are there?
I'm ...
- 2,821
7
votes
4
answers
11k
views
Non-isomorphic graphs of given order.
It is well discussed in many graph theory texts that it is somewhat hard to distinguish non-isomorphic graphs with large order. But as to the construction of all the non-isomorphic graphs of any given ...
- 2,855