|
%I #72 Aug 31 2023 10:49:08
%S 1,1,2,3,7,12,31,59,164,339,999,2210,6841,16033,51790,127643,428131,
%T 1103372,3827967,10269643,36738144,102225363,376118747,1082190554,
%U 4086419601,12126858113,46910207114,143268057587,566845074703,1778283994284,7186474088735
%N Number of fixed points of permutation of SetPartitions under {1,2,...,n}->{n,n-1,...,1}. Number of symmetric arrangements of non-attacking rooks on upper half of n X n chessboard.
%C Even-numbered terms a(2k) are A002872: 2,7,31,164,999 ("Sorting numbers"); odd-numbered terms are its binomial transform, A080337. The symmetrical set partitions of {-n,...,-1,0,1,...,n} can be classified by the partition containing 0. Thus we get the sum over k of {n choose k} times the number of symmetrical set partitions of 2n-2k elements. - _Don Knuth_, Nov 23 2003
%C Number of partitions of n numbers that are symmetrical and cannot be nested (i.e., include a pattern of the form abab). - _Douglas Boffey_, May 21 2015
%C Number of achiral color patterns in a row or loop of length n. Two color patterns are equivalent if the colors are permuted. - _Robert A. Russell_, Apr 23 2018
%C Also the number of self-complementary set partitions of {1, ..., n}. The complement of a set partition pi of {1, ..., n} is defined as n + 1 - pi (elementwise) on page 3 of Callan. For example, the complement of {{1,5},{2},{3,6},{4}} is {{1,4},{2,6},{3},{5}}. - _Gus Wiseman_, Feb 13 2019
%D D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765).
%H Alois P. Heinz, <a href="/A080107/b080107.txt">Table of n, a(n) for n = 0..1000</a>
%H Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, <a href="https://arxiv.org/abs/2308.14183">Combinatorial Identities for Vacillating Tableaux</a>, arXiv:2308.14183 [math.CO], 2023. See p. 18.
%H David Callan, <a href="https://arxiv.org/abs/math/0508052">On conjugates for set partitions and integer compositions</a>, arXiv:math/0508052 [math.CO], 2005.
%H Juan B. Gil and Luiz E. Lopez, <a href="https://arxiv.org/abs/2203.10589">Enumeration of symmetric arc diagrams</a>, arXiv:2203.10589 [math.CO], 2022.
%H S. V. Pemmaraju and S. S. Skiena, <a href="http://www.cs.uiowa.edu/~sriram/Combinatorica/newFeatures.nb.pdf">The New Combinatorica</a>, 2001.
%H Frank Ruskey, <a href="http://combos.org/part">Set Partitions</a>
%F Knuth gives recurrences and generating functions.
%F a(n) = Sum_{k=0..t(n)} (-1)^k*A125810(n,k) where A125810 is a triangle of coefficients for a q-analog of the Bell numbers and t(n)=A125811(n)-1. - _Paul D. Hanna_, Jan 19 2009
%F From _Robert A. Russell_, Apr 23 2018: (Start)
%F a(n) = Sum_{k=0..n} Ach(n,k) where
%F Ach(n,k) = [n>1]*(k*Ach(n-2,k)+Ach(n-2,k-1)+Ach(n-2,k-2)) + [n<2]*[n==k]*[n>=0].
%F a(n) = 2*A103293(n+1) - A000110(n). (End)
%F a(n) = [n==0 mod 2]*Sum_{k=0..n/2} Stirling2(n/2, k)*A005425(k) + [n==1 mod 2] * Sum_{k=1..(n+1)/2} Stirling2((n+1)/2, k) * A005425(k-1). (from Knuth reference)
%F a(n) = 2*A084708(n) - A084423(n). - _Robert A. Russell_, Apr 27 2018
%e Of the set partitions of 4, the following 7 are invariant under 1->4, 2->3, 3->2, 4->1: {{1,2,3,4}}, {{1,2},{3,4}}, {{1,4},{2,3}}, {{1,3},{2,4}}, {{1},{2,3},{4}}, {{1,4},{2},{3}}, {{1},{2},{3},4}}, so a[4]=7.
%e For a(4)=7, the row patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, and ABCD (same as previous example). The loop patterns are AAAA, AAAB, AABB, AABC, ABAB, ABAC, and ABCD. - _Robert A. Russell_, Apr 23 2018
%e From _Gus Wiseman_, Feb 13 2019: (Start)
%e The a(1) = 1 through a(5) = 12 self-complementary set partitions:
%e {{1}} {{12}} {{123}} {{1234}} {{12345}}
%e {{1}{2}} {{13}{2}} {{12}{34}} {{1245}{3}}
%e {{1}{2}{3}} {{13}{24}} {{135}{24}}
%e {{14}{23}} {{15}{234}}
%e {{1}{23}{4}} {{1}{234}{5}}
%e {{14}{2}{3}} {{12}{3}{45}}
%e {{1}{2}{3}{4}} {{135}{2}{4}}
%e {{14}{25}{3}}
%e {{15}{24}{3}}
%e {{1}{24}{3}{5}}
%e {{15}{2}{3}{4}}
%e {{1}{2}{3}{4}{5}}
%e (End)
%t <<DiscreteMath`NewCombinatorica`; Table[t = SetPartitions[n]; t= t /. Thread[Range[n] -> Range[n, 1, -1]]; t= 1 + RankSetPartition /@ t; t= ToCycles[t]; t= Cases[t, {_Integer}]; Length[t], {n, 7}]
%t (* second program: *)
%t QB[n_, q_] := QB[n, q] = Sum[QB[j, q] QBinomial[n-1, j, q], {j, 0, n-1}] // FunctionExpand // Simplify; QB[0, q_]=1; QB[1, q_]=1; Table[cc = CoefficientList[QB[n, q], q]; cc.Table[(-1)^(k+1), {k, 1, Length[cc]}], {n, 0, 30}] (* _Jean-François Alcover_, Feb 29 2016, after _Paul D. Hanna_ *)
%t (* Ach[n, k] is the number of achiral color patterns for a row or loop of n
%t colors containing exactly k different colors *)
%t Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0],
%t k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]]
%t Table[Sum[Ach[n, k], {k, 0, n}], {n, 0, 30}] (* _Robert A. Russell_, Apr 23 2018 *)
%t x[n_] := x[n] = If[n < 2, n+1, 2x[n-1] + (n-1)x[n-2]]; (* A005425 *)
%t Table[Sum[StirlingS2[Ceiling[n/2], k] x[k-Mod[n, 2]], {k, 0, Ceiling[n/2]}],
%t {n, 0, 30}] (* _Robert A. Russell_, Apr 27 2018, after Knuth reference *)
%Y Cf. A002872, A080337.
%Y Cf. A125810. - _Paul D. Hanna_, Jan 19 2009
%Y Cf. A000126, A000296, A124323, A169985, A324012, A324013, A324014.
%K nonn
%O 0,3
%A _Wouter Meeussen_, Mar 15 2003
%E Offset set to 0 by _Alois P. Heinz_, May 23 2015
|
