Sets of sequences

[hv at crypt.org]

Berny <redgolpe at redgolpe.com> wrote:
:David Wilson dice:
:
:> How many sets of sequences are there that include the numbers 1 through 
:> n once? For n = 5, we might have
:> 
:> {(3, 1, 5), (4 ,2)}  and  {(1), (2, 4), (5, 3)} as examples.
:
:They should be n!*2^(n-1), since you can write a sequence of n numbers 
:in n! ways and then you can group them in 2^(n-1) ways.
:
:First few sequences:
:n=1 -> 1 : {(1)}
:n=2 -> 4 : {(1,2)},{(2,1)},{(1),(2)} and {(2),(1)}
:n=3 -> 24

Sequences are ordered, sets are not, so {(1),(2)} and {(2),(1)} are
equivalent, and a(2)=3.

For a(3), we can divide the numbers into sequences of {3}, {2,1} or {1,1,1}
elements; these splits respectively supply 6, 6 and 1 possibilities, so
a(3)=13.

I get:
n=1 => 1
n=2 => 3
n=3 => 13
n=4 => 73 ({4}={3,1}=24; {2,2}={2,1,1}=12; {1,1,1,1}=1)
n=5 => 501 ({5}={4,1}={3,2}=120; {3,1,1}={2,2,1}=60; {2,1,1,1}=20; {1,1,1,1,1}=1)
.. and that lets me lookup to find A000262:
  Number of "sets of lists": number of partitions of {1,..,n} into any
  number of lists, where a list means an ordered subset.

Hugo