User richard stanley - MathOverflow

Magic trick based on deep mathematics

2009-12-25T22:07:11Z

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?

Answer by Richard Stanley for Combinatorics of index sets multiplicities in characters of symmetric groups

2013-05-26T22:56:06Z

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

Answer by Richard Stanley for Why are the dinv-statistic and the partition length equidistributed?

2013-05-22T21:28:35Z

This formula appears in Exercise 1.103 of Enumerative Combinatorics, vol. 1, second ed. It was first proved by K. Liu, C. H. F. Yan, and J. Zhou, Sci. China, Ser. A 45 (2002), 420-431. A combinatorial proof was given by G. Warrington, J. Combinatorial Theory Ser. A 116 (2009), 379-403.

Answer by Richard Stanley for Discrete disjoint covering of integer lattices

2013-05-09T14:53:12Z

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<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 & 0 & 0 & 2\\ 0 & 1 & 0 & 3\\ 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 5\end{bmatrix}, \qquad \begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 5\end{bmatrix}. $$

Answer by Richard Stanley for Semi-Standard Young Diagrams and Families

2013-05-07T00:43:32Z

I use standard facts about symmetric functions that can be found, e.g, in Chapter 7 of Enumerative Combinatorics, 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.

Answer by Richard Stanley for Relations involving Stirling numbers of second kind

2013-04-09T01:18:35Z

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.

Answer by Richard Stanley for Counting linear extensions of unlabeled series parallel structures

2013-03-21T16:21:13Z

Normally linear extensions are counted for labelled posets. You are asking about the unlabelled 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.

Answer by Richard Stanley for Characters of p-groups

2013-03-18T00:33:38Z

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

Answer by Richard Stanley for Generalization's of Greene's Theorem for the Robinson-Schensted correspondence

2013-03-16T01:09:55Z

For shifted RSK, see Section 3.5 of the thesis of Luis Guillermo Serrano Herrera at http://deepblue.lib.umich.edu/bitstream/handle/2027.42/77864/lserrano_1.pdf;jsessionid=B5A8F5AD166B6960A30EE5E16394A963?sequence=1.

Answer by Richard Stanley for Invertibility of a certain matrix indexed by the Hamming cube

2013-03-08T02:25:13Z

For a vast generalization, see Exercise 3.96(a) of Enumerative Combinatorics, 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$.

Access to a preprint by D. N. Verma

2013-02-28T02:37:02Z

Some work I am doing is connected with a sequence 1, 3, 40, 1225, 67956, $\dots$ which agrees with http://oeis.org/A012250 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.

Answer by Richard Stanley for Good books on problem solving / math olympiad

2009-12-30T18:50:43Z

For a slightly annotated list of some books on problem-solving, see http://math.mit.edu/~rstan/refs.pdf.

Answer by Richard Stanley for Statistics on Lehmer codes

2013-02-18T02:38:30Z

The papers http://www4.ncsu.edu/~savage/PAPERS/ESofLHPandEPforIS.pdf and http://www4.ncsu.edu/~savage/PAPERS/rational.pdf contain some information about statistics on generalizations of Lehmer codes called $s$-inversion sequences.

Answer by Richard Stanley for What is the probability for sequence of lenght L in subset of [n]

2013-02-16T19:48:34Z

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

Answer by Richard Stanley for Partial order relation on subsets

2013-02-14T21:55:51Z

This order is sometimes denoted $L(k,n-k)$ and has many interesting properties. See for instance Chapter 6 of http://math.mit.edu/~rstan/algcomb.pdf. For the characteristic polynomial of the Hasse diagram of $L(k,n-k)$ (considered as a graph), see Remark 5.6 of http://math.mit.edu/~rstan/papers/vac.pdf.

Answer by Richard Stanley for connected components of a real hyperplane arrangement

2013-01-22T03:48:26Z

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.

Density of values of polynomials in two variables

2010-11-10T02:32:47Z

This question is a reposting of a comment I made on http://mathoverflow.net/questions/9731/polynomial-representing-all-nonnegative-integers. 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)}$.

