User richard stanley - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T02:42:00Z http://mathoverflow.net/feeds/user/2807 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/9754/magic-trick-based-on-deep-mathematics Magic trick based on deep mathematics Richard Stanley 2009-12-25T22:07:11Z 2013-06-10T22:54:47Z <p>I am interested in magic tricks whose explanation requires deep mathematics. The trick should be one that would actually appeal to a layman. An example is the following: the magician asks Alice to choose two integers between 1 and 50 and add them. Then add the largest two of the three integers at hand. Then add the largest two again. Repeat this around ten times. Alice tells the magician her final number $n$. The magician then tells Alice the next number. This is done by computing $(1.61803398\cdots) n$ and rounding to the nearest integer. The explanation is beyond the comprehension of a random mathematical layman, but for a mathematician it is not very deep. Can anyone do better?</p> http://mathoverflow.net/questions/131928/combinatorics-of-index-sets-multiplicities-in-characters-of-symmetric-groups/131959#131959 Answer by Richard Stanley for Combinatorics of index sets multiplicities in characters of symmetric groups Richard Stanley 2013-05-26T22:56:06Z 2013-05-26T22:56:06Z <p>It can't be true in general that $m_{\mu,I}$ is always 0 or 1. That is because $K_{\mu,1^n}=f^\mu$, the number of standard Young tableaux of shape $\mu$. The maximum value of $f^\mu$ for $\mu\vdash n$ is approximately $\sqrt{n!}$, which is much bigger than $2^n$, the number of sets $I\subseteq\lbrace 1,\dots,n\rbrace$. In fact, this reasoning shows that for fixed $n$, we have $\log\max m_{\mu,I} =\frac 12 n\log n +O(n)$. </p> http://mathoverflow.net/questions/131484/why-are-the-dinv-statistic-and-the-partition-length-equidistributed/131516#131516 Answer by Richard Stanley for Why are the dinv-statistic and the partition length equidistributed? Richard Stanley 2013-05-22T21:28:35Z 2013-05-22T21:28:35Z <p>This formula appears in Exercise 1.103 of <em>Enumerative Combinatorics</em>, vol. 1, second ed. It was first proved by K. Liu, C. H. F. Yan, and J. Zhou, <em>Sci. China, Ser. A</em> <strong>45</strong> (2002), 420-431. A combinatorial proof was given by G. Warrington, <em>J. Combinatorial Theory Ser. A</em> <strong>116</strong> (2009), 379-403.</p> http://mathoverflow.net/questions/129983/discrete-disjoint-covering-of-integer-lattices/130175#130175 Answer by Richard Stanley for Discrete disjoint covering of integer lattices Richard Stanley 2013-05-09T14:53:12Z 2013-05-09T14:53:12Z <p>For fixed dimension $n$ there is an algorithm to find all such lattice tilings. Namely, let $S_n$ be the set of all $n\times n$ matrices $A$ of determinant $n+1$ that are in Hermite normal form over $\mathbb{Z}$. If the columns of $A$ are $v_1,\dots,v_n$, then there are $n$ nonzero integer column vectors $u_1,\dots,u_n$ for which there exist $0\leq a_i&lt;1$ satisfying $\sum a_i v_i=u_i$. If the determinant of the matrix $M$ with columns $u_i$ is $\pm 1$, then the translates by the lattice generated by $v_1,\dots,v_n$ of the origin and the vectors $u_i$ gives a tiling of $\mathbb{Z}^n$. By a unimodular integral change of basis we can convert the $u_i$'s to the unit coordinate vectors. This construction gives all the desired lattice tilings, and is easy to implement algorithmically. For $n=4$ there are exactly two Hermite normal forms such that $\det M=\pm 1$, namely, $$\begin{bmatrix} 1 &amp; 0 &amp; 0 &amp; 2\\ 0 &amp; 1 &amp; 0 &amp; 3\\ 0 &amp; 0 &amp; 1 &amp; 4\\ 0 &amp; 0 &amp; 0 &amp; 5\end{bmatrix}, \qquad \begin{bmatrix} 1 &amp; 0 &amp; 0 &amp; 1\\ 0 &amp; 1 &amp; 0 &amp; 0\\ 0 &amp; 0 &amp; 1 &amp; 1\\ 0 &amp; 0 &amp; 0 &amp; 5\end{bmatrix}.$$</p> http://mathoverflow.net/questions/129854/semi-standard-young-diagrams-and-families/129913#129913 Answer by Richard Stanley for Semi-Standard Young Diagrams and Families Richard Stanley 2013-05-07T00:43:32Z 2013-05-07T00:43:32Z <p>I use standard facts about symmetric functions that can be found, e.g, in Chapter 7 of <em>Enumerative Combinatorics</em>, vol. 2. Let $s_\lambda$ denote a Schur function and $p_1=s_1=x_1+x_2+\cdots$. Then $\frac{\partial s_\lambda}{\partial p_1}=\sum_\mu s_\mu$, where the $\mu$'s are obtained by removing a single box from $\lambda$. Moreover, the coefficient of $q^n$ in $s_\lambda(q,q^2,q^3,\dots)$ is equal to the number of SSYT with entries summing to $n$. Thus if we let $c_n$ be the coefficient of $q^n$ in the symmetric function $f$ defined by $$f+\frac{\partial}{\partial p_1}f = \sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots),$$ and if $c_n=\sum a_{\mu,n}s_\mu$, then we need $a_{\mu,n}$ copies of the shape $\mu$ in a set of fathers generating all SSYT with entries summing to $n$. Hence we need to show that $a_{\mu,n}\geq 0$. Now $$\sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots) = \exp \sum_{n\geq 1} \frac{q^n}{1-q^n}p_n.$$ This leads to a simple linear first-order differential equation with solution $$f = (1-q) \sum_\lambda s_\lambda\cdot s_\lambda(q,q^2,q^3,\dots).$$ If $h_u$ denotes the hook length of the square $u$ of $\lambda$, then $$s_\lambda(q,q^2,q^3,\dots) = \frac{q^{b(\lambda)}}{\prod_{u\in \lambda} (1-q^{h_u})},$$ where $b_\lambda=\sum i\lambda_i$. Since there is always a hook length equal to one, the power series $(1-q)s_\lambda(q,q^2,q^3,\dots)$ will be a product of factors of the form $1/(1-q^h)$, $h\geq 1$, so will have nonnegative coefficients as desired. Thus we have not just an existence proof, but a precise generating function for the number of fathers of each shape.</p> http://mathoverflow.net/questions/126900/relations-involving-stirling-numbers-of-second-kind/126924#126924 Answer by Richard Stanley for Relations involving Stirling numbers of second kind Richard Stanley 2013-04-09T01:18:35Z 2013-04-09T01:18:35Z <p>Let $f_n$ denote your expression. Using the well-known formula $\sum_n S_k^n\frac{t^n}{n!} =\frac{1}{k!}(e^t-1)^k$, we get the generating function $$\sum_{n\geq 0}f_n\frac{t^n}{n!} = (1-x(e^t-1))^{-\alpha}.$$ This generating function suggests that there will be no simpler expression for $f_n$ than its definition.</p> http://mathoverflow.net/questions/125171/counting-linear-extensions-of-unlabeled-series-parallel-structures/125185#125185 Answer by Richard Stanley for Counting linear extensions of unlabeled series parallel structures Richard Stanley 2013-03-21T16:21:13Z 2013-03-21T16:21:13Z <p>Normally linear extensions are counted for <em>labelled</em> posets. You are asking about the <em>unlabelled</em> case. Simply take the number of labelled linear extensions and divide by the order of the automorphism group $G$ of the poset, since in the action of $G$ on labelled linear extensions all orbits have size $|G|$. It is easy to compute $|G|$ as a product of factorials arising from parallel connections of isomorphic posets. </p> http://mathoverflow.net/questions/124821/characters-of-p-groups/124829#124829 Answer by Richard Stanley for Characters of p-groups Richard Stanley 2013-03-18T00:33:38Z 2013-03-18T00:33:38Z <p>Here is a more elementary argument than Geoff's. The number of linear characters of $P$ divides the order of $P$ and is hence a power $p^r$ of $p$. All the other characters have degrees $d_i$ of the form $p^{a_i}$. Hence $$p^n = p^r +\sum_i p^{2a_i}.$$ I claim that if $p^n$ is written as a sum of powers of $p$, then the number $N$ of summands satisfies $N\equiv 1$ (mod $p-1$), and the proof follows. One way to prove the claim is to consider the smallest summand $p^k$. Considering the sum mod $p^k$ shows that the number $N_k$ of summands equal to $p^k$ is a multiple of $p$. Hence we can replace them with $N_k/p$ summands equal to $p^{k+1}$ without affecting the number of summands mod $p-1$. Now continue this argument until reaching $p^n$.</p> http://mathoverflow.net/questions/124633/generalizations-of-greenes-theorem-for-the-robinson-schensted-correspondence/124664#124664 Answer by Richard Stanley for Generalization's of Greene's Theorem for the Robinson-Schensted correspondence Richard Stanley 2013-03-16T01:09:55Z 2013-03-16T01:09:55Z <p>For shifted RSK, see Section 3.5 of the thesis of Luis Guillermo Serrano Herrera at <a href="http://deepblue.lib.umich.edu/bitstream/handle/2027.42/77864/lserrano_1.pdf;jsessionid=B5A8F5AD166B6960A30EE5E16394A963?sequence=1" rel="nofollow">http://deepblue.lib.umich.edu/bitstream/handle/2027.42/77864/lserrano_1.pdf;jsessionid=B5A8F5AD166B6960A30EE5E16394A963?sequence=1</a>.</p> http://mathoverflow.net/questions/123681/invertibility-of-a-certain-matrix-indexed-by-the-hamming-cube/123934#123934 Answer by Richard Stanley for Invertibility of a certain matrix indexed by the Hamming cube Richard Stanley 2013-03-08T02:25:13Z 2013-03-08T02:25:13Z <p>For a vast generalization, see Exercise 3.96(a) of <em>Enumerative Combinatorics</em>, vol. 1, second ed. To get the posted problem, take $L$ to be the boolean algebra of all subsets of $F$ (ordered by inclusion), and set $F(u,s)=1$ if $u\neq\emptyset$ or $s=\emptyset$, and otherwise $F(u,s)=0$. (Note that I am using $F$ in two different ways: one is Yemen's use, and the other is the use in EC1.) Then in the row of the matrix $F(s\wedge t,s)$ indexed by $\emptyset$, every entry is 0 except in the column indexed by $\emptyset$. Hence the determinant remains the same if we remove the row and column and indexed by $\emptyset$, but this gives the matrix $A$. </p> http://mathoverflow.net/questions/123179/access-to-a-preprint-by-d-n-verma Access to a preprint by D. N. Verma Richard Stanley 2013-02-28T02:37:02Z 2013-03-01T15:14:12Z <p>Some work I am doing is connected with a sequence 1, 3, 40, 1225, 67956, $\dots$ which agrees with <a href="http://oeis.org/A012250" rel="nofollow">http://oeis.org/A012250</a> for all eight terms. The only useful information in OEIS on this sequence is the reference D. N. Verma, Towards Classifying Finite Point-Set Configurations, preprint, 1997. Does anyone know how to obtain this preprint? Verma himself passed away last year. </p> http://mathoverflow.net/questions/10146/good-books-on-problem-solving-math-olympiad/10164#10164 Answer by Richard Stanley for Good books on problem solving / math olympiad Richard Stanley 2009-12-30T18:50:43Z 2013-02-21T02:09:22Z <p>For a slightly annotated list of some books on problem-solving, see <a href="http://math.mit.edu/~rstan/refs.pdf" rel="nofollow">http://math.mit.edu/~rstan/refs.pdf</a>.</p> http://mathoverflow.net/questions/122096/statistics-on-lehmer-codes/122129#122129 Answer by Richard Stanley for Statistics on Lehmer codes Richard Stanley 2013-02-18T02:38:30Z 2013-02-18T02:38:30Z <p>The papers <a href="http://www4.ncsu.edu/~savage/PAPERS/ESofLHPandEPforIS.pdf" rel="nofollow">http://www4.ncsu.edu/~savage/PAPERS/ESofLHPandEPforIS.pdf</a> and <a href="http://www4.ncsu.edu/~savage/PAPERS/rational.pdf" rel="nofollow">http://www4.ncsu.edu/~savage/PAPERS/rational.pdf</a> contain some information about statistics on generalizations of Lehmer codes called <strong>$s$</strong>-<em>inversion sequences</em>.</p> http://mathoverflow.net/questions/121980/what-is-the-probability-for-sequence-of-lenght-l-in-subset-of-n/122012#122012 Answer by Richard Stanley for What is the probability for sequence of lenght L in subset of [n] Richard Stanley 2013-02-16T19:48:34Z 2013-02-16T19:48:34Z <p>Let $f(n,k,L)$ be the number of $k$-element subsets of $\lbrace 1,2,\dots,n\rbrace$ containing no $L+1$ consecutive integers. Then $$\sum_{n,k}f(n,k,L)x^{n+1}y^k = \frac{1-xy}{1-x-xy-x^{L+2}y^{L+1}}.$$</p> http://mathoverflow.net/questions/121804/partial-order-relation-on-subsets/121842#121842 Answer by Richard Stanley for Partial order relation on subsets Richard Stanley 2013-02-14T21:55:51Z 2013-02-14T21:55:51Z <p>This order is sometimes denoted $L(k,n-k)$ and has many interesting properties. See for instance Chapter 6 of <a href="http://math.mit.edu/~rstan/algcomb.pdf" rel="nofollow">http://math.mit.edu/~rstan/algcomb.pdf</a>. For the characteristic polynomial of the Hasse diagram of $L(k,n-k)$ (considered as a graph), see Remark 5.6 of <a href="http://math.mit.edu/~rstan/papers/vac.pdf" rel="nofollow">http://math.mit.edu/~rstan/papers/vac.pdf</a>.</p> http://mathoverflow.net/questions/118960/connected-components-of-a-real-hyperplane-arrangement/119534#119534 Answer by Richard Stanley for connected components of a real hyperplane arrangement Richard Stanley 2013-01-22T03:48:26Z 2013-01-22T03:48:26Z <p>There is a formula for the number of components which unfortunately is pretty useless, namely, $$\sum_{k,r} \frac{(-1)^{n+k+r}}{k!}f(k,n,r),$$ where $f(k,n,r)$ is the number of real $k\times n$ $(0,1)$-matrices of rank $r$ with no zero row and no two rows equal.</p> http://mathoverflow.net/questions/45511/density-of-values-of-polynomials-in-two-variables Density of values of polynomials in two variables Richard Stanley 2010-11-10T02:32:47Z 2013-01-18T20:35:23Z <p>This question is a reposting of a comment I made on <a href="http://mathoverflow.net/questions/9731/polynomial-representing-all-nonnegative-integers" rel="nofollow">http://mathoverflow.net/questions/9731/polynomial-representing-all-nonnegative-integers</a>. Let $f(x,y)\in \mathbb Q[x,y]$ such that $f(\mathbb Z\times \mathbb Z)$ is a subset of $\mathbb N$ (the nonnegative integers). Let $g(n)$ be the number of elements of $f(\mathbb Z\times \mathbb Z)\cap \lbrace 0,1,\dots, n\rbrace$. How fast can $g(n)$ grow? Is it always true that $g(n)=O(n/\sqrt{\log(n)})$? If true this is best possible since if $f(x,y)=x^2+y^2$ then $g(n)\sim cn/\sqrt{\log(n)}$. </p> http://mathoverflow.net/questions/118903/elementary-applications-of-linear-algebra-over-finite-fields/118935#118935 Answer by Richard Stanley for Elementary applications of linear algebra over finite fields Richard Stanley 2013-01-15T00:27:26Z 2013-01-15T00:27:26Z <p>Possibly the simplest application is Berlekamp's Oddtown theorem. One reference is Section 12.2 of <a href="http://math.mit.edu/~rstan/algcomb.pdf" rel="nofollow">http://math.mit.edu/~rstan/algcomb.pdf</a>.</p> http://mathoverflow.net/questions/118157/a-question-on-the-laurent-phenomenon A question on the Laurent phenomenon Richard Stanley 2013-01-05T21:33:25Z 2013-01-08T15:36:30Z <p>This question is motivated by <a href="http://mathoverflow.net/questions/109955/what-is-the-probability-that-a-scissor-became-the-champion/110043#110043" rel="nofollow">my answer</a> to <a href="http://mathoverflow.net/questions/109955/" rel="nofollow">109955</a>. It gives a recurrence relation satisfied by a function $P(n)$ whose terms <em>a priori</em> are rational functions (of three variables) with complicated denominators. However, by introducing further functions $R(n)$ and $S(n)$, we can get a joint recurrence from which it is obvious that $P(n)$ is a Laurent polynomial (the "Laurent phenomenon"). (Actually in 109955 the recurrence for $P(n)$ was derived from the joint recurrence, but this is irrelevant to my question.) I am wondering whether the same technique might apply to other Laurent phenomenon recurrences, or whether it can be proved in certain cases that such an approach cannot work. One of the simplest examples of this behavior is the Somos-4 recurrence $$f(n)f(n+4) = f(n+1)f(n+3)+f(n+2)^2,$$ with generic initial conditions $f(0)=w$, $f(1)=x$, $f(2)=y$, $f(3)=z$. Can the Laurent phenomenon be proved by introducing additional functions as in 109955?</p> http://mathoverflow.net/questions/116714/are-there-any-binomial-poset-which-has-non-isomorphic-interval-of-the-same-length/116836#116836 Answer by Richard Stanley for Are there any binomial poset which has non-isomorphic interval of the same length? Richard Stanley 2012-12-20T02:22:46Z 2012-12-20T02:44:34Z <p>To avoid creating new binomial posets by taking two of them with the same factorial function (i.e., number of maximal chains in an $n$-interval) and identifying their least elements, we should add the extra condition that there exists a maximal chain $\hat{0}&lt; x _0&lt; x _1&lt; \cdots$ such that every element $x$ satisfies $x\leq x_n$ for some $n$. Backelin has constructed an uncountable number of nonisomorphic such binomial posets, all with the same factorial function. Most of these have the property that they contain two nonisomorphic intervals of the same length. See <a href="http://front.math.ucdavis.edu/0508.5397" rel="nofollow">http://front.math.ucdavis.edu/0508.5397</a>.</p> http://mathoverflow.net/questions/116336/combinatorial-interpretation-of-i-choose-n-where-i2-1 Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$ Richard Stanley 2012-12-14T01:43:49Z 2012-12-15T23:41:19Z <p>At MIT all departments have numbers, and math is 18. Last year MIT math majors produced a tee shirt that said ${i\choose 18}$ ("I choose 18") on the front, and on the back $$\frac{34376687+1499084559i}{14485008384}.$$ With the more natural denominator $18!$ this is $$\frac{15194495654000+662595375078000i}{18!}.$$ This suggests the question: for any $n\geq 1$ find a "nice" combinatorial interpretation of the real and imaginary parts of $i(i-1)(i-2)\cdots (i-n+1)=f_n+ig_n$. It is easy to express $f_n$ and $g_n$ as certain alternating sums of Stirling numbers of the first kind, but I don't consider this "nice." The $g_n$'s seem to alternate in sign beginning with $n=5$. The $f_n$'s alternate in sign up to $n=17$ and then seem to alternate in sign beginning with $n=18$. It is curious that $i(i-1)(i-2)(i-3)=-10$, a real number. One could ask the same question with $i$ replaced by any Gaussian integer $a+bi$. One can also ask about the asymptotic rate of growth of $f_n$ and $g_n$. Clearly $f_n^2+g_n^2\sim C\cdot (n-1)!^2$, so one would expect $f_n$ and $g_n$ to be roughly of the size of $(n-1)!$.</p> http://mathoverflow.net/questions/116267/what-is-the-smallest-number-of-subsets-in-such-a-subdivision/116337#116337 Answer by Richard Stanley for What is the smallest number of subsets in such a subdivision? Richard Stanley 2012-12-14T01:54:15Z 2012-12-14T01:54:15Z <p>Consider the general problem of $n$ points (no three on a line). It is known that some $N$ of these points are in convex position if $n=4^N$. Thus for $n$ points we can find $\log_4 n$ points in convex position. After removing them, we can find $\log_4(n-\log_4 n)$ points in convex position, etc. It takes about $n/(\log n)$ steps (does someone know a more accurate estimate?) to remove all the points by this procedure, so we get an upper bound on the number of subsets which is on the order of $n/(\log n)$. Can this be improved?</p> http://mathoverflow.net/questions/14219/why-do-littlewood-richardson-coefficients-describe-the-cohomology-of-the-grassman/116228#116228 Answer by Richard Stanley for Why do Littlewood-Richardson coefficients describe the cohomology of the Grassmannian? Richard Stanley 2012-12-13T03:13:29Z 2012-12-13T03:13:29Z <p>There is some additional information on page 399 of <em>Enumerative Combinatorics</em>, vol. 2. The first conceptual explanations are due to Horrocks in 1957 and Carrell in 1978. See also pages 278-279 of Fulton's <em>Intersection Theory</em>.</p> http://mathoverflow.net/questions/116171/littlewood-richardson-coefficients-from-kostka-coefficients/116224#116224 Answer by Richard Stanley for Littlewood-Richardson Coefficients from Kostka coefficients Richard Stanley 2012-12-13T02:06:36Z 2012-12-13T02:06:36Z <p>I prefer to write $K_{\lambda/\nu,\mu}$ for $K^\nu_{\lambda,\mu}$. Using standard symmetric function notation, we have $$K_{\lambda/\nu,\mu}=\langle s_{\lambda/\nu},h_\mu\rangle = \langle s_\lambda,s_\nu h_\mu\rangle.$$ Let $\rho/\sigma$ be a skew shape which is a disjoint union of shapes $\nu, (\mu_1), (\mu_2), \dots$. Here $(\mu_i)$ is a single row of length $\mu_i$. By "disjoint union," I mean that none of the shapes has a square in the same row or in the same column as a square of another of the shapes. Thus $s_{\rho/\sigma} = s_\nu h_\mu$, so $$K_{\lambda/\nu,\mu}=\langle s_\lambda,s_{\rho/\sigma}\rangle = \langle s_\lambda s_\sigma, s_\rho\rangle,$$ an ordinary Littlewood-Richardson coefficient.</p> http://mathoverflow.net/questions/77663/pairs-of-permutations-up-to-simultaneous-conjugation/116020#116020 Answer by Richard Stanley for Pairs of Permutations up to Simultaneous Conjugation Richard Stanley 2012-12-10T21:17:42Z 2012-12-10T21:17:42Z <p>Another way to say what's in oeis.org/A110143 is the following. Let $\lambda$ be a partition of $n$, denoted $\lambda\vdash n$, and let $z_\lambda$ be the number of permutations in $S_n$ commuting with a fixed permutation $w$ of cycle type $\lambda$, so $z_\lambda=1^{m_1}m_1!2^{m_2}m_2!\cdots$, where $\lambda$ has $m_i$ parts equal to $i$. Thus the size of the conjugacy class containing $w$ is $n!/z_\lambda$. It is then immediate from the Cauchy-Frobenius lemma (aka Burnside's lemma) that the number of classes is $$\frac{1}{n!}\sum_{\lambda\vdash n} \frac{n!}{z_\lambda}z_\lambda^2 = \sum_{\lambda\vdash n} z_\lambda.$$ Similarly the number of $k$-tuples of permutations up to simultaneous conjugation is $\sum_{\lambda\vdash n}z_\lambda^{k-1}$. </p> http://mathoverflow.net/questions/115810/combinatorics-product-rules/115828#115828 Answer by Richard Stanley for Combinatorics: Product Rules. Richard Stanley 2012-12-08T18:57:19Z 2012-12-09T21:17:50Z <p>It seems to me that in either your expression for $L$ or for $L^{n/2}f(X)$, you need to replace $\lambda_j$ with $1/\lambda_j$. (I see this has been corrected, so my previous sentence is irrelevant.) In any event, since $f(X)=(X_1+\cdots+X_n)^n$ it is clear that $C(n)=n!$. </p> http://mathoverflow.net/questions/10014/applications-of-the-chinese-remainder-theorem/10051#10051 Answer by Richard Stanley for Applications of the Chinese remainder theorem Richard Stanley 2009-12-29T17:27:07Z 2012-11-30T02:02:57Z <p>There are some cute exercises based on the Chinese remainder theorem, e.g., (1) there exist an arbitrarily large number of consecutive integers, none of which is squarefree (1955 Putnam Competition), (2) there exist an arbitrarily large number of consecutive integers, none of which is powerful ($n$ is <em>powerful</em> if for every prime $p$ dividing $n$, we have $p^2|n$), (3) there exist an arbitrarily large number of consecutive positive integers, none of which is a sum of two squares, (4) the number of integers $1\cdot 2, 2\cdot 3, \dots, n\cdot (n+1)$ divisible by $n$ is $2^{\omega(n)}$, where $\omega(n)$ is the number of distinct prime divisors of $n$. </p> http://mathoverflow.net/questions/113983/salie-permutations-and-fair-permutations/114007#114007 Answer by Richard Stanley for Salié permutations and fair permutations Richard Stanley 2012-11-21T01:29:59Z 2012-11-28T02:37:50Z <p>Write a fair permutation in cycle form, as follows. First write all cycles of length $>1$ in decreasing order of their smallest element, with the smallest element of each cycle written as the leftmost element of the cycle. Then append all the fixed points in increasing order. An example is $$(3,9,4,6)(1,7,2,10)(5)(8).$$ Now erase the parentheses. We obtain a Salié permutation. Each Salié permutation arises in exactly two ways. If the first fixed point is less than the element preceding it in the representation just described (as is the case for the example above), then we can absorb the first two fixed points into the cycle preceding them (that is, the rightmost cycle). Otherwise, we can turn the last two elements of the rightmost cycle into fixed points. For the example above we get the additional fair permutation $$(3,9,4,6)(1,7,2,10,5,8)$$ yielding the same Sailé permutation.</p> <p><strong>Addendum.</strong> There is a small inaccuracy above. If 1 is a fixed point, then rather than absorbing 1 and the fixed point $j$ following it into the previous cycle, we should create a new cycle $(1,j)$.</p> http://mathoverflow.net/questions/114084/absolute-sum-of-coefficient-of-1-xb-1xn-b/114133#114133 Answer by Richard Stanley for Absolute sum of coefficient of (1-x)^b (1+x)^{(n-b)} Richard Stanley 2012-11-22T03:44:03Z 2012-11-22T03:44:03Z <p>Assume without loss of generality that $b\leq n/2$. Writing $f(x)=(1-x^2)^b(1+x)^{n-2b}$ shows that an upper bound is $2^{n-b}$, but this is very crude.</p> http://mathoverflow.net/questions/86193/combinatorial-morse-functions-and-random-permutations/113965#113965 Answer by Richard Stanley for Combinatorial Morse functions and random permutations Richard Stanley 2012-11-20T17:10:34Z 2012-11-20T21:32:53Z <p>The suggestion of Karl Waugh can be fixed. Let us call a permutation <em>nice</em> if it satisfies the conditions of the problem. Let $a_0 a_1\cdots a_{2n}$ be a permutation of $V_n$. There are six possible orderings of the numbers $a_0, a_1, a_2$, all equally likely. Two of these orderings are incompatible with niceness, so there is a $2/3$ probability of compatibility. Similarly there is a $2/3$ probability, independent from the values of $a_0,a_1,a_2$, that $a_3,a_4,a_5$ are compatible with niceness. Continuing this argument gives an upper bound of $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ on the probability for a permutation of $0,1,\dots,2n$ to be nice.</p> <p><strong>A further thought.</strong> Alternating permutations are nice. The number $E_n$ of alternating permutations of $1,2,\dots,n$ (an Euler number) satisfies $E_n\sim C(2/\pi)^nn!$. If $f(2n+1)$ denotes the number of nice permutations of $V_n$, then this suggests that the limit $$L=\lim_{n\to \infty} \left( \frac{f(2n+1)}{(2n+1)!}\right)^{1/(2n+1)}$$ exists. The observations above show that then $$\frac{2}{\pi}=0.6366\cdots \leq L\leq\left(\frac 23\right)^{1/3}= 0.8735\cdots.$$ It would be interesting to determine this limit. The upper bound can be made arbitrary close to $L$ by looking at blocks of length $k$ (rather than of length three) as $k\to\infty$. Doing it for $k=10$ yields (modulo computational error) an upper bound of $L\leq (405581/10!)^{1/5} = 0.64515\cdots$. </p> http://mathoverflow.net/questions/133190/retrieving-sequences-of-numbers Comment by Richard Stanley Richard Stanley 2013-06-08T23:20:19Z 2013-06-08T23:20:19Z See <a href="http://mathoverflow.net/questions/42344" rel="nofollow">mathoverflow.net/questions/42344</a>. http://mathoverflow.net/questions/133131/maximum-determinant-of-a-reduced-laplacian-matrix Comment by Richard Stanley Richard Stanley 2013-06-08T17:32:43Z 2013-06-08T17:32:43Z For planar graphs, see <a href="http://arxiv.org/abs/0912.0712" rel="nofollow">arxiv.org/abs/0912.0712</a>. http://mathoverflow.net/questions/133131/maximum-determinant-of-a-reduced-laplacian-matrix Comment by Richard Stanley Richard Stanley 2013-06-08T12:59:24Z 2013-06-08T12:59:24Z The determinant is the number of spanning trees of $G$. The maximum number of spanning trees of a simple $n$-vertex graph is $n^{n-2}$, achieved by the complete graph $K_n$. http://mathoverflow.net/questions/116171/littlewood-richardson-coefficients-from-kostka-coefficients/116224#116224 Comment by Richard Stanley Richard Stanley 2013-06-05T19:40:52Z 2013-06-05T19:40:52Z $K_{\lambda-\mu,\nu}$ is simply another notation for $K_{\lambda/\mu,\nu}$. In general $\langle f,h_\mu\rangle$ is the coefficient of $m_\mu$ when $f$ is expanded in the basis of monomial symmetric functions. http://mathoverflow.net/questions/132187/do-there-exist-transcendental-numbers-which-are-not-hypertranscendental Comment by Richard Stanley Richard Stanley 2013-05-29T13:24:11Z 2013-05-29T13:24:11Z A related question is <a href="http://mathoverflow.net/questions/42449" rel="nofollow">mathoverflow.net/questions/42449</a>. http://mathoverflow.net/questions/123179/access-to-a-preprint-by-d-n-verma Comment by Richard Stanley Richard Stanley 2013-05-25T00:04:07Z 2013-05-25T00:04:07Z The work referred to in the question is now available. See Theorem 4.6 and Remark 4.7 at <a href="http://math.mit.edu/~rstan/papers/distinctparts.pdf" rel="nofollow">math.mit.edu/~rstan/papers/distinctparts.pdf</a>. http://mathoverflow.net/questions/129983/discrete-disjoint-covering-of-integer-lattices/130175#130175 Comment by Richard Stanley Richard Stanley 2013-05-09T17:29:48Z 2013-05-09T17:29:48Z For any $n\times n$ integer matrix $M$ with determinant $d\neq 0$ and columns $v_1,\dots,v_n$, there are exactly $|d|-1$ nonzero integer vectors $u_1,\dots,u_{d-1}$ of the form $u_i=\sum a_i v_i$, where $0\leq a_i&lt;1$. The point here is that these nonzero $u_i$'s should form a basis for the lattice $\mathbb{Z}^n$. http://mathoverflow.net/questions/129377/is-it-possible-to-write-quasiprojective-and-quasifinite-without-a Comment by Richard Stanley Richard Stanley 2013-05-02T13:15:41Z 2013-05-02T13:15:41Z See <a href="http://en.wikipedia.org/wiki/Hyphen" rel="nofollow">en.wikipedia.org/wiki/Hyphen</a> for information on hyphens. In particular, &quot;the use of the hyphen in English compound nouns and verbs has, in general, been steadily declining.&quot; http://mathoverflow.net/questions/128738/inequivalence-of-group-representations-preserved-under-tensor-product Comment by Richard Stanley Richard Stanley 2013-04-25T17:48:07Z 2013-04-25T17:48:07Z If $r_1$ and $r_2$ are two ordinary linear representations of the same degree of a finite group $G$ and $R$ is the regular representation, then $r_1\otimes R\cong r_2\otimes R$. http://mathoverflow.net/questions/128529/using-extended-group-rings-for-combinatorial-generating-functions Comment by Richard Stanley Richard Stanley 2013-04-24T01:15:54Z 2013-04-24T01:15:54Z Guoce Xin has some papers that seem relevant. See for instance <a href="http://front.math.ucdavis.edu/0409.5190" rel="nofollow">front.math.ucdavis.edu/0409.5190</a> and <a href="http://front.math.ucdavis.edu/0504.5425" rel="nofollow">front.math.ucdavis.edu/0504.5425</a>. http://mathoverflow.net/questions/126998/criteria-for-ghost-witt-vectors-looking-for-history-and-references Comment by Richard Stanley Richard Stanley 2013-04-10T00:21:33Z 2013-04-10T00:21:33Z Some partial information (with references) can be found in Exercise 5.2 of <i>Enumerative Combinatorics</i>, vol. 2. http://mathoverflow.net/questions/123179/access-to-a-preprint-by-d-n-verma/123215#123215 Comment by Richard Stanley Richard Stanley 2013-04-05T17:45:22Z 2013-04-05T17:45:22Z The above formula can be simplified to $$\frac 12\sum_{j=0}^{m-1}(m-j)^{n-3}(-1)^{j+1}\binom nj.$$ http://mathoverflow.net/questions/125606/other-variant-of-schur-polynomials-functions Comment by Richard Stanley Richard Stanley 2013-03-27T01:30:45Z 2013-03-27T01:30:45Z Ignoring your list of properties, there is a list of some variants of Schur functions (with references) in the Notes to Chapter 7 of my book <i>Enumerative Combinatorics</i>, vol. 2. http://mathoverflow.net/questions/125182/counting-seating-arrangements-at-a-circular-table Comment by Richard Stanley Richard Stanley 2013-03-21T17:33:11Z 2013-03-21T17:33:11Z Do the members of a team sit together with no spaces between them? In your example, since the boys are identical it seems to me that there is only one way of seating two teams of two and one way of seating a team of three and a team of one, so two ways in all. http://mathoverflow.net/questions/124821/characters-of-p-groups/124829#124829 Comment by Richard Stanley Richard Stanley 2013-03-19T13:00:43Z 2013-03-19T13:00:43Z In fact, if $M$ is the number of nonlinear irreducible characters, then $M\equiv 0$ (mod $p^2-1$) if $n\equiv r$ (mod 2); $M\equiv p-1$ (mod $p^2-1$) if $n$ is odd and $r$ is even; and $M\equiv -p+1$ (mod $p^2-1$) if $n$ is even and $r$ is odd.