User christopher creutzig - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T11:29:03Z http://mathoverflow.net/feeds/user/2933 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37377/how-to-describe-a-tree-depth-degree-balance-what-else/37401#37401 Answer by Christopher Creutzig for How to describe a tree? (depth, degree, balance, ... what else?) Christopher Creutzig 2010-09-01T16:53:21Z 2010-09-01T16:53:21Z <p>As others indicated, trees are an active research area and there are lots of characteristics to choose from. For mind maps especially, the following characteristics come to mind:</p> <ul> <li>fan-out: every node has a fan-out. The average/min/max fan-out of non-leaf nodes could be of interest</li> <li>longest path: Similar to depth, but ignoring the current root node</li> <li>average length to leafs, the distribution of these lengths (the statistics of these should give you various possible measures of balanced-ness)</li> <li>number of distinct labellings (up to isomorphisms): This indicates how asymmetric the tree is</li> </ul> http://mathoverflow.net/questions/14481/calculate-percentiles-from-a-histogram/14482#14482 Answer by Christopher Creutzig for calculate percentiles from a histogram Christopher Creutzig 2010-02-07T10:47:22Z 2010-02-07T10:47:22Z <p>A histogram gives you the number $n_i$ of observations between some $x_i$ and $x_{i+1}$. I'm assuming a total of $n$ observation. So, to get an approximation for the upper $p$-percentile, you want to find the maximal $j$ such that $\sum_{i=j}^\infty n_i\geq p*n$. Then, the empirical upper $p$-percentile is between $x_j$ and $x_{j+1}$.</p> http://mathoverflow.net/questions/12967/combinatorial-sequences-whose-ratios-a-n1-a-n-are-integers/13730#13730 Answer by Christopher Creutzig for Combinatorial sequences whose ratios $a_{n+1}/a_{n}$ are integers. Christopher Creutzig 2010-02-01T19:58:54Z 2010-02-01T19:58:54Z <p>There are 651 sequences in the <a href="http://www.research.att.com/njas/sequences/index.html?q=quotient" rel="nofollow">OEIS</a> qith the word “quotient” in their descriptions, does that help?</p> http://mathoverflow.net/questions/8741/justifying-a-theory-by-a-seemingly-unrelated-example/12324#12324 Answer by Christopher Creutzig for Justifying a theory by a seemingly unrelated example Christopher Creutzig 2010-01-19T17:48:30Z 2010-01-19T17:48:30Z <p>Proving the termination of <a href="http://en.wikipedia.org/wiki/Goodstein%27s%5Ftheorem" rel="nofollow">Goodstein sequences</a> (a problem in natural numbers) via arithmetic on infinite ordinals.</p> http://mathoverflow.net/questions/10266/counting-lattice-points-on-an-n-simplex/10396#10396 Answer by Christopher Creutzig for Counting lattice points on an n-simplex Christopher Creutzig 2010-01-01T20:00:31Z 2010-01-02T22:02:42Z <p><strike>From your problem description, I assume the $x_i$ from the first two paragraphs are what is called $r_i$ later.</strike> I do not yet have a complete answer, but would like to point out some observations and ideas (sorry, I'm not allowed to write comments yet):</p> <p>It seems to me that we can, without loss of generality, assume the $x_i$ to be commensurable. Otherwise, split $S\in\mathbb{Z}[x_1,\dots,x_n]$ into a representation wrt a basis of $\mathbb{Z}[x_1,\dots,x_n]$.</p> <p>Thus, by multiplying through with a suitable constant, we can assume that the $x_i$ are positive integers. We may also assume $\gcd(x_1,\dots,x_n)=1$, since otherwise, any $S$ for which the equation has a solution is also divisible by this gcd, which allows dividing the whole equation. *Edit: Both of these simplifying assumptions shift the set of solutions (to solutions for some other $S$ and $r_1,\dots,r_n$, but in a bijective way.*</p> <p>The number of solutions for any particular $S$ and $x_1,\dots,x_n$ can be counted using generating functions (similar to Polya's method for counting possibilities of giving change); with your example $S=98\,a_1+99\,a_2$ and $0 \leq a_1,a_2 \leq 100$, the number of solutions for $S$ is the coefficient of $x^S$ in the polynomial $(x^{98}+x^{2\cdot98}+\cdots+x^{100\cdot98})\,(x^{99}+x^{2\cdot99}+\cdots+x^{100\cdot99})$, whose lowest exponent with coefficient larger than $1$ is $9899$.</p> <p><hr /></p> <p>I'm not sure I've got a good way of explaining this. Essentially, the first of these polynomials is the generating function for the number of solutions for $S=98\,a_1$ and the second is the generating function for the number of solutions for $S=99\,a_2$. Since in these generating functions, the $S$ values are in the exponents, summation of the $S$ values corresponds to multiplication.</p> <p>If you wanted to write a computer program to find the smallest $S$ such that the corresponding coefficient in the generating function as given above fulfills some condition (e.g., is larger than $1$), it would probably be a good idea to use standard written multiplication and use a heap structure for carrying out the steps. Such an implementation would provide a stream of coefficient/exponent pairs and can also use such as one of its two inputs, which means that the multiplication of very many polynomials can be performed with little memory overhead, especially without needing to store all the coefficients already checked and found not interesting, and the calculation can stop almost without computing anything beyond the first “interesting” term.</p> http://mathoverflow.net/questions/37377/how-to-describe-a-tree-depth-degree-balance-what-else/37401#37401 Comment by Christopher Creutzig Christopher Creutzig 2010-09-04T08:24:16Z 2010-09-04T08:24:16Z @JW: In an undirected graph, degree - 1, right. Else, outdegree - indegree. From what I have seen, this term is mostly used when the trees describe some sort of process or search space.