A002846 Number of ways of transforming a set of n indistinguishable objects into n singletons via a sequence of n-1 refinements.

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

Offset: 1

Author

N. J. A. Sloane. Entry revised by N. J. A. Sloane, Jun 11 2012

Keywords

• nonn
• nice

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

Examples

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

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

• Alois P. Heinz, Table of n, a(n) for n = 1..80
• P. Erdős, R. K. Guy and J. W. Moon, On refining partitions, J. London Math. Soc., 9 (1975), 565-570.
• R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission]
• Olivier Gérard, The ranked posets L(2),...,L(8)
• Gus Wiseman, Hasse Diagrams of Partition Refinement Posets n=1..9
• Gus Wiseman, Hasse Diagrams of Partition Refinement Posets n=1..9, Version 1, [Cached copy, with permission]
• Gus Wiseman, Hasse Diagrams of Partition Refinement Posets n=1..9, Version 2, [Cached copy, with permission]

Crossrefs

See A213242, A213385, A213427 for related sequences, A327643.

Programs

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]):
seq(a(n), n=1..30);  # Alois P. Heinz, Sep 22 2019

Mathematica

<Mitch Harris, Jan 19 2006 *)

Sage

def A002846(n): return Posets.IntegerPartitions(n).chain_polynomial().leading_coefficient()  # Max Alekseyev, Dec 23 2015

Extensions

a(17)-a(25) from Mitch Harris, Jan 19 2006