3
$\begingroup$

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.

  • 0
    @ Moron & Kaestur Hakarl: Thanks for the information.2010-09-17

1 Answers 1

4

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

  • 0
    Thanks that second equation was what I was looking for.2010-09-17