User brian hopkins - MathOverflow

Citation for subset complement result

2013-04-07T18:13:24Z

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.

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.

My question is not how to prove this (it's a nice proof appropriate for a discrete math course), rather the history of this result or at least a citation. For me, this arose in looking at applications of permutations to fair division of indivisible goods.

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.

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.

Answer by Brian Hopkins for What would you want to see at the Museum of Mathematics?

2012-12-01T05:24:34Z

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).

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).

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).

Answer by Brian Hopkins for Explicit formula for the number of compositions with m strictly positive parts bounded by n?

2012-09-02T05:27:03Z

Heubach and Mansour's Combinatorics of Compositions and Words (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.

p85, Exercise 3.12

A composition $\sigma = \sigma_1 \cdots \sigma_m$ of $n$ with $m$ parts is said to be limited if $1 \leq \sigma_i \leq n_i$ for all $i = 1, 2, \ldots, n$. [[I think that should be $1, 2, \ldots m$.]]

(1) Derive a formula for the generating function for the number of limited compositions of $n$.

(2) Using Part (1), obtain a simple formula for the case $n_i = k$ for all $i$.

(3) Prove that the number of limited compositions of $n$ is given by $F_{n+1}$ [[Fibonacci]] when $n_i = 2$ for all $i$.

I wanted more room to follow up on Douglas' comment than a comment would allow.

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.

For maximum part $k = 2$, as in the Heubach & 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 & Quinn's Proofs that Really Count (MAA 2003, Identity 4).

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 http://arXiv.org/abs/math.HO/0505425). For $k = 4$ the total number of limited compositions are given by "tetranacci" numbers (OEIS http://oeis.org/A000078) 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:

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]

Answer by Brian Hopkins for Hamiltonian paths where the vertices are integer partitions

2012-07-18T05:30:26Z

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).

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 http://www-rp.lip6.fr/~latapy/Publis/tcs04a.pdf

Fibonacci, compositions, history

2011-04-30T21:57:16Z

There are three basic families of restricted compositions (ordered partitions) that are enumerated by the Fibonacci numbers (with offsets):

a) compositions with parts from {1,2} (e.g., 2+2 = 2+1+1 = 1+2+1 = 1+1+2 = 1+1+1+1)

b) compositions that do not have 1 as a part (e.g., 6 = 4+2 = 3+3 = 2+4 = 2+2+2)

c) compositions that only have odd parts (e.g., 5 = 3+1+1 = 1+3+1 = 1+1+3 = 1+1+1+1+1)

The connection between (a) & the Fibonacci numbers traces back to the analysis of Vedic poetry in the first millennium C.E., at least (Singh, Hist. Math. 12, 1985).

Cayley made the connection to (b) in 1876 (Messenger of Mathematics).

Who first established the connection with (c), odd-part compositions? It was known by 1969 (Hoggatt & Lind, Fib. Quart.), but I suspect it was done before that. Thanks for any assistance, especially with citations.

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.'').

Answer by Brian Hopkins for Does this type of partition have a name?

2011-11-13T01:30:49Z

These are counted in OEIS A001970 where they are called "partitions of partitions" along with some other interpretations. As Simon noted, they do differ from the more-studied plane partitions.

Answer by Brian Hopkins for Alternative Undergraduate Analysis Texts

2011-07-08T02:40:31Z

A very alternative approach is Carol Schumacher's Closer and Closer: Introducing Real Analysis which uses inquiry-based learning / the Moore method. (http://www.jblearning.com/catalog/9780763735937/)

Answer by Brian Hopkins for Identifying the generating function $ G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}. $

2011-05-13T04:01:01Z

Another possible connection is the following result of Gauss:

$$ \sum_{n=0}^\infty \ q^{n(n+1)/2} = \prod_{m=1}^\infty \ \frac{1-q^{2m}}{1-q^{2m-1}} $$

(Andrews The Theory of Partitions Corollary 2.10), actually a corollary of the Jacobi Triple Identity that Simon used.

One close mock theta function is $$\psi_0(q) = \sum_{n=0}^\infty \ q^{(n+1)(n+2)/2}(-q)_n$$

(see Andrews chapter 2 examples 12 and 13).

Answer by Brian Hopkins for Interesting and Accessible Topics in Graph Theory

2011-05-10T04:47:31Z

On the application side, you can introduce graph theory as a way to model connected systems:

web pages (familiar, has some nice visualizations, but hard to get your hands on),
people a la Stanley Milgram and "six degrees of separation" (important but very "fuzzy"),
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)

Comment by Brian Hopkins

2013-04-28T20:42:36Z

Makes me think of the sliding window in symbolic dynamics, à la Lind and Marcus An Introduction to Symbolic Dynamics and Coding, Cambridge 1995. And also that application of Euler paths to recombining fragments of RNA, Tucker "A new applicable proof of the Euler circuit theorem" American Mathematical Monthly 83 (1976) 638-640.

Comment by Brian Hopkins

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$.

Comment by Brian Hopkins

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 "n-colour compositions" 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. cms.math.ca/cmb/v4/cmb1961v04.0039-0043.pdf

Comment by Brian Hopkins

2011-06-09T18:21:14Z

This is a continuous version of the Colonel Blotto combinatorial game; knowing that name may help your literature search.

Comment by Brian Hopkins

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 "nuggets."

Comment by Brian Hopkins

2011-04-30T23:04:37Z

Thanks, Kevin. I don't find anything about compositions in Hardy & Wright (I have the fifth edition). All of these restricted compositions are discussed in Heubach & Mansour's 2010 Combinatorics of Compositions and Words, but their history does not go back very far (nor do they claim to trace back to the very first sources).