Answer by Richard Stanley for Elementary applications of linear algebra over finite fields

2013-01-15T00:27:26Z

Possibly the simplest application is Berlekamp's Oddtown theorem. One reference is Section 12.2 of http://math.mit.edu/~rstan/algcomb.pdf.

A question on the Laurent phenomenon

2013-01-05T21:33:25Z

This question is motivated by my answer to 109955. It gives a recurrence relation satisfied by a function $P(n)$ whose terms a priori 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?

Answer by Richard Stanley for Are there any binomial poset which has non-isomorphic interval of the same length?

2012-12-20T02:22:46Z

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}< x _0< x _1< \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 http://front.math.ucdavis.edu/0508.5397.

Combinatorial interpretation of ${i\choose n}$, where $i^2=-1$

2012-12-14T01:43:49Z

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

Answer by Richard Stanley for What is the smallest number of subsets in such a subdivision?

2012-12-14T01:54:15Z

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?

Answer by Richard Stanley for Why do Littlewood-Richardson coefficients describe the cohomology of the Grassmannian?

2012-12-13T03:13:29Z

There is some additional information on page 399 of Enumerative Combinatorics, vol. 2. The first conceptual explanations are due to Horrocks in 1957 and Carrell in 1978. See also pages 278-279 of Fulton's Intersection Theory.

Answer by Richard Stanley for Littlewood-Richardson Coefficients from Kostka coefficients

2012-12-13T02:06:36Z

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.

Answer by Richard Stanley for Pairs of Permutations up to Simultaneous Conjugation

2012-12-10T21:17:42Z

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

Answer by Richard Stanley for Combinatorics: Product Rules.

2012-12-08T18:57:19Z

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

Answer by Richard Stanley for Applications of the Chinese remainder theorem

2009-12-29T17:27:07Z

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

Answer by Richard Stanley for Salié permutations and fair permutations

2012-11-21T01:29:59Z

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.

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

Answer by Richard Stanley for Absolute sum of coefficient of (1-x)^b (1+x)^{(n-b)}

2012-11-22T03:44:03Z

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.

Answer by Richard Stanley for Combinatorial Morse functions and random permutations

2012-11-20T17:10:34Z

The suggestion of Karl Waugh can be fixed. Let us call a permutation nice 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.

A further thought. 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$.

Comment by Richard Stanley

2013-06-08T23:20:19Z

See mathoverflow.net/questions/42344.

Comment by Richard Stanley

2013-06-08T17:32:43Z

For planar graphs, see arxiv.org/abs/0912.0712.

Comment by Richard Stanley

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

Comment by Richard Stanley

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.

Comment by Richard Stanley

2013-05-29T13:24:11Z

A related question is mathoverflow.net/questions/42449.

Comment by Richard Stanley

2013-05-25T00:04:07Z

The work referred to in the question is now available. See Theorem 4.6 and Remark 4.7 at math.mit.edu/~rstan/papers/distinctparts.pdf.

Comment by Richard Stanley

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<1$. The point here is that these nonzero $u_i$'s should form a basis for the lattice $\mathbb{Z}^n$.

Comment by Richard Stanley

2013-05-02T13:15:41Z

See en.wikipedia.org/wiki/Hyphen for information on hyphens. In particular, "the use of the hyphen in English compound nouns and verbs has, in general, been steadily declining."

Comment by Richard Stanley

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

Comment by Richard Stanley

2013-04-24T01:15:54Z

Guoce Xin has some papers that seem relevant. See for instance front.math.ucdavis.edu/0409.5190 and front.math.ucdavis.edu/0504.5425.

Comment by Richard Stanley

2013-04-10T00:21:33Z

Some partial information (with references) can be found in Exercise 5.2 of Enumerative Combinatorics, vol. 2.

Comment by Richard Stanley

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

Comment by Richard Stanley

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 Enumerative Combinatorics, vol. 2.

Comment by Richard Stanley

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.

Comment by Richard Stanley

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.