This morning I thought of a nice little combinatorial pattern, and so I investigated a bit.
Consider the set of finite nonempty sequences of positive integers starting with 1, with the restriction that a number N cannot appear in the sequence until N-1 has appeared. For any given length, the subset of sequences of that length is finite, so we can list them. For length 1 we have just the sequence containing the number 1. For length 2 we have (1 1) and (1 2). For lengths 3 and 4 there are 5 and 15 sequences respectively:
1,1,1 1,1,2 1,2,1 1,2,2 1,2,3 1,1,1,1 1,1,1,2 1,1,2,1 1,1,2,2 1,1,2,3 1,2,1,1 1,2,1,2 1,2,1,3 1,2,2,1 1,2,2,2 1,2,2,3 1,2,3,1 1,2,3,2 1,2,3,3 1,2,3,4
If we plug the sequence (1 2 5 15) into the Encyclopedia of Integer Sequences, we find the Bell numbers, which I had not heard of until now. They have a Wikipedia article as well.
Apparently the Bell numbers have a number of interpretations (though with a brief scan of the OIES entry I didn’t see mine), and the easiest one to relate to these sequences is the “number of ways of placing n labeled balls into n indistinguishable boxes”.
To see the connection, say we have n labeled balls. A particular placement into indistinguishable boxes will correspond to one of these sequences. Assume our balls are labeled from 1 to n. Then we’re going to create a list of the boxes that each ball goes in, in order of their labels. Since the boxes are unlabeled, we can give them names: call the box that the first ball goes into “1”. Then call the next new box in the list “2”, and the next new one “3”, and so on. In this way we’ll get a sequence of n positive integers, not necessarily ever greater that 1 (perhaps all the balls went in the same box), but with the property that any number N does not appear until N-1 has already appeared.
Here are the 52 sequences of length 5:
1,1,1,1,1 1,1,2,3,3 1,2,2,1,2 1,2,3,2,1 1,1,1,1,2 1,1,2,3,4 1,2,2,1,3 1,2,3,2,2 1,1,1,2,1 1,2,1,1,1 1,2,2,2,1 1,2,3,2,3 1,1,1,2,2 1,2,1,1,2 1,2,2,2,2 1,2,3,2,4 1,1,1,2,3 1,2,1,1,3 1,2,2,2,3 1,2,3,3,1 1,1,2,1,1 1,2,1,2,1 1,2,2,3,1 1,2,3,3,2 1,1,2,1,2 1,2,1,2,2 1,2,2,3,2 1,2,3,3,3 1,1,2,1,3 1,2,1,2,3 1,2,2,3,3 1,2,3,3,4 1,1,2,2,1 1,2,1,3,1 1,2,2,3,4 1,2,3,4,1 1,1,2,2,2 1,2,1,3,2 1,2,3,1,1 1,2,3,4,2 1,1,2,2,3 1,2,1,3,3 1,2,3,1,2 1,2,3,4,3 1,1,2,3,1 1,2,1,3,4 1,2,3,1,3 1,2,3,4,4 1,1,2,3,2 1,2,2,1,1 1,2,3,1,4 1,2,3,4,5
Comments