login
Number of irreducible representations of the symmetric group S_n that have odd degree.
12

%I #31 Jun 17 2020 17:03:48

%S 1,2,2,4,4,8,8,8,8,16,16,32,32,64,64,16,16,32,32,64,64,128,128,128,

%T 128,256,256,512,512,1024,1024,32,32,64,64,128,128,256,256,256,256,

%U 512,512,1024,1024,2048,2048,512,512,1024,1024,2048,2048,4096,4096,4096,4096

%N Number of irreducible representations of the symmetric group S_n that have odd degree.

%C Ayyer et al. (2016, 2016) obtain this sequence (which they call "odd partitions") as the number of partitions of n such that the dimension of the corresponding irreducible representation of S_n is odd.

%H Eric M. Schmidt, <a href="/A059867/b059867.txt">Table of n, a(n) for n = 1..1000</a>

%H Arvind Ayyer, Amritanshu Prasad, Steven Spallone, <a href="http://arxiv.org/abs/1601.01776">Odd partitions in Young's lattice</a>, arXiv:1601.01776 [math.CO], 2016.

%H Arvind Ayyer, A. Prasad, S. Spallone, <a href="http://arxiv.org/abs/1604.08837">Representations of symmetric groups with non-trivial determinant</a>, arXiv preprint arXiv:1604.08837 [math.RT], 2016. See Eq. (14).

%H I. G. Macdonald, <a href="https://doi.org/10.1112/blms/3.2.189">On the degrees of the irreducible representations of symmetric groups</a>, Bulletin of the London Mathematical Society, 3(2):189-192, 1971.

%H John McKay, <a href="http://dx.doi.org/10.1016/0021-8693(72)90066-X">Irreducible representations of odd degree</a>, Journal of Algebra 20, 1972 pages 416-418.

%H Igor Pak, Greta Panova, <a href="https://doi.org/10.1016/j.laa.2020.05.005">Bounds on Kronecker coefficients via contingency tables</a>, Linear Algebra and its Applications (2020), Vol. 602, 157-178.

%F If n = sum 2^e[i] in binary, then the number of odd degree irreducible complex representations of S_n is 2^sum e[i]. In words: write n in binary and take the product of the powers of 2 that appear.

%F G.f.: prod(k>=0, 1 + 2^k * x^2^k). a(n) = 2^A073642(n). - _Ralf Stephan_, Jun 02 2003

%F a(1)=1, a(2n) = 2^e1(n)*a(n), a(2n+1) = a(2n), where e1(n) = A000120(n). - _Ralf Stephan_, Jun 19 2003

%e a(3) = 2 because S_3 the degrees of the irreducible representations of S_3 are 1,1,2.

%t a[n_] := 2^Total[Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1];

%t Array[a, 60] (* _Jean-François Alcover_, Jul 21 2018 *)

%o (Sage) def A059867(n) : dig = n.digits(2); return prod(2^n for n in range(len(dig)) if dig[n]==1) # _Eric M. Schmidt_, Apr 27 2013

%o (PARI) A059867(n)={my(d=binary(n));prod(k=1,#d,if(d[#d+1-k],2^(k-1),1));} \\ _Joerg Arndt_, Apr 29 2013

%o (PARI) a(n) = {my(b = Vecrev(binary(n))); 2^sum(k=1, #b, (k-1)*b[k]);} \\ _Michel Marcus_, Jan 11 2016

%Y Cf. A000120, A029930; A029931: the bisection of log_2(a(n)); A073642, A089248.

%K nonn,easy

%O 1,2

%A Noam Katz (noamkj(AT)hotmail.com), Feb 28 2001

%E More terms from Larry Reeves (larryr(AT)acm.org), Mar 27 2001