http://qs1969.pair.com?node_id=1179558

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(n-1, k-1) + kS(n-1, 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.
"Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
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 non-empty 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 subsets--the elements of the non-empty set have to go somewhere.
    • S(n,1) = S(n,n) = 1 : There is only one way to partition a non-empty set into one non-empty subset--the subset being the set itself. There is only one way to partition a set of n elements into n non-empty subsets--each element has to be in its own subset (a singleton set).
    • S(n,k) = S(n-1, k-1) + kS(n-1,k) : Every partition of a set of n elements into k non-empty subsets can be created from one of the partitions of a set of n-1 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)
      1. You can add the singleton set containing just the new element to any partition of n-1 elements into k-1 subsets, thus creating a partition of a set of n elements into k subsets. There are S(n-1, k-1) partitions that we can do this to.
      2. You can add the new element to any non-empty subset of a partition of n-1 elements into k non-empty subsets. There are S(n-1, 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(n-1, k) partitions, i.e., there are k*S(n-1, k) ways to get to a partition of a set of n elements into k non-empty 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 non-empty 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 non-empty 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.

      Sometimes the rule S(n,k) = 0 if k>n is given for completeness

      VERY important if you dont realize n elements ... k non-empty 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($n-1,$k-1); my $p2=fs($n-1,$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($n-1,$k-1); my $p2=s($n-1,$k ); return $p1 + ($k*$p2); }
      output
      Global symbol "$p2" requires explicit package name at buk-2.pl line 30 +. syntax error at buk-2.pl line 31, near "return" (Might be a runaway multi-line ;; string starting on line 29) Global symbol "$p1" requires explicit package name at buk-2.pl line 31 +. Global symbol "$p2" requires explicit package name at buk-2.pl line 31 +. Missing right curly or square bracket at buk-2.pl line 32, at end of l +ine syntax error at buk-2.pl line 32, at EOF Execution of buk-2.pl aborted due to compilation errors.

           ...And i learned never to name my subroutines s

        I wish I could give you more ++ for that !

                ...it is unhealthy to remain near things that are in the process of blowing up.     man page for WARP, by Larry Wall

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 non-empty subsets. It can be calculated by an explicit formula:

    S(n,k) = 1/k!.SUM[j=0 to k]( (-1)^(k-j) . 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,k-1)

    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,

    Athanasius <°(((><contra mundum Iustus alius egestas vitae, eros Piratica,

Re: [Answered; thanks.] Can this be explained in layman's terms?
by jdporter (Paladin) on Jan 14, 2017 at 23:15 UTC

      I did!

      (If you have a point to make; try making it.)

        How about read the document I linked and think carefully about how your post's title falls short.

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