OFFSET
0,3
COMMENTS
Commuting permutations: number of ordered pairs (g, h) in Sym(n) such that gh = hg.
Equivalently sum of the order of all normalizers of all cyclic subgroups of Sym(n). - Olivier Gérard, Apr 04 2012
From Gus Wiseman, Jan 16 2019: (Start)
Also the number of Young tableaux with distinct entries from 1 to n, where a Young tableau is an array obtained by replacing the dots in the Ferrers diagram of an integer partition of n with positive integers. For example, the a(3) = 18 tableaux are:
123 213 132 312 231 321
.
12 21 13 31 23 32
3 3 2 2 1 1
.
1 2 1 3 2 3
2 1 3 1 3 2
3 3 2 2 1 1
(End)
REFERENCES
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.12, solution.
LINKS
T. D. Noe, Table of n, a(n) for n = 0..200
M. Holloway, M. Shattuck, Commuting pairs of functions on a finite set, PU.M.A, Volume 24 (2013), Issue No. 1.
M. Holloway, M. Shattuck, Commuting pairs of functions on a finite set, Research Gate, 2015.
R. P. Stanley, Pairs with equal squares, Problem 10654, Amer. Math. Monthly, 107 (April 2000), solution p. 368.
Wikipedia, Young tableau
FORMULA
E.g.f: Sum_{n>=0} x^n/(Product_{k=1..n} 1-x^k) = exp(Sum_{n>=1} (x^n/n)/(1-x^n))). - Joerg Arndt, Jan 29 2011
a(n) = Sum{k=1..n} (((n-1)!/(n-k)!)*sigma(k)*a(n-k)), n > 0, and a(0)=1. See A274760. - Johannes W. Meijer, Jul 28 2016
a(n) ~ sqrt(Pi/6)*exp(sqrt(2/3)*Pi*sqrt(n))*n^n/(2*exp(n)*sqrt(n)). - Ilya Gutkovskiy, Jul 28 2016
MAPLE
seq(count(Permutation(n))*count(Partition(n)), n=1..20); # Zerinvary Lajos, Oct 16 2006
with(combinat): A053529 := proc(n): n! * numbpart(n) end: seq(A053529(n), n=0..20); # Johannes W. Meijer, Jul 28 2016
MATHEMATICA
Table[PartitionsP[n] n!, {n, 0, 20}] (* T. D. Noe, Jun 19 2012 *)
PROG
(PARI) N=66; x='x+O('x^N); Vec(serlaplace(exp(sum(k=1, N, x^k/(1-x^k)/k)))) \\ Joerg Arndt, Apr 16 2010
(PARI) N=66; x='x+O('x^N); Vec(serlaplace(sum(n=0, N, x^n/prod(k=1, n, 1-x^k)))) \\ Joerg Arndt, Jan 29 2011
(PARI) a(n) = n!*numbpart(n); \\ Michel Marcus, Jul 28 2016
(Magma) a:= func< n | NumberOfPartitions(n)*Factorial(n) >; [ a(n) : n in [0..25]]; // Vincenzo Librandi, Jan 17 2019
(Python)
from math import factorial
from sympy import npartitions
def A053529(n): return factorial(n)*npartitions(n) # Chai Wah Wu, Jul 10 2023
CROSSREFS
KEYWORD
nonn,easy,nice
AUTHOR
N. J. A. Sloane, Jan 16 2000
STATUS
approved