A002872 Number of partitions of {1..2n} that are invariant under a permutation consisting of n 2-cycles.

1, 2, 7, 31, 164, 999, 6841, 51790, 428131, 3827967, 36738144, 376118747, 4086419601, 46910207114, 566845074703, 7186474088735, 95318816501420, 1319330556537631, 19013488408858761, 284724852032757686, 4422344774431494155, 71125541977466879231

Offset: 0

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• nonn
• easy
• nice

Comments

Previous name was: Sorting numbers.

a(n) = number of symmetric partitions of the set {-n,...,-1,1,...,n}. A partition of {-n,...,-1,1,...,n} into nonempty subsets X_1,...,X_k is 'symmetric' if for each i, -X_i=X_j for some j. a(n) = S_B(n,1)+...+S_B(n,n) where S_B(n,k) is as in A085483. a(n) is the n-th Bell number of 'type B'. - James East, Aug 18 2003

Column 2 of A162663. - Franklin T. Adams-Watters, Jul 09 2009

a(n) is equal to the sum of all expressions of the form p(1^n)[st(lambda)] for partitions lambda of order less than or equal to n, where p(1^n)[st(lambda)] denotes the coefficient of the irreducible character basis element indexed by the partition lambda in the expansion of the power sum basis element indexed by the partition (1^n). - John M. Campbell, Sep 16 2017

Number of achiral color patterns in a row or loop of length 2n. Two color patterns are equivalent if the colors are permuted. - Robert A. Russell, Apr 24 2018

Stirling transform of A005425 per Knuth reference. - Robert A. Russell, Apr 28 2018

Examples

			For a(2)=7, the row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD.  The loop patterns are AAAA, AAAB, AABB, AABC, ABAB, ABAC, and ABCD. - _Robert A. Russell_, Apr 24 2018
		

References

• D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765). - Robert A. Russell, Apr 28 2018
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..513 (first 101 terms from T. D. Noe)
• Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See pp. 12, 18, 29.
• T. Halverson and M. Reeks, Gelfand Models for Diagram Algebras, arXiv preprint arXiv:1302.6150 [math.RT], 2013.
• Vaclav Kotesovec, Asymptotics for a certain group of exponential generating functions, arXiv:2207.10568 [math.CO], Jul 13 2022.
• Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.
• T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
• J. Pasukonis and S. Ramgoolam, From counting to construction for BPS states in N=4 SYM, arXiv:1010.1683 [hep-th], 2010, (E.2).
• J. Pasukonis and S. Ramgoolam, From counting to construction for BPS states in N=4 SYM, J. High En. Phys. 2011 (2) (2011), (E.2).
• OEIS Wiki, Sorting numbers
• R. Orellana and M. Zabrocki, Symmetric group characters as symmetric functions, arXiv preprint arXiv:1605.06672 [math.CO], 2016-2017.
• J. Quaintance, Letter representations of rectangular m x n x p proper arrays, arXiv:math/0412244 [math.CO], 2004-2006.
• Index entries for sequences related to sorting

Crossrefs

Cf. A002873, A002874, A080107, A085483.

u[n,j] is A162663.

Row sums of A293181.

Column k=2 of A306024.

Cf. A005425.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1, add((1+
      2^(j-1))*binomial(n-1, j-1)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 29 2015

Mathematica

u[0,j_]:=1;u[k_,j_]:=u[k,j]=Sum[Binomial[k-1,i-1]Plus@@(u[k-i,j]#^(i-1)&/@Divisors[j]),{i,k}]; Table[u[n,2],{n,0,12}] (* Wouter Meeussen, Dec 06 2008 *)
mx = 16; p = 2; Range[0, mx]! CoefficientList[ Series[ Exp[ (Exp[p*x] - p - 1)/p + Exp[x]], {x, 0, mx}], x] (* Robert G. Wilson v, Dec 12 2012 *)
Aeven[m_, k_] := Aeven[m, k] = If[m>0, k Aeven[m-1, k] + Aeven[m-1, k-1]
  + Aeven[m-1, k-2], Boole[m==0 && k==0]]
Table[Sum[Aeven[m, k], {k, 0, 2m}], {m, 0, 30}] (* Robert A. Russell, Apr 24 2018 *)
x[n_] := x[n] = If[n<2, n+1, 2x[n-1] + (n-1)x[n-2]]; (* A005425 *)
Table[Sum[StirlingS2[n, k] x[k], {k, 0, n}], {n, 0, 20}] (* Robert A. Russell, Apr 28 2018, from Knuth reference *)
Table[Sum[Binomial[n,k] * 2^k * BellB[k, 1/2] * BellB[n-k], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Jun 29 2022 *)

Formula

E.g.f.: e^( (e^(2x) - 3)/2 + e^x ).

a(n) = A080107(2n) for all n. - Jörgen Backelin, Jan 13 2016

From Robert A. Russell, Apr 24 2018: (Start)

Aeven(n,k) = [n>0]*(k*Aeven(n-1,k)+Aeven(n-1,k-1)+Aeven(n-1,k-2))

+ [n==0]*[k==0]

a(n) = Sum_{k=0..2n} Aeven(n,k). (End)

a(n) = Sum_{k=0..n} Stirling2(n, k)*A005425(k). (from Knuth reference) - Robert A. Russell, Apr 28 2018

a(n) ~ exp(exp(2*r)/2 + exp(r) - 3/2 - n) * (n/r)^(n + 1/2) / sqrt((1 + 2*r)*exp(2*r) + (1 + r)*exp(r)), where r = LambertW(2*n)/2 - 1/(1 + 2/LambertW(2*n) + n^(1/2) * (1 + LambertW(2*n)) * (2/LambertW(2*n))^(3/2)). - Vaclav Kotesovec, Jul 03 2022

a(n) ~ (2*n/LambertW(2*n))^n * exp(n/LambertW(2*n) + (2*n/LambertW(2*n))^(1/2) - n - 7/4) / sqrt(1 + LambertW(2*n)). - Vaclav Kotesovec, Jul 10 2022

Extensions

Edited by Franklin T. Adams-Watters, Jul 09 2009