|
|
A002846
|
|
Number of ways of transforming a set of n indistinguishable objects into n singletons via a sequence of n-1 refinements.
(Formerly M1251 N0478)
|
|
43
|
|
|
1, 1, 1, 2, 4, 11, 33, 116, 435, 1832, 8167, 39700, 201785, 1099449, 6237505, 37406458, 232176847, 1513796040, 10162373172, 71158660160, 511957012509, 3819416719742, 29195604706757, 230713267586731, 1861978821637735, 15484368121967620, 131388840051760458
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Construct the ranked poset L(n) whose nodes are the A000041(n) partitions of n, with all the partitions into the same number of parts having the same rank. A partition into k parts is joined to a partition into k+1 parts if the latter is a refinement of the former.
The partition n^1 is at the left and the partition 1^n at the right. The illustration by Olivier Gérard shows the posets L(2) through L(8).
Then a(n) is the number of paths of length n-1 in L(n) that join n^1 to 1^n.
Stated another way, a(n) is the number of maximal chains in the ranked poset L(n). (This poset is not a lattice for n > 4.) - Comments corrected by Gus Wiseman, May 01 2016
|
|
REFERENCES
|
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
|
R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission]
|
|
EXAMPLE
|
a(5) = 4 because there are 4 paths from top to bottom in this lattice:
.
ooooo
/ \
o.oooo oo.ooo
| X |
o.o.ooo o.oo.oo
\ /
o.o.o.oo
|
o.o.o.o.o
.
(This is the ranked poset L(5), but drawn vertically rather than horizontally.)
|
|
MAPLE
|
v:= l-> [seq(`if`(i=1 or l[i]>l[i-1], seq(subs(1=[][], sort(subsop(
i=[j, l[i]-j][], l))), j=1..l[i]/2), [][]), i=1..nops(l))]:
b:= proc(l) option remember; `if`(max(l)<2, 1, add(b(h), h=v(l))) end:
a:= n-> b([n]):
|
|
MATHEMATICA
|
<<posets.m Table[Build[NumP[n], np]; Last@MaximalChainsDown@np, {n, 1, 25}] (* Mitch Harris, Jan 19 2006 *)
|
|
PROG
|
(Sage) def A002846(n): return Posets.IntegerPartitions(n).chain_polynomial().leading_coefficient() # Max Alekseyev, Dec 23 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|