Stirling Numbers - Online Math Tutor Juan Castaneda, MS

Math

»Stirling Numbers«

Please support this site by giving a donation in the amount of your choosing. Send it to: tutor@sdmath.com via www.PayPal.com because with your help we can increase and improve the mathematical information you can find in here.

Stirling Numbers: counting Partitions and/or Equivalence Relations

The Stirling number S(n,k) equals each of:

• (A) Number of ways to distribute n distinct objets into k non-empty, indistinct bins.
• (B) Number of partitions of a set of n objects into k non-empty subsets
• (C) Number of equivalence relations with k equivalence classes, defined on a set with n elements
• (D) Number of factorizations, each with exactly k factors greater than 1, of a square-free positive integer that has exactly n different prime factors.

Recurrence Relation:

S(n,k) = S(n-1, k-1) + k*S(n-1, k)

Stirling Numbers S(n, k) with k ≤ n and 1 ≤ n ≤ 11
n = 1n = 2n = 3n = 4n = 5n = 6n = 7n = 8n = 9n = 10n = 11
k = 111111111111
k = 21371531631272555111023
k = 31625903019663025933028501
k = 4110653501701777034105145750
k = 51151401050695142525246730
k = 612126626462282779487
k = 7128462588063987
k = 813675011880
k = 91451155
k = 10155
k = 111

Stirling Numbers S(n, k) with k ≤ n and 12 ≤ n ≤ 17
n = 12n = 13n = 14n = 15n = 16n = 17
k = 1111111
k = 2204740958191163833276765535
k = 3865262616257889702375101714168621457825
k = 461150125325301039174542355950171798901694337290
k = 5137940075085014007503521076692010961905505652751651
k = 61323652932131263436373420693273273492655817505749898
k = 7627396571542449329280408741333328188260425708104786
k = 8159027189961220912320216627840214176405320415995028
k = 9222753595025135130671284908207842509528822303
k = 10170539325752752126626501937549902758334150
k = 1166243166066147947828936908512060978
k = 121783367106470275711862022324
k = 1319145501656204910178
k = 1411056020249900
k = 151120 7820
k = 161136
k = 171

Stirling Numbers S(n, k) with k ≤ n and 18 ≤ n ≤ 21
n = 18n = 19n = 20n = 21
k = 11111
k = 21310712621435242871048575
k = 3644390101934481015806064461742343625
k = 427988069851125966695045232115901181509070050
k = 5289580955451475892847107492060905003791262568401
k = 6110687251039693081601779430607889538426585679462804
k = 719746248340014929246348391114355404565282310957214948
k = 8189036065010170975100348015170932662679132511015347084
k = 9106175395755114461462680512011282644725123272476465204
k = 1037112163803477297033785591758496465571187132291275
k = 118391004908129413217791190084242948626826851689001
k = 121256328866234669513004110166333916833042030178
k = 131258546382892439160610686603801204909218331
k = 1484087782435775306302524580149304004500
k = 153672001391677845232920013087462580
k = 16999652713622350954809944464
k = 171531259774128534952799
k = 181171156751023435
k = 19119019285
k = 201210
k = 211

Some Special Cases
Looking at the table above, we can see the following patterns:

• S(n,1) = 1, because all n objects have to go into the same bin
• S(n,n) = 1, because each object has to go into a different bin
• S(n,2) = 2n-1-1
• S(n, n-1) = n(n-1)/2, this is the sequence of triangular numbers

Stirling Numbers and Surjective Functions

Stirling numbers are closely related to the problem of counting the number of surjective (onto) functions from a set with n elements to a set with k elements. However, they are not the same because:

The number of surjective (onto) functions from a set of size n to a set of size k equals the total number of ways for distributing n distinct objects into k distinct, non-empty bins; while the Stirling number S(n,k) counts the total number of ways for distributing n distinct objects into k indistinct, non-empty bins.

So, the total number of possible surjective (onto) functions from a set of size n to a set of size k equals S(n,k)*k!, that is a multiple of the Stirling number S(n,k) by a factor of k!.

Stirling Numbers in Discrete Math Homework Problems

Example Problem (1)
A group of 14 people go walking in the desert. After a while, they get lost and they get randomly separated into 5 smaller (nonempty) groups. In how many ways can this happen if we consider an isolated person as a possible group?

S(14,5) = 40,075,035 different ways.

Explanation:
The 15 people are obviously different from each other, while the difference between any two groups is solely determined by the people who are in them. No indication is given to assume that the groups could be labeled, distinguished or identified by any external factors. In this sense we can consider the people in this problem as 14 distinct "objects", and the 5 groups as indistinct "bins."

