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.

  • 1
    Can you add an example? I can't understand what exactly you're trying to count. Please enumerate all possibilities for some small n.2010-09-17
  • 0
    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.2010-09-17
  • 0
    @Yuval Filmus, I've add an example at the end of the question.2010-09-17
  • 0
    To get the math equations use latex in `$` signs: Example: `$x^2 + y^2 = r^2$` gives $x^2 + y^2 = r^2$2010-09-17
  • 0
    @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](http://meta.math.stackexchange.com/questions/107/what-should-go-in-the-math-stackexchange-faq/117#117).2010-09-17
  • 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