A324012 -id:A324012 - cp's OEIS frontend

A080107 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.

1, 1, 2, 3, 7, 12, 31, 59, 164, 339, 999, 2210, 6841, 16033, 51790, 127643, 428131, 1103372, 3827967, 10269643, 36738144, 102225363, 376118747, 1082190554, 4086419601, 12126858113, 46910207114, 143268057587, 566845074703, 1778283994284, 7186474088735

Offset: 0

Wouter Meeussen, Mar 15 2003

nonn

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
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
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
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

			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.
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
From _Gus Wiseman_, Feb 13 2019: (Start)
The a(1) = 1 through a(5) = 12 self-complementary set partitions:
  {{1}}  {{12}}    {{123}}      {{1234}}        {{12345}}
         {{1}{2}}  {{13}{2}}    {{12}{34}}      {{1245}{3}}
                   {{1}{2}{3}}  {{13}{24}}      {{135}{24}}
                                {{14}{23}}      {{15}{234}}
                                {{1}{23}{4}}    {{1}{234}{5}}
                                {{14}{2}{3}}    {{12}{3}{45}}
                                {{1}{2}{3}{4}}  {{135}{2}{4}}
                                                {{14}{25}{3}}
                                                {{15}{24}{3}}
                                                {{1}{24}{3}{5}}
                                                {{15}{2}{3}{4}}
                                                {{1}{2}{3}{4}{5}}
(End)

D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.5 (p. 765).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Zhanar Berikkyzy, Pamela E. Harris, Anna Pun, Catherine Yan, and Chenchen Zhao, Combinatorial Identities for Vacillating Tableaux, arXiv:2308.14183 [math.CO], 2023. See p. 18.
David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.
Juan B. Gil and Luiz E. Lopez, Enumeration of symmetric arc diagrams, arXiv:2203.10589 [math.CO], 2022.
S. V. Pemmaraju and S. S. Skiena, The New Combinatorica, 2001.
Frank Ruskey, Set Partitions

Cf. A002872, A080337.
Cf. A125810. - Paul D. Hanna, Jan 19 2009
Cf. A000126, A000296, A124323, A169985, A324012, A324013, A324014.

< Range[n, 1, -1]]; t= 1 + RankSetPartition /@ t; t= ToCycles[t]; t= Cases[t, {_Integer}]; Length[t], {n, 7}]
(* second program: *)
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 *)
(* Ach[n, k] is the number of achiral color patterns for a row or loop of n
  colors containing exactly k different colors *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0],
  k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]]
Table[Sum[Ach[n, k], {k, 0, n}], {n, 0, 30}] (* Robert A. Russell, Apr 23 2018 *)
x[n_] := x[n] = If[n < 2, n+1, 2x[n-1] + (n-1)x[n-2]]; (* A005425 *)
Table[Sum[StirlingS2[Ceiling[n/2], k] x[k-Mod[n, 2]], {k, 0, Ceiling[n/2]}],
  {n, 0, 30}] (* Robert A. Russell, Apr 27 2018, after Knuth reference *)

Knuth gives recurrences and generating functions.
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
From Robert A. Russell, Apr 23 2018: (Start)
a(n) = Sum_{k=0..n} Ach(n,k) where
  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].
a(n) = 2*A103293(n+1) - A000110(n). (End)
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)
a(n) = 2*A084708(n) - A084423(n). - Robert A. Russell, Apr 27 2018

Offset set to 0 by Alois P. Heinz, May 23 2015

A324011 Number of set partitions of {1, ..., n} with no singletons or cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 5, 14, 66, 307, 1554, 8415, 48530, 296582, 1913561, 12988776, 92467629, 688528288, 5349409512, 43270425827, 363680219762, 3170394634443, 28619600156344, 267129951788160, 2574517930001445, 25587989366964056, 261961602231869825

Offset: 0

Gus Wiseman, Feb 12 2019

nonn

These set partitions are fixed points under Callan's bijection phi on set partitions.

			The a(4) = 1, a(6) = 5, and a(7) = 14 set partitions:
  {{13}{24}}  {{135}{246}}    {{13}{246}{57}}
              {{13}{25}{46}}  {{13}{257}{46}}
              {{14}{25}{36}}  {{135}{26}{47}}
              {{14}{26}{35}}  {{135}{27}{46}}
              {{15}{24}{36}}  {{136}{24}{57}}
                              {{136}{25}{47}}
                              {{14}{257}{36}}
                              {{14}{26}{357}}
                              {{146}{25}{37}}
                              {{146}{27}{35}}
                              {{15}{246}{37}}
                              {{15}{247}{36}}
                              {{16}{24}{357}}
                              {{16}{247}{35}}

