User william j. keith - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T01:41:58Z http://mathoverflow.net/feeds/user/12878 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/96204/a-simple-looking-problem-in-partitions-that-became-increasingly-complex/96271#96271 Answer by William J. Keith for A simple looking problem in partitions that became increasingly complex William J. Keith 2012-05-07T22:31:33Z 2012-05-07T22:31:33Z <p>This may or may not be useful to you; I didn't get a complete answer from it.</p> <p>If you multiply the original equation by $n!$ on both sides, you get $$n \cdot n! = k_1 n! + k_2 \frac{n!}{2} + \dots + k_n \frac{n!}{n} .$$</p> <p>In the factorial-base expansion $n = a_1 1! + a_2 2! + a_3 3! + \dots$, this is then partitioning $00\dots0n$ into parts $00\dots0001 = (n-1)! = \frac{n!}{n}$ , $00\dots0011 = (n-1)!+(n-2)! = \frac{n!}{n-1}$ , $00\dots0221 = \frac{n!}{n-3}$ , $00\dots6631$ , ... , $00\dots000\frac{n}{2}$ , $00\dots00001 = n!$.</p> <p>The leading digits obey the obvious distribution, starting with $0\dots x1$, then $0\dots x2$, with the $x$ increasing at increasing rates. Now, partition problems don't necessarily behave well under small changes in the allowed parts, but if you can prove some sort of well-behavedness in the vicinity of these summands -- say, just taking the $0\dots x j$ parts -- perhaps poking at the factorial-base expansion will give you some sense of the asymptotics?</p> <p>(Interestingly, the very largest parts converge to a constant form with trailing zeros, but only about log of them have frozen at any $n$.)</p> http://mathoverflow.net/questions/89800/symmetric-distribution-of-maj-over-des-in-pattern-avoidance-classes Symmetric distribution of maj over des in pattern avoidance classes William J. Keith 2012-02-28T21:21:37Z 2012-03-01T02:10:37Z <p>It appears from computation to be the case (and would prove at least one clause of a conjecture advanced by Bruce Sagan and collaborators in a recent preprint) that in some pattern avoidance classes of permutations, the distribution of the major index is symmetric among permutations with a given descent number. For instance, $$\sum_{S_6(1234)} q^{maj(\sigma)}t^{des(\sigma)} = \dots + (10 q^6 + 35 q^7 + 66 q^8 + 80 q^9 + 66 q^{10} + 35 q^{11} + 10 q^{12}) t^3 + \dots.$$</p> <p>As you can see, the coefficient of $t^3$ is a symmetric polynomial.</p> <p>This is not the case for all avoidance classes: for instance, $$\sum_{S_6(2134)} q^{maj(\sigma)}t^{des(\sigma)} = \dots + (4 q^6 + 21 q^7 + 42 q^8 + 61 q^9 + 56 q^{10} + 35 q^{11} + 10 q^{12}) t^3 + \dots.$$</p> <p>Before I start hammering at this, I was wondering if this was known to be the case for any particular avoidance classes, and if so, which. Since I have not even found any papers that seem to deal with the subject, pointers to one you know of would also be gratefully received.</p> http://mathoverflow.net/questions/85927/number-of-integer-combinations-x-1-x-n/85997#85997 Answer by William J. Keith for Number of integer combinations x_1 < ... < x_n ? William J. Keith 2012-01-18T14:31:17Z 2012-01-18T14:31:17Z <p>Robin Pemantle and Herb Wilf give a short recurrence as an answer to this question, and a more compact formula when the sequence $a_n$ is linear, in a freely available paper from the EJC in 2009: vol. 16 (2009), #R60, "Counting Nondecreasing Integer Sequences that Lie Below a Barrier." Link: <a href="http://www.combinatorics.org/Volume_16/PDF/v16i1r60.pdf" rel="nofollow">http://www.combinatorics.org/Volume_16/PDF/v16i1r60.pdf</a> .</p> http://mathoverflow.net/questions/66145/pattern-avoiding-permutations-and-zig-zags/66188#66188 Answer by William J. Keith for Pattern avoiding permutations and zig-zags William J. Keith 2011-05-27T13:22:19Z 2011-05-27T13:22:19Z <p>For involutions, 3412-avoiding involutions are counted by the Motzkin numbers, and there is a nice bijection to Motzkin paths [1].</p> <p>Would you still call the upside-down version of this pattern zig-zag? If so, then 2143-avoiding permutations are called vexillary, and there are several results about them. They are Wilf equivalent (by a bijection) to permutations avoiding 2134, 3421, 1243, and 1234 [2]. The last one tells us that we have a map to the usual pairs of three-column tableaux.</p> <p>2143-avoiding involutions are also counted by the Motzkin numbers. The Barnabei reference will lead you to most of the relevant papers for this collection of patterns that I know of.</p> <p>[1] M. Barnabei et al., Restricted involutions and Motzkin paths, Adv. in Appl. Math. (2010), doi:10.1016/j.aam.2010.05.002</p> <p>[2] J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, 1990</p> http://mathoverflow.net/questions/89800/symmetric-distribution-of-maj-over-des-in-pattern-avoidance-classes/89916#89916 Comment by William J. Keith William J. Keith 2012-03-01T11:09:01Z 2012-03-01T11:09:01Z Thanks Richard. Your argument also proves the property for any other class preserved by reverse-complement, such as $S_n(2143)$, since that's the purpose of (3) and the properties (1) and (2) hold generally. Also seems to hold for a few other singleton classes, but given the discussion so far I think I can attack it with confidence and at least know I'm not reinventing the wheel.