CODEWITHSUNDEEP
graphgroupingpartitioningpermutationcombinatorics
zenna
zenna

Reputation: 9176

Number of all possible groupings of a set of values?

I want to find a combinatorial formula that given a certain number of integers, I can find the number of all possible groupings of these integers (such that all values belong to a single group)

Say I have 3 integers, 1, 2, 3 There would be 5 groupings:

1 2 3
1|2|3|
1 2|3
1|2 3
2|1 3

I have calculated these computationally for N = 3 to 11, but I am trying to theoretically assertain. These values are: (I believe they are correct)

num_integers num_groupings
3            5
4            15
5            52
6            203
7            877
8            4140
9            21147
10           115975
11           678570

The reason for doing this is to find the total number of partitionings of a complete graph.

Any advice, or references would be appreciated

Upvotes: 3

Views: 2156

Answers (2)

Petar Minchev
Petar Minchev

Reputation: 47373

This is called the Bell number. When you have integer sequences you don't know about look here - OEIS.

Upvotes: 1

deinst
deinst

Reputation: 18782

What you are looking for is Set Partitons. The counts that you are looking for are Bell numbers, see the wikipedia article.

Upvotes: 4

Related Questions