BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:
The number of partitions of size k of a set of n elements are known as Stirling numbers of the second kind, and satisfy the recursion:
 S(0, 0) = 1
 S(n, 0) = 0 if n > 0
 S(n, 1) = S(n, n) = 1
 S(n, k) = S(n1, k1) + kS(n1, k)
The source is a cpan perl module; a google search will almost certainly discover which one; but that is irrelevant.
All I'm looking for is a tangible explanation of the above description.
Can any Monk put me in my place by transcribing the above description Into English?
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks  Silence betokens consent  Love the truth but pardon error.
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Can this be explained in layman's terms?
by jaredor (Priest) on Jan 14, 2017 at 07:27 UTC

Hi BrowserUk,
I'm a lackluster mathematics student, but perhaps I can volunteer an explanation that doesn't stray too far from the rigor.
First, I think I would like to recast your statement as "For any set of n elements the number of ways to partition the set into k nonempty subsets is denoted S(n,k) and these numbers are known as Stirling numbers of the second kind."
 S(0,0) = 1 : There is only one way to make no partitions out of nothing.
 S(n,0) = 0 if n>0 : If you have a set of something, you cannot have a partition with no subsetsthe elements of the nonempty set have to go somewhere.
 S(n,1) = S(n,n) = 1 : There is only one way to partition a nonempty set into one nonempty subsetthe subset being the set itself. There is only one way to partition a set of n elements into n nonempty subsetseach element has to be in its own subset (a singleton set).
 S(n,k) = S(n1, k1) + kS(n1,k) : Every partition of a set of n elements into k nonempty subsets can be created from one of the partitions of a set of n1 elements. The sum comes about by looking at the two ways a new, identified, element can be added to the partitions (thus making a new partition that is of a larger set of n elements)
 You can add the singleton set containing just the new element to any partition of n1 elements into k1 subsets, thus creating a partition of a set of n elements into k subsets. There are S(n1, k1) partitions that we can do this to.
 You can add the new element to any nonempty subset of a partition of n1 elements into k nonempty subsets. There are S(n1, k) partitions that we can do this to and since we have k subsets in any partition, we have k ways to modify each of the S(n1, k) partitions, i.e., there are k*S(n1, k) ways to get to a partition of a set of n elements into k nonempty subsets this way.
Note that because we are talking about an identified element being included, then this sum counts each possible partition of a set of n elements into k nonempty subsets exactly once. The identified element must be in any partition of this set of n elements. The identified element is either in a subset by itself (case 1) or in a subset with at least one other element (case 2).
Sometimes the rule S(n,k) = 0 if k>n is given for completeness, i.e., you can't partition something up into more nonempty subsets than for which it has elements, but this is considered obvious and you won't run into the need for it if you start with any reasonable case where n>=k.
 [reply] 

Sometimes the rule S(n,k) = 0 if k>n is given for completeness
VERY important if you dont realize n elements ... k nonempty subsets
and you just start with
for $n (0..10) {
for $k (0..10) {
print "$n $k '.fs($n,$k)."\n";
}
}
use strict; use warnings;
my $l='k ';
$l.=sprintf "%3d ",0;
for my $k (0..10){
$l.=sprintf " %10s",$k;
}
print $l."\n";
$l=~s/.//g;
print $l."\n";
for my $n (0..10){
printf "n %3d ",$n;
for my $k (0..10){
printf " %10s",fs($n,$k);
}
print "\n";
}
sub fs {
my $n=shift;
my $k=shift;
if ( $n ==0 && $k == 0 ) {return 1};
if ( $k > $n ) {return 0}; # important
if ( $n > 0 && $k == 0 ) {return 0}
if ( $k == 1 ) {return 1}
if ($n == $k ) {return 1}
my $p1=fs($n1,$k1);
my $p2=fs($n1,$k );
return $p1 + ($k*$p2);
}
And i learned never to name my subroutines s
use strict; use warnings;
my $l='k ';
$l.=sprintf "%3d ",0;
for my $k (0..10){
$l.=sprintf " %10s",$k;
}
print $l."\n";
$l=~s/.//g;
print $l."\n";
for my $n (0..10){
printf "n %3d ",$n;
for my $k (0..10){
printf " %10s",s($n,$k);
}
print "\n";
}
sub s {
my $n=shift;
my $k=shift;
if ( $n ==0 && $k == 0 ) {return 1};
if ( $k > $n ) {return 0}; # important
if ( $n > 0 && $k == 0 ) {return 0}
if ( $k == 1 ) {return 1}
if ($n == $k ) {return 1}
my $p1=s($n1,$k1);
my $p2=s($n1,$k );
return $p1 + ($k*$p2);
}
output
Global symbol "$p2" requires explicit package name at buk2.pl line 30
+.
syntax error at buk2.pl line 31, near "return"
(Might be a runaway multiline ;; string starting on line 29)
Global symbol "$p1" requires explicit package name at buk2.pl line 31
+.
Global symbol "$p2" requires explicit package name at buk2.pl line 31
+.
Missing right curly or square bracket at buk2.pl line 32, at end of l
+ine
syntax error at buk2.pl line 32, at EOF
Execution of buk2.pl aborted due to compilation errors.
 [reply] [d/l] [select] 

 [reply] 

 [reply] 
Re: Can this be explained in layman's terms?
by Athanasius (Archbishop) on Jan 14, 2017 at 07:41 UTC

Hello BrowserUk,
A Stirling number of the second kind, S(n,k), gives the number of ways in which a set of n elements can be partitioned into exactly k nonempty subsets. It can be calculated by an explicit formula:
S(n,k) = 1/k!.SUM[j=0 to k]( (1)^(kj) . kCj . j^n )
where kCj is a binomial coefficient (“ k select j ”). But if you’re calculating successive values of S, it will be more efficient to use the recurrence relation:
S(n+1,k) = k.S(n,k) + S(n,k1)
Here’s a simple implementation:
I would say, “hope that helps,” but I’m sure you already know all of the above. So my best hope is that it will help you to clarify what you mean by “tangible explanation” and “transcribing the above description into English.” Then again, if what you’re really after is an explanation of the maths behind the formulae, you’ll need an actual mathematician. ;)
Cheers,
 [reply] [d/l] [select] 
Re: [Answered; thanks.] Can this be explained in layman's terms?
by jdporter (Chancellor) on Jan 14, 2017 at 23:15 UTC

 [reply] 

 [reply] 

 [reply] 



 A reply falls below the community's threshold of quality. You may see it by logging in.


