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
    $\begingroup$ Can you add an example? I can't understand what exactly you're trying to count. Please enumerate all possibilities for some small n. $\endgroup$ – Yuval Filmus Sep 17 '10 at 4:49
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Sep 17 '10 at 4:52
  • $\begingroup$ @Yuval Filmus, I've add an example at the end of the question. $\endgroup$ – AvatarOfChronos Sep 17 '10 at 13:55
  • $\begingroup$ To get the math equations use latex in $ signs: Example: $x^2 + y^2 = r^2$ gives $x^2 + y^2 = r^2$ $\endgroup$ – Aryabhata Sep 17 '10 at 14:27
  • $\begingroup$ @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. $\endgroup$ – Larry Wang Sep 17 '10 at 17:19

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

| cite | improve this answer | |
  • $\begingroup$ Thanks that second equation was what I was looking for. $\endgroup$ – AvatarOfChronos Sep 17 '10 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.