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

1, 2, 2, 4, 4, 8, 8, 8, 8, 16, 16, 32, 32, 64, 64, 16, 16, 32, 32, 64, 64, 128, 128, 128, 128, 256, 256, 512, 512, 1024, 1024, 32, 32, 64, 64, 128, 128, 256, 256, 256, 256, 512, 512, 1024, 1024, 2048, 2048, 512, 512, 1024, 1024, 2048, 2048, 4096, 4096, 4096, 4096

Offset: 1

Author

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

Keywords

• nonn
• easy

Comments

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.

Examples

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

Links

• Eric M. Schmidt, Table of n, a(n) for n = 1..1000
• Arvind Ayyer, Amritanshu Prasad, Steven Spallone, Odd partitions in Young's lattice, arXiv:1601.01776 [math.CO], 2016.
• Arvind Ayyer, A. Prasad, S. Spallone, Representations of symmetric groups with non-trivial determinant, arXiv preprint arXiv:1604.08837 [math.RT], 2016. See Eq. (14).
• I. G. Macdonald, On the degrees of the irreducible representations of symmetric groups, Bulletin of the London Mathematical Society, 3(2):189-192, 1971.
• John McKay, Irreducible representations of odd degree, Journal of Algebra 20, 1972 pages 416-418.
• Igor Pak, Greta Panova, Bounds on Kronecker coefficients via contingency tables, Linear Algebra and its Applications (2020), Vol. 602, 157-178.

Crossrefs

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

Programs

Mathematica

a[n_] := 2^Total[Flatten[Position[Reverse[IntegerDigits[n, 2]], 1]] - 1];
Array[a, 60] (* Jean-François Alcover, Jul 21 2018 *)

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

PARI

a(n) = {my(b = Vecrev(binary(n))); 2^sum(k=1, #b, (k-1)*b[k]);} \\ Michel Marcus, Jan 11 2016

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

Formula

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.

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

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

Extensions

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