packs of shirts

This fun exercise comes from "Problems and Recreations," by Ralph E. Winger, Ralph Leighton's great-uncle (after whom he was named). Winger was a graduate of Caltech, and Robert Leighton's  physics teacher at Los Angeles City College.

A wholesaler sells six patterns of shirts, and packs them in boxes each containing six shirts. Since his customers have different demands for different patterns, the jobber wishes to pack boxes in advance, so that he can pull any kind of pack the retailer desires off the shelf. How many different packs must he prepare?

Solution by Keith Wald

Simple combinatorial solution to "packs of shirts".

This calls for the trusty "stars and bars" method of Combinatorics. We can (mentally) divide each box into 6 partitions by using 6-1 = 5 walls, or "bars". (We don't need walls on the ends because the box walls take care of that.) And we can represent the shirts of each pattern by "stars", since shirts of a given pattern are identical. So, for example, one pack will contain one shirt of each pattern, which we can represent like this:

* | * | * | * | * | *

Another pack will contain, say, two shirts of the first pattern, four of the second pattern, and no others, which we can represent like this:

* * | * * * * |  |  |  |

and so on for all the different possible packs. The problem is to count up all these packs.

It's actually instructive (and no more difficult) to consider the general case:  n shirt patterns and k shirts per pack.This amounts to choosing k shirts out of the n patterns, with repetition allowed. So our general case diagram would contain (n-1) bars and k stars. In how many ways can we arrange (n-1) bars and k stars? Well, imagine (n-1+k) "sites" in a row. Each site is either a star or a bar. The first bar can go in any one of the (n-1+k) sites. Then the second bar can go in any one of the remaining (n-2+k) sites, and so on down, until the last remaining bar can go in any of the remaining (k+1) sites. But the bars are identical, so we have to divide by the number of bar permutations, (n-1)!. Thus the number of arrangements is:

N  = (n-1+k)(n-2+k)...(k+1) / (n-1)!

=  (n-1+k)! / [k!(n-1)!]

Finally, for our "6 by 6" problem, this is:

11*10*9*8*7 / (5*4*3*2*1)

=  462.