User brian hopkins - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T19:53:37Z http://mathoverflow.net/feeds/user/14807 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/126794/citation-for-subset-complement-result Citation for subset complement result Brian Hopkins 2013-04-07T18:13:24Z 2013-04-07T18:13:24Z <p>Let $S=\lbrace s_1,\ldots,s_n \rbrace \subset \lbrace1,\ldots,2n\rbrace$. Consider two operations on $S$: the complement $C(S)=\lbrace 1,\ldots,2n \rbrace \setminus S$ and a reflection* $R(S)=\lbrace2n+1−s_1,\ldots,2n+1−s_n\rbrace$. In general, $C(S) \ne R(S)$, but the sums of their elements are equal.</p> <p>E.g., $S=\lbrace3,4,5\rbrace \subset \lbrace1,\ldots,6\rbrace$ has $C(S)=\lbrace1,2,6\rbrace$, sum 9, and $R(S)=\lbrace2,3,4\rbrace$, sum 9.</p> <p>My question is <em>not</em> how to prove this (it's a nice proof appropriate for a discrete math course), rather <strong>the history of this result or at least a citation</strong>. For me, this arose in looking at applications of permutations to fair division of indivisible goods.</p> <p>Footnote * This operation $R$ is also called the complement in Egge, Annals of Combinatorics, 2007; Marc van Leeuwen suggested calling it reflection to avoid confusion.</p> <p>Caveat: I recently ran this question on math.stackexchange where, despite a bonus, it generated no answers. I'm still figuring out which site is better for certain questions. </p> http://mathoverflow.net/questions/50343/what-would-you-want-to-see-at-the-museum-of-mathematics/115052#115052 Answer by Brian Hopkins for What would you want to see at the Museum of Mathematics? Brian Hopkins 2012-12-01T05:24:34Z 2012-12-01T05:24:34Z <p>As a late adapter to smart phones, I just recently started idling away some time playing the popular app Flow Free (Big Duck Games). The goal is to connect pairs of dots of the same color with grid paths that do not intersect and cover the entire grid. It makes me think of the Gessel-Viennot lemma about a determinant counting nonintersecting sets of paths (although there often only moves right and up are allowed).</p> <p>One could make a computer display where the pairs of dots have a unique set of nonintersecting paths. An initial step could lead visitors through the number of paths between two points being counted by binomial coefficients. Then finding a set of nonintersecting paths is similar to the game (same sort of touchscreen interface), with the bonus that your work shows that a particular determinant is 1 (without all the arithmetic and plus / minus signs).</p> <p>The same interface could have an exploration of paths strictly below the diagonal that lead to Catalan numbers, which connects to a whole host of visually engaging things such as triangulating regular polygons and making "penny piles" (Richard Stanley is up to 202 things counted by these numbers -- that could be a whole special exhibit).</p> http://mathoverflow.net/questions/104826/explicit-formula-for-the-number-of-compositions-with-m-strictly-positive-parts-bo/106161#106161 Answer by Brian Hopkins for Explicit formula for the number of compositions with m strictly positive parts bounded by n? Brian Hopkins 2012-09-02T05:27:03Z 2012-09-02T14:46:58Z <p>Heubach and Mansour's <em>Combinatorics of Compositions and Words</em> (CRC 2010) call these "limited" in an exercise (copied below), although I have not found that terminology elsewhere. Part 2 suggests there is a "simple" formula for what you want.</p> <p>p85, Exercise 3.12</p> <p>A composition $\sigma = \sigma_1 \cdots \sigma_m$ of $n$ with $m$ parts is said to be <em>limited</em> if $1 \leq \sigma_i \leq n_i$ for all $i = 1, 2, \ldots, n$. [[I think that should be $1, 2, \ldots m$.]]</p> <p>(1) Derive a formula for the generating function for the number of limited compositions of $n$.</p> <p>(2) Using Part (1), obtain a simple formula for the case $n_i = k$ for all $i$.</p> <p>(3) Prove that the number of limited compositions of $n$ is given by $F_{n+1}$ [[Fibonacci]] when $n_i = 2$ for all $i$.</p> <hr> <p>I wanted more room to follow up on Douglas' comment than a comment would allow.</p> <p>Douglas, I believe you're right, that everything comes down to essentially Pietro's generating function and the summation you gave in a comment there. Let me just add some other names used for the numbers that answer Fink's original question.</p> <p>For maximum part $k = 2$, as in the Heubach &amp; Mansour exercise part (3) above, there are $F_{n+1}$ (Fibonacci) limited compositions of $n$. The number with $m$ parts is $\binom{m}{n-m}$ (there are $n-m$ 2's and $2m-n$ 1's). The connection between these binomial coefficients and the Fibonacci number is often expressed as sums of diagonal entries in Pascal's triangle; proving the identity in terms of limited compositions is the basis of Benjamin &amp; Quinn's <em>Proofs that Really Count</em> (MAA 2003, Identity 4).</p> <p>For maximum part $k = 3$, Fibonacci numbers are replaced by "tribonacci" numbers (recurrence $a_n = a_{n-1}+a_{n-2}+a_{n-3}$) and binomial coefficients are replaced by trinomial coefficients, so not Pascal's triangle of coefficients of $(1+x)^n$ but coefficients of $(1+x+x^2)^n$, studied by Euler (see <a href="http://arXiv.org/abs/math.HO/0505425" rel="nofollow">http://arXiv.org/abs/math.HO/0505425</a>). For $k = 4$ the total number of limited compositions are given by "tetranacci" numbers (OEIS <a href="http://oeis.org/A000078" rel="nofollow">http://oeis.org/A000078</a>) and the number with $m$ parts is given by "quadronomial" coefficients (http://oeis.org/A008287). A comment for that integer sequence describes the general result:</p> <blockquote> <p>In general, the entry $(n,k)$ of the ($\ell$+1)-nomial triangle gives the number of compositions of $k$ into $n$ parts $p$, each part $0 \leq p \leq \ell$. [Steffen Eger, Jun 18 2011] </p> </blockquote> http://mathoverflow.net/questions/16107/hamiltonian-paths-where-the-vertices-are-integer-partitions/102510#102510 Answer by Brian Hopkins for Hamiltonian paths where the vertices are integer partitions Brian Hopkins 2012-07-18T05:30:26Z 2012-07-18T05:30:26Z <p>If you mean to allow any part to go down 1 and any part (or 0) to go up 1, while maintaining non-increasing order, then Carla Savage's 1989 paper does in fact solve your problem (without requiring "double moves" as in the 10th listed partition of 7 above).</p> <p>There are refinements of this operation in the literature. If you only allow a dot to "fall" into an adjacent part, i.e., from $(\ldots, p_i, p_{i+1}, \ldots)$ with $p_i \geq p_{i+1}+2$ to $(\ldots, p_i - 1, p_{i+1}+1, \ldots)$, that is called the "sandpile operation" or Brylawski's vertical rule. There is a transpose horizontal rule, and restictions of these called $\theta$ operations and "ice pile" operations, respectively. For some of these operations, the set of partitions of $n$ is not a connected graph, much less one with a Hamiltonian path. A survey article on these operations is available at <a href="http://www-rp.lip6.fr/~latapy/Publis/tcs04a.pdf" rel="nofollow">http://www-rp.lip6.fr/~latapy/Publis/tcs04a.pdf</a></p> http://mathoverflow.net/questions/63561/fibonacci-compositions-history Fibonacci, compositions, history Brian Hopkins 2011-04-30T21:57:16Z 2012-02-11T06:06:08Z <p>There are three basic families of restricted compositions (ordered partitions) that are enumerated by the Fibonacci numbers (with offsets):</p> <p>a) compositions with parts from {1,2} (e.g., 2+2 = 2+1+1 = 1+2+1 = 1+1+2 = 1+1+1+1)</p> <p>b) compositions that do not have 1 as a part (e.g., 6 = 4+2 = 3+3 = 2+4 = 2+2+2)</p> <p>c) compositions that only have odd parts (e.g., 5 = 3+1+1 = 1+3+1 = 1+1+3 = 1+1+1+1+1)</p> <p>The connection between (a) &amp; the Fibonacci numbers traces back to the analysis of Vedic poetry in the first millennium C.E., at least (Singh, Hist. Math. 12, 1985). </p> <p>Cayley made the connection to (b) in 1876 (Messenger of Mathematics). </p> <p>Who first established the connection with (c), odd-part compositions? It was known by 1969 (Hoggatt &amp; Lind, Fib. Quart.), but I suspect it was done before that. Thanks for any assistance, especially with citations.</p> <p>BOUNTY! Not sure how much this incentivizes responses, but it would be nice to figure this out. By the way, I have queried Art Benjamin, Neville Robbins, and Doug Lind about this (Doug modestly mentioned of the 1969 article It's even possible this was an original result.'').</p> http://mathoverflow.net/questions/57971/does-this-type-of-partition-have-a-name/80791#80791 Answer by Brian Hopkins for Does this type of partition have a name? Brian Hopkins 2011-11-13T01:30:49Z 2011-11-13T01:30:49Z <p>These are counted in <a href="http://oeis.org/A001970" rel="nofollow">OEIS A001970</a> where they are called "partitions of partitions" along with some other interpretations. As Simon noted, they do differ from the more-studied plane partitions.</p> http://mathoverflow.net/questions/10282/alternative-undergraduate-analysis-texts/69763#69763 Answer by Brian Hopkins for Alternative Undergraduate Analysis Texts Brian Hopkins 2011-07-08T02:40:31Z 2011-07-08T02:40:31Z <p>A very alternative approach is Carol Schumacher's <em>Closer and Closer: Introducing Real Analysis</em> which uses inquiry-based learning / the Moore method. (http://www.jblearning.com/catalog/9780763735937/)</p> http://mathoverflow.net/questions/64817/identifying-the-generating-function-ga-z-sum-n0-infty-an-zn1n/64864#64864 Answer by Brian Hopkins for Identifying the generating function $G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}.$ Brian Hopkins 2011-05-13T04:01:01Z 2011-05-13T04:01:01Z <p>Another possible connection is the following result of Gauss:</p> <p>$$\sum_{n=0}^\infty \ q^{n(n+1)/2} = \prod_{m=1}^\infty \ \frac{1-q^{2m}}{1-q^{2m-1}}$$</p> <p>(Andrews <em>The Theory of Partitions</em> Corollary 2.10), actually a corollary of the Jacobi Triple Identity that Simon used.</p> <p>One close mock theta function is $$\psi_0(q) = \sum_{n=0}^\infty \ q^{(n+1)(n+2)/2}(-q)_n$$</p> <p>(see Andrews chapter 2 examples 12 and 13).</p> http://mathoverflow.net/questions/64448/interesting-and-accessible-topics-in-graph-theory/64460#64460 Answer by Brian Hopkins for Interesting and Accessible Topics in Graph Theory Brian Hopkins 2011-05-10T04:47:31Z 2011-05-10T04:47:31Z <p>On the application side, you can introduce graph theory as a way to model connected systems: </p> <ul> <li>web pages (familiar, has some nice visualizations, but hard to get your hands on),</li> <li>people a la Stanley Milgram and "six degrees of separation" (important but very "fuzzy"),</li> <li>actors connected by movies (precise via the Internet Movie Database and front-end Oracle of Bacon -- for ideas on using this, see my PRIMUS article "Kevin Bacon and Graph Theory," available through my web page)</li> </ul> http://mathoverflow.net/questions/128931/hamming-codes-from-overlapping-vectors Comment by Brian Hopkins Brian Hopkins 2013-04-28T20:42:36Z 2013-04-28T20:42:36Z Makes me think of the sliding window in symbolic dynamics, &#224; la Lind and Marcus <i>An Introduction to Symbolic Dynamics and Coding</i>, Cambridge 1995. And also that application of Euler paths to recombining fragments of RNA, Tucker &quot;A new applicable proof of the Euler circuit theorem&quot; <i>American Mathematical Monthly</i> 83 (1976) 638-640. http://mathoverflow.net/questions/109856/recovering-a-group-from-its-number-of-symmetric-embeddings Comment by Brian Hopkins Brian Hopkins 2012-10-17T01:16:51Z 2012-10-17T01:16:51Z Noah, I think the sequence for the Klein four group begins 0, 0, 0, 3, 5 and the sequence for $\Bbb{Z}_4$ begins 0, 0, 0, 3, 15. Interesting question, Jon. Reminds me of an algebra prelim question where we were asked to find the smallest $n$ for which various groups embedded into $S_n$. http://mathoverflow.net/questions/63561/fibonacci-compositions-history/88179#88179 Comment by Brian Hopkins Brian Hopkins 2012-02-25T05:23:08Z 2012-02-25T05:23:08Z Thanks for coming back to this, Gerhard. The article you pointed me to is available free online. It does include both topics, but not the case I mentioned. Odd part compositions come up in Example 2, and Fibonacci numbers in Example 3 (which foreshadows what Agarwal called &quot;n-colour compositions&quot; in a 2000 paper!). These interesting results are more involved than the number of compositions with odd parts being counted by Fibonacci numbers, which again makes me think that had to be known before. Of course the article has no references. <a href="http://cms.math.ca/cmb/v4/cmb1961v04.0039-0043.pdf" rel="nofollow">cms.math.ca/cmb/v4/cmb1961v04.0039-0043.pdf</a> http://mathoverflow.net/questions/67351/a-game-on-numbers Comment by Brian Hopkins Brian Hopkins 2011-06-09T18:21:14Z 2011-06-09T18:21:14Z This is a continuous version of the Colonel Blotto combinatorial game; knowing that name may help your literature search. http://mathoverflow.net/questions/64448/interesting-and-accessible-topics-in-graph-theory/64460#64460 Comment by Brian Hopkins Brian Hopkins 2011-05-11T03:01:41Z 2011-05-11T03:01:41Z Nope, no theorems in these initial applications. Their purpose is to engage students early on and give contexts for distance, cliques, diameters, dynamic graphs, etc. I like theorems as well as the next mathematician, but they're not the only possible &quot;nuggets.&quot; http://mathoverflow.net/questions/63561/fibonacci-compositions-history Comment by Brian Hopkins Brian Hopkins 2011-04-30T23:04:37Z 2011-04-30T23:04:37Z Thanks, Kevin. I don't find anything about compositions in Hardy &amp; Wright (I have the fifth edition). All of these restricted compositions are discussed in Heubach &amp; Mansour's 2010 <i>Combinatorics of Compositions and Words</i>, but their history does not go back very far (nor do they claim to trace back to the very first sources).