login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 13
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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

REFERENCES

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

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

S. V. Pemmaraju and S. S. Skiena, The New Combinatorica, 2001.

Frank Ruskey, Set Partitions

FORMULA

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

EXAMPLE

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

MATHEMATICA

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

(* 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 *)

CROSSREFS

Cf. A002872, A080337.

Cf. A125810. - Paul D. Hanna, Jan 19 2009

Sequence in context: A299295 A305752 A034786 * A056156 A112837 A056355

Adjacent sequences:  A080104 A080105 A080106 * A080108 A080109 A080110

KEYWORD

nonn

AUTHOR

Wouter Meeussen, Mar 15 2003

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 19:49 EST 2019. Contains 319206 sequences. (Running on oeis4.)