Stirling numbers of a second kind, from the hint in the book, look correct?

In summary: This can be understood as a 2-step process where the first step is to partition X into m subsets and the second step is to choose an element of Y for each subset to be sent to.
  • #1
mr_coffee
1,629
1
Hello everyone i was wondering if someone could check to see if this looks correct or not. The question is:

If X is a set with n elements and Y is a set with m elements, express the number of onto functions from X and Y using Stirling numbers of the second kind. Justify your answer.

note: the x in the latex generated graphics means multiply not the variable 'x'.

for more info on stirling numbers of a second kind look here:
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html

Well the back of the book gave the following hint:
The number of onto functions from X = {x_1,x_2,x_3,x_4} to Y = {y_1,y_2,y_3} is [tex]S_{4,3}x3![/tex] because the construction of an onto function can be thought of as a 2-step processs where
step 1: is to choose a partion of X into 3 subsets and
step 2: is to choose, for each subset of the partition, an element of Y for the elements of the subset to be sent to.

Well in the question X has n elements in the hint 4 elements.
Y has m elements in the question and in the hint it has 3 elements.
So it looks like the answer would be:
[tex]S_{n,m} x m![/tex]
does that look right to you? thanks!
 
Last edited:
Physics news on Phys.org
  • #2
Yes, your answer looks correct. Stirling numbers of the second kind are used to count the number of onto functions from a set X with n elements to a set Y with m elements. The formula for the number of onto functions is S_{n,m} x m!.
 

1. What are Stirling numbers of a second kind?

Stirling numbers of a second kind, also known as Stirling partition numbers, are a type of combinatorial number that represent the number of ways to partition a set of n elements into k non-empty subsets.

2. How are Stirling numbers of a second kind calculated?

Stirling numbers of a second kind can be calculated using the recurrence relation S(n, k) = k*S(n-1, k) + S(n-1, k-1), with base cases S(n, 1) = 1 and S(n, n) = 1, where n represents the number of elements and k represents the number of subsets.

3. What is the significance of Stirling numbers of a second kind?

Stirling numbers of a second kind have applications in a variety of fields, including combinatorics, number theory, and probability. They are also used in the analysis of algorithms and in the study of integer partitions.

4. Can Stirling numbers of a second kind be generalized to higher orders?

Yes, Stirling numbers of a second kind can be generalized to higher orders, known as Stirling numbers of the third kind. These numbers represent the number of ways to partition a set of n elements into k non-empty subsets, where each subset has a specified number of elements.

5. How do Stirling numbers of a second kind differ from Stirling numbers of the first kind?

Stirling numbers of the first kind, also known as Stirling cycle numbers, represent the number of ways to permute a set of n elements into k disjoint cycles. In contrast, Stirling numbers of the second kind represent the number of ways to partition a set of n elements into k non-empty subsets.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
495
  • Topology and Analysis
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
890
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
931
  • Programming and Computer Science
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
7K
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
Back
Top