Example Problem (2)
In how many ways can a boss assign 8 different tasks to 5 employees, in such a way that each employee is responsible for at least one of these tasks, and no task is shared between employees?

S(8,5)*5! = 126,000 different ways.

Explanation:
This is a problem of counting all possible surjective functions from a set with 8 elements (the tasks) onto a set with 5 elements (the employees), because tasks are not to be shared. Therefore the applicable formula is S(n,k)*k!. The problem explicitly states that the tasks are different, so we have 8 distincts "objects" (the tasks) being distributed into 5 distinct "non-empty bins" (the employees). In this situation, even if the 5 task bundles were the same, we can still tell between different assignations by who is working on what task bundle. That is why the answer is not just S(8,5) but we need to multiply this number times (5!).

Example Problem (3)
In how many ways can the number 2,310 be expressed as the product of three whole numbers, each greater than 1? (Note: Rearranging the same three factors into a different order does not count as a different factorization)

S(5,3) = 25 such factorizations.

Explanation:
Completely factoring out 2,310 into prime factors, we find its prime factorization is 2,310 = (2)(3)(5)(7)(11).
This is a square-free number, because its prime factors are not repeated. So we can basically consider this number as the set of its five prime factors, {2, 3, 5, 7, 11}, and then partition it into three non-empty subsets, because each of the required factorizations needs to consist of three factors greater than one. Since the order of the factors does not matter, we can view this problem as distributing 5 distinct "objects" (the prime factors) into 3 indistinct "bins" (the 3 factors required in each factorization).

Example Problem (4)
In how many ways can 4 fund-raising teams be formed from 8 people? The teams are to compete against each other on the shortest time to reach the same fund-raising goal, and each team can have anywhere from a single member, up to 5 members.

S(8,4) = 1,701 ways to form the teams.

Explanation:
Here all the teams have the same function (fund-raising). The teams will be non-empty because they must have at least one member. Mentioning the 5-member upper limit is just a redundant distraction since a 6-member team would be ruled out because there are only 8 people available to form the teams. Also, the problem does not specify any possible way to distinguish the teams before they are formed. Therefore we can consider this situation as one of distributing 8 distinct "objects" (the people), into 4 indistinct non-empty "bins" (the teams). That is why the answer is directly the Stirling number S(8,4).

Set Theory Example:
Stirling Numbers S(4,1), S(4,2), S(4,3), S(4,4) and the corresponding partitions of a set with 4 elements:

Let M be the set with four elements M = {a, b, c, d}.

We will list all partitions of the set M, grouping them by k, the number of subsets of M they include.

Here the notation Pn,k,j will refer to the j-th partition with k subsets of a set with n elements. The sub-index j is only to distinguish different k-partitions. The order in our list is rather arbitrary, it is not fixed according to any set criteria.

S(4,1) = 1
Four objects going into one bin. The only partition of {a, b, c, d} into one subset is the "whole set" partition:

P4,1,1 = { {a, b, c, d} }.

S(4,2) = 7
Four objects going into two bins. These are the seven bi-partitions of set {a, b, c, d} :

P4,2,1 = { {a}, {b, c, d} }

P4,2,2 = { {b}, {a, c, d} }

P4,2,3 = { {c}, {a, b, d} }

P4,2,4 = { {d}, {a, b, c} }

P4,2,5 = { {a, b}, {c, d} }

P4,2,6 = { {a, c}, {b, d} }

P4,2,7 = { {a, d}, {b, c} }

S(4,3) = 6
Four objects going into three bins. These are the six tri-partitions of set {a, b, c, d} :

P4,3,1 = { {a, b}, {c}, {d} }

P4,3,2 = { {a, c}, {b}, {d} }

P4,3,3 = { {a, d}, {b}, {c} }

P4,3,4 = { {a}, {b, c}, {d} }

P4,3,5 = { {a}, {b, d}, {c} }

P4,3,6 = { {a}, {b}, {c, d} }

S(4,4) = 1
Four objects going into four bins. The only partition of {a, b, c, d} into four subsets is the "total split" partition:

P4,4,1 = { {a}, {b}, {c}, {d} }

Tutoring

Home

=

=

=

Online Math Tutor
• Effective
• Simple
• Affordable
• Expert Tutor
• Homework Help
• Exam Preparation
• All Math Subjects
• K-4 Through College
• Individual Online Sessions
• Excellent Results
• CSET
• GRE
• ELM
• SAT
• GMAT
• TEAS
• CBEST
• CAHSEE
• ASVAB
• ASTB
• FBI phase II
• ACT
• More...