Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
781 questions
2
votes
0
answers
62
views
Statement on regular language density
On this forum, I've found following statement on densities of regular languages:
The density of a regular language is of the form $\Theta \left( n^k \lambda ^ n \right)$ for some integer $k \geq 0$ ...
- 21
0
votes
1
answer
74
views
Counting Number of Complete Binary Trees with n Nodes
I know that the number of different complete binary tree structures (unlabeled) for n nodes is basically 1, because the structure is fixed.
Now I am trying to find the number of labeled complete ...
- 91
2
votes
0
answers
67
views
Number of non-isomorphic Moore machines with less than four states
does somebody know how to derive a formula for the number of non-isomorphic Moore machines with less than four states and binary input alphabet and binary output alphabet?
- 191
0
votes
0
answers
27
views
What software can compute restricted matching numbers of graphs?
Let $\Delta$ be a simplicial complex and $F, G$ be two facets of $\Delta$. We say that $F$ and $G$ form a gap in $\Delta$ if $F \cap G = \emptyset$ and the induced subcollection on the vertex set $F \...
user181751
1
vote
0
answers
39
views
Transforming undirected trees into rooted directed trees in Macaulay2
I'm working with the NautyGraphs package in Macaulay2, and I use it to generate all the undirected trees with a fixed number of vertices.
For instance:
i23 : g = generateGraphs(10, OnlyTriangleFree =&...
user181751
1
vote
1
answer
104
views
Help understanding how to reduce to a symmetry-based coloring problem (NP-completeness)
I'm working on a theoretical computer science problem and I'm honestly not sure how to approach it — so I’m hoping for some conceptual guidance.
The problem is to show that a specific coloring problem ...
- 11
3
votes
0
answers
127
views
Trilinear sum of characters in $\mathbb{Z}_2^n$
This is my first time asking a question on this site, as I believe my question is probably related to computer science (and possibly to the analysis of Boolean functions), and someone here might be ...
- 131
3
votes
0
answers
47
views
What is a minimal set of combinators capable of performing any tree permutation in a linear setup?
Let's define a Tree of Ints as:
data Tree = Node Tree Tree | Leaf Int
Let X be a source tree, and ...
- 4,219
1
vote
0
answers
52
views
Efficiently Counting Pairs (i, j) with a Given Sum in Range Queries
Given an array $A = (a_1,a_2,\dots,a_n)$, and $q$ queries in the form $(l,r,k)$, for each query I want to find the number of pairs $(i, j)$ such that $l \leq i < j \leq r$ and $a_i + a_j = k$.
I am ...
- 11
5
votes
3
answers
2k
views
Avoid brute forcing all combinations for this optimisation problem
I have a real life problem where I need to join two data sets such that the absolute difference between keys is minimal.
Technically: we have DS1 and ...
- 173
1
vote
1
answer
75
views
Find rank of vector of length $k$ with elements up to $n$ in graded lexicographic order (grlex)
Let $v = (a_1, a_2, …, a_k)$ be a vector of length $k$, such that $0 \leq a_i < n$. Also let $|v| = a_1 + a_2 + \dots + a_k$ be a total degree of $v$. There is finite number of such vectors.
We can ...
- 133
0
votes
1
answer
119
views
How to determine the solvability of an 𝑛 × 𝑛 sliding puzzle efficiently?
I am trying to determine whether a given n × n sliding puzzle configuration is solvable. Given an initial board state as a flattened list, I want a general and efficient algorithm to test its ...
1
vote
1
answer
94
views
Generate new sequence different from all the previous ones
I have a string and I need to generate some new strings that are not in the set I already have. What would be an efficient way to do it?
Average length of a string is 20. Alphabet contains about 100 ...
- 191
1
vote
1
answer
268
views
How to count the number of topological sorts in a directed acyclic graph with multiple roots
I have a task to count the number of possible topological sorts, and it is known that the graph has N vertices and N-1 edges, and the edges are also given.
For example:
N = 4
1 2
1 3
4 3
For this ...
- 13
0
votes
0
answers
34
views
Boolean functions on the hypercube and sensitivity conjecture
I'm reading this paper which relates the sensitivity conjecture to a graph-theoretic question on the hypercube and I'm struggling to understand some things. A Boolean function here is defined as $f: \{...
- 123