Young Diagrams and The Ski Lift Problem
Somewhere years ago when I was in college, I came across what seemed like a simple combinatorics problem:
"There are 3 ski lifts and 3 students who wish to ride them. Given that each lift has an unlimited amount of room to seat students, what is the total number of permutations of students on lifts?"
As a fun bonus, rather than simply solving the problem (which is really a trivial calculation on its own) I thought it would be fun to find a generating function for any number of lifts and students. Not knowing much beyond rudimentary discrete math or combinatorics, I began to work.
This at first seems like a straight-forward permutation problem: there are both students and lifts being permuted, but ultimately this is nothing a first year student couldn't reckon with. To create a generating function, it's necessary to calculate the permutations of lifts used, then multiply this by the number of permutations of students.
For the lifts, there are 3 of what I’ll call ‘unique configurations’ of occupied lifts (which I’ll demonstrate below). So, let L = number of total ski lifts, n = number of students, r = the total ‘configurations’ of occupied chairlifts, then for L = 3, n = 3, the total unique occupied ski lift permutations (r) is 3:
Configuration i = 1:
('x' is an arbitrary student)
[ x x x ] Lift 1
[ ] Lift 2
[ ] Lift 3
Configuration i = 2:
[ x x ] Lift 1
[ x ] Lift 2
[ ] Lift 3
Configuration i = 3:
[ x ] Lift 1
[ x ] Lift 2
[ x ] Lift 3
The importance of these ‘configurations’ will be revealed later. These configurations are ‘unique’ because all other configurations of occupied lifts are similar but with indices of occupied lifts permuted. For example, one permutation of configuration i=2 would involve 2 students on Lift 2 and 1 student on Lift 3. Using these unique configurations, it's possible to calculate the permutations of occupied ski lifts. Given L is the number of total lifts, let L_i be the number of non-empty lifts in the i-th configuration. Then for each configuration i, the number of permutations is P(L,L_i). So for i = 1, P(3,1) = 3. Then, i = 2, P(3,2) = 6.
There is one boundary condition,
however. It is not true that for configuration i = 3, P(3,3) = 6. Where L = L_i,
there is only 1 possible configuration in which all ski lifts are occupied by a single student. Considering this, our permutation
function for lifts is: 
As for the permutations of students, the number of student permutations is simply factorial(n). Putting this together, I wrote out the following generating function:
If you calculate the results by hand for n=3, L=3, you'll see that f(3,3) = 6 * (3 + 6 + 1) = 60 (which is correct).
This is great, but I had no mathematical method for calculating configurations. After doing some research, the answer surprised me. Turns out that this problem is an entreé into deeper number theory, as 'r' can be calculated using a function known to Number Theorists called the 'partition function.' Let’s examine the configurations again, but using the number of filled lifts to represent a configuration.
For n=3, L=3, the 3 configurations are:
3 + 0 + 0
2 + 1 + 0
1 + 1 + 1
These are the ways to uniquely add numbers to equal 3 which are called the “partitions” of 3. Representing each number as a single square, this would be:
These figures are known as Young diagrams. So now for my generating function I can now write the following:
There are boundary cases that must be considered. For the case where students outnumber lifts (ie n > L), there will be fewer unique configurations than otherwise. In this case, instead of using the partition function p(n), the sum of integers divided into k sets is used, ie p(n,k), for all k in the range [1, L]. This is because p(n) = sum(p(n,i)) for all i in range [1,n]. The proof is too long to list here, but can be found in many combinatorics texts [1]. So, instead of using p(n) we should use p(n, L), which will simplify to p(n) in the case where n = L.
Then, r(n) is:
It’s worth noting that there’s no direct calculation for p(n) or p(n,k), but there are recursive definitions. As for L_i, I don’t think there is a method of calculation except by recursion, which I haven’t yet worked out.
Later in my studies I found out that this sort of problem is well known, they’re called 'partition problems,' and computer scientists have been working on them for decades. However, studying this problem naively provided a lot of fun moments of discovery for myself that helped me learn a lot more about connections between different fields of mathematics.
//=============================================
References
Farmer, David. Combinatorics and Graph Theory. Self-published, San Francisco, CA. 2020. https://www.whitman.edu/mathematics/cgt_online/cgt.pdf
Rademacher, Hans. Topics in Analytic Number Theory. Springer-Verlag, Berlin Heidelberg, 1973. https://www.springer.com/gp/book/9783642806179
