# Given a collection of items, how many ordered subsets can I make?

If I want to find the number of all possible groupings of a set of numbers, including all groupings with only a single number and groupings will all numbers is there a better method than this. For this use I don't want to count empty groups and order is important.

Take the summation of the number of permutations with repetition of size i where i goes from 1 to the number of items in my collection?
s = number of elements in the collection
i = number I'm summing over from one to s

$$\sum_{i=1}^{s} s^i$$

basically I want to know this: 1. will this count all possible groupings except for the empty group? 2. how do you get math equations to show up in questions for future use? 3. is there a better way to express this (if you can understand what I'm trying to say)?

Ok small example. if I have a collection (1,2,3) I want to count the possible collections that could be made from is such as: (1),(2),(3) (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3), (1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,2,3),(1,3,1),(1,3,2),(1,3,3),(2,1,1),(2,1,2),(2,1,3),(2,2,1),(2,2,2),(2,2,3),(2,3,1),(2,3,2),(2,3,3),(3,1,1),(3,1,2),(3,1,3),(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3).

so for the collection (1,2,3) I can make 39 collections from it not exceeding the length of the original collection.

• Can you add an example? I can't understand what exactly you're trying to count. Please enumerate all possibilities for some small n. – Yuval Filmus Sep 17 '10 at 4:49
• If your list starts 1, 2, 5, 15, 52 then it's the Bell numbers (q.v.). In general, given a few numbers in a sequence (which you can get by enumeration), you can try you luck in the online encyclopedia of integer sequences. – Yuval Filmus Sep 17 '10 at 4:52
• @Yuval Filmus, I've add an example at the end of the question. – AvatarOfChronos Sep 17 '10 at 13:55
• To get the math equations use latex in $ signs: Example: $x^2 + y^2 = r^2$ gives$x^2 + y^2 = r^2$– Aryabhata Sep 17 '10 at 14:27 • @AvatarOfChronos: To add on to Moron's comment, you can right-click any existing formulas and click 'show source' to see how to write something similar, or see your edited question. For more details, see the proposed faq. – Larry Wang Sep 17 '10 at 17:19 ## 1 Answer Seems like you need $$\sum_{i=1}^{s} s^i$$ This is a geometric progression with the sum $$\frac{s(s^{s} -1)}{s-1}$$ For$s=3$this gives$\frac{3(3^3 -1)}{3-1} = 39\$.

• Thanks that second equation was what I was looking for. – AvatarOfChronos Sep 17 '10 at 15:51