|
Search: id:A080107
|
|
|
| A080107 |
|
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. |
|
+0
7
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Even-numbered terms a(2k) are conjectured to be A002872: 2,7,31,164,999 ("Sorting numbers"); odd-numbered terms are conjectured to be its binomial transform, A080337.
Both conjecture are true. 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. - D. E. Knuth, Nov 23 2003
|
|
LINKS
|
S. V. Pemmaraju and S. S. Skiena, NewCombinatorica
Frank Ruskey, Set Partitions
|
|
FORMULA
|
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. [From Paul D. Hanna (pauldhanna(AT)juno.com), Jan 19 2009]
|
|
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.
|
|
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}]
|
|
CROSSREFS
|
Cf. A002872, A080337.
Cf. A125810. [From Paul D. Hanna (pauldhanna(AT)juno.com), Jan 19 2009]
Sequence in context: A134565 A100982 A034786 this_sequence A056156 A112837 A056355
Adjacent sequences: A080104 A080105 A080106 this_sequence A080108 A080109 A080110
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Wouter Meeussen (wouter.meeussen(AT)pandora.be), Mar 15 2003
|
|
|
Search completed in 0.002 seconds
|