David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Cf. A000110, A000126, A000296 (singletons allowed, or adjacencies allowed), A001610, A124323, A169985, A261139, A324012, A324014, A324015.

Table[Select[sps[Range[n]],And[Count[#,{_}]==0,Total[If[First[#]==1&&Last[#]==n,1,0]+Count[Subtract@@@Partition[#,2,1],-1]&/@#]==0]&]//Length,{n,0,10}]

a(11)-a(26) from Alois P. Heinz, Feb 12 2019

A306417 Number of self-conjugate set partitions of {1, ..., n}.

Original entry on oeis.org

1, 1, 0, 1, 1, 2, 7, 7, 46, 39, 321

Offset: 0

Gus Wiseman, Feb 14 2019

This sequence counts set partitions fixed under Callan's conjugation operation.

			The  a(3) = 1 through a(7) = 7 self-conjugate set partitions:
  {{12}{3}}  {{13}{24}}  {{123}{4}{5}}  {{135}{246}}    {{13}{246}{57}}
                         {{13}{2}{45}}  {{124}{35}{6}}  {{15}{246}{37}}
                                        {{13}{25}{46}}  {{1234}{5}{6}{7}}
                                        {{14}{2}{356}}  {{124}{3}{56}{7}}
                                        {{14}{236}{5}}  {{134}{2}{5}{67}}
                                        {{14}{25}{36}}  {{14}{2}{3}{567}}
                                        {{145}{26}{3}}  {{14}{23}{57}{6}}

David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Cf. A000110, A000126, A000296, A001610, A032032, A052841, A080107, A169985, A306416, A324011, A324012.

A324014 Number of self-complementary set partitions of {1, ..., n} with no cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 9, 16, 43, 89, 250, 571, 1639

Offset: 0

Gus Wiseman, Feb 12 2019

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}}.

			The  a(3) = 1 through a(6) = 9 self-complementary set partitions with no cyclical adjacencies:
  {{1}{2}{3}}  {{13}{24}}      {{14}{25}{3}}      {{135}{246}}
               {{1}{2}{3}{4}}  {{1}{24}{3}{5}}    {{13}{25}{46}}
                               {{1}{2}{3}{4}{5}}  {{14}{25}{36}}
                                                  {{1}{24}{35}{6}}
                                                  {{13}{2}{46}{5}}
                                                  {{14}{2}{36}{5}}
                                                  {{15}{26}{3}{4}}
                                                  {{1}{25}{3}{4}{6}}
                                                  {{1}{2}{3}{4}{5}{6}}

David Callan, On conjugates for set partitions and integer compositions [math.CO].

Cf. A000110, A000296, A001610, A080107 (self-complementary), A169985, A324012 (self-conjugate), A324015.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
cmp[stn_]:=Union[Sort[Max@@Join@@stn+1-#]&/@stn];
Table[Select[sps[Range[n]],And[cmp[#]==Sort[#],Total[If[First[#]==1&&Last[#]==n,1,0]+Count[Subtract@@@Partition[#,2,1],-1]&/@#]==0]&]//Length,{n,0,10}]

A324013 Number of self-complementary set partitions of {1, ..., n} with no singletons.

Original entry on oeis.org

1, 0, 1, 1, 4, 3, 15, 16, 75, 89, 428, 571, 2781, 4060, 20093, 31697, 159340, 268791, 1372163, 2455804, 12725447, 24012697, 126238060, 249880687, 1332071241, 2754348360, 14881206473, 32029000641, 175297058228, 391548016475, 2169832010759

Offset: 0

Gus Wiseman, Feb 12 2019

nonn

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}}.

			The  a(3) = 1 through a(6) = 15 self-complementary set partitions with no singletons:
  {{123}}  {{1234}}    {{12345}}    {{123456}}
           {{12}{34}}  {{135}{24}}  {{123}{456}}
           {{13}{24}}  {{15}{234}}  {{124}{356}}
           {{14}{23}}               {{1256}{34}}
                                    {{1346}{25}}
                                    {{135}{246}}
                                    {{145}{236}}
                                    {{16}{2345}}
                                    {{12}{34}{56}}
                                    {{13}{25}{46}}
                                    {{14}{25}{36}}
                                    {{15}{26}{34}}
                                    {{16}{23}{45}}
                                    {{16}{24}{35}}
                                    {{16}{25}{34}}

Andrew Howroyd, Table of n, a(n) for n = 0..500
David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Cf. A000110, A000296, A080107 (self-complementary), A086365, A124323, A324012 (self-conjugate).

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
cmp[stn_]:=Union[Sort[Max@@Join@@stn+1-#]&/@stn];
Table[Select[sps[Range[n]],And[cmp[#]==Sort[#],Count[#,{_}]==0]&]//Length,{n,0,10}]

seq(n)={my(x=x+O(x*x^(n\2)), p=exp((exp(2*x)-3)/2-x+exp(x)), q=(exp(x)-1)*p); vector(n+1, n, my(c=(n-1)\2); c!*polcoef(if(n%2, p, q), c))} \\ Andrew Howroyd, Feb 16 2022

From Andrew Howroyd, Feb 16 2022: (Start)
a(2*n) = A086365(n-1) for n > 0.
a(2*n) = n!*[x^n] exp((exp(2*x) - 3)/2 - x + exp(x));
a(2*n+1) = n!*[x^n] (exp(x) - 1)*exp((exp(2*x) - 3)/2 - x + exp(x)).
(End)

Terms a(13) and beyond from Andrew Howroyd, Feb 16 2022

A306416 Number of ordered set partitions of {1, ..., n} with no singletons or cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Original entry on oeis.org

1, 0, 0, 0, 2, 0, 26, 84, 950, 6000, 62522, 556116, 6259598, 69319848, 874356338, 11384093196, 161462123894, 2397736692144, 37994808171962, 631767062124564, 11088109048500158, 203828700127054008, 3928762035148317314, 79079452776283889820, 1661265965479375937030, 36332908076071038467520, 826376466514358722894154

Offset: 0

Gus Wiseman, Feb 14 2019

nonn

			The a(4) = 2 ordered set partitions are: {{1,3},{2,4}}, {{2,4},{1,3}}.

David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Cf. A000110, A000126, A000296, A000670, A001610, A032032 (adjacencies allowed), A052841 (singletons allowed), A124323, A169985, A306417, A324011 (orderless case), A324012, A324015.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[Length[stn]!,{stn,Select[sps[Range[n]],And[Count[#,{_}]==0,Total[If[First[#]==1&&Last[#]==n,1,0]+Count[Subtract@@@Partition[#,2,1],-1]&/@#]==0]&]}],{n,0,10}]

a(12)-a(26) from Alois P. Heinz, Feb 14 2019

A306418 Regular triangle read by rows where T(n, k) is the number of set partitions of {1, ..., n} requiring k steps of removing singletons and cyclical adjacency initiators until reaching a fixed point, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 3, 0, 1, 2, 12, 0, 0, 0, 12, 35, 5, 0, 0, 5, 56, 100, 42, 0, 0, 0, 14, 282, 343, 231, 7, 0, 0, 0, 66, 1406, 1476, 1088, 104, 0, 0, 0, 0, 307, 7592, 7383, 4929, 909, 27, 0, 0, 0, 0, 1554, 44227, 40514, 22950, 6240, 470, 20, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Feb 14 2019

See Callan's article for details on this transformation (SeparateIS).

			Triangle begins:
    1
    0    1
    0    2    0
    0    2    3    0
    1    2   12    0    0
    0   12   35    5    0    0
    5   56  100   42    0    0    0
   14  282  343  231    7    0    0    0
   66 1406 1476 1088  104    0    0    0    0
  307 7592 7383 4929  909   27    0    0    0    0

David Callan, On conjugates for set partitions and integer compositions, arXiv:math/0508052 [math.CO], 2005.

Row sums are A000110. First column is A324011.

Cf. A000126, A000296, A001610, A306416, A306417, A324012.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
qbj[stn_]:=With[{ini=Join@@Table[Select[s,If[#==Max@@Max@@@stn,MemberQ[s,First[Union@@stn]],MemberQ[s,(Union@@stn)[[Position[Union@@stn,#][[1,1]]+1]]]]&],{s,stn}],sng=Join@@Select[stn,Length[#]==1&]},DeleteCases[Table[Complement[s,Union[sng,ini]],{s,stn}],{}]];
Table[Length[Select[sps[Range[n]],Length[FixedPointList[qbj,#]]-2==k&]],{n,0,8},{k,0,n}]

cp's OEIS Frontend

A080107 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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A324011 Number of set partitions of {1, ..., n} with no singletons or cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A306417 Number of self-conjugate set partitions of {1, ..., n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A324014 Number of self-complementary set partitions of {1, ..., n} with no cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A324013 Number of self-complementary set partitions of {1, ..., n} with no singletons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A306416 Number of ordered set partitions of {1, ..., n} with no singletons or cyclical adjacencies (successive elements in the same block, where 1 is a successor of n).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A306418 Regular triangle read by rows where T(n, k) is the number of set partitions of {1, ..., n} requiring k steps of removing singletons and cyclical adjacency initiators until reaching a fixed point, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica