1,006 reputation
621
bio website jacquerie.github.io
location Pisa, Italy
age 27
visits member for 4 years
seen 7 hours ago

I'm a bad student of Mathematics Computer Science, interested in too many things, good in none.


1d
awarded  Constituent
2d
awarded  Nice Question
2d
comment How many “good” graphs of size $n$ are there?
I accepted this answer because it's the easiest to compute: just memoize the recursive calls to $T$.
2d
accepted How many “good” graphs of size $n$ are there?
2d
revised How many “good” graphs of size $n$ are there?
Recomputed T(5).
2d
comment How many “good” graphs of size $n$ are there?
Ok, I uncovered a mistake in my enumeration for $T(5)$ and now I get 944 too.
Dec
18
comment How many “good” graphs of size $n$ are there?
Thank you for your answer. I really wish I could follow it, but I'm losing you right at the beginning when you write $\mathcal{E} = \mathfrak{P}(\mathcal{Q})$. What's the meaning of $\mathfrak{P}$?
Dec
17
comment How many “good” graphs of size $n$ are there?
I wouldn't be surprised if I made some mistake calculating $T(5)$. I'd be much more surprised if your simpler (albeit recursive) formula matches the one by @jschnei!
Dec
17
comment How many “good” graphs of size $n$ are there?
Ah, yes, while writing this question I learned that this kind of graph is called a "functional graph" (en.wikipedia.org/wiki/Pseudoforest#Graphs_of_functions) as it can be interpreted as a function.
Dec
17
revised How many “good” graphs of size $n$ are there?
Fix a count in T(4)
Dec
17
asked How many “good” graphs of size $n$ are there?
Dec
16
comment Help with a recurrence with even and odd terms
@ScottHarris No, I just used the standard Python integer type.
Dec
15
comment Help with a recurrence with even and odd terms
I just got this problem in Google Foobar. I ended up writing a very simple program running two binary searches using a memoized function that computes the recursion. I didn't run into any performance issues with this approach, even using Python 2.7.
Dec
14
comment graph theory “ three nodes of degree 0 1 3 respectively”
Now I agree! I think this question boils down to "Is your graph simple?", a concept which the OP should understand.
Dec
14
comment graph theory “ three nodes of degree 0 1 3 respectively”
I disagree with your edit. Check my example in the comments to the question.
Dec
14
comment graph theory “ three nodes of degree 0 1 3 respectively”
If your graph isn't simple, consider a graph on three vertices $u,v,w$ where $u$ is connected to itself and $v$. $u$ has degree 3, $v$ has degree 1, and $w$ has degree 0.
Dec
14
comment Number of ways to connect N nodes with K edges.
Take a look at this question and its comments.
Dec
12
revised Minimal number of moves needed to solve a “Lights Out” variant
added 234 characters in body
Dec
11
accepted Which algorithms are commonly used to solve this kind of Binary Integer Programming problem?
Dec
11
comment Which algorithms are commonly used to solve this kind of Binary Integer Programming problem?
Thank you for your answer. Unfortunately my matrices are not unimodular (for instance, $\text{det}(A_2) = -3$), therefore standard LP methods don't apply. Branch and Bound algorithms look promising, and Chapter 8 of your notes looks nice. Thank you!