20100804, 16:47  #1 
Jan 2005
Caught in a sieve
2·197 Posts 
Stacking boxes  combinatorics?
Here's a puzzle I'm working on right now. I promise it's not a homework problem. It's a problem for a program I'm considering. And I'm not sure if there's any easy solution without writing a program to solve it. It seems like combinatorics to me; but I never really studied combinatorics, so I'm hoping someone here knows an easy answer.
Suppose you have 16 cubic boxes and 16 different places to stack them. They can be in any arrangement  for example they can be laid out one in each place, or all 16 can be stacked in one place. Order doesn't matter, and orientation doesn't matter. Now define the "maximum height" of any arrangement to be the height of the tallest stack in that arrangement. Question: What is the average "maximum height" for all possible arrangements of these boxes? Question 2: Can you guess what problem I'm trying to solve here? 
20100804, 17:17  #3 
Jun 2003
The Texas Hill Country
3^{2}×11^{2} Posts 
Question: When you take an "average", it matters how many times you count each possible combination of stack sizes. So, do you consider 871 and 817 to be the same? Or are you trying to determine the expected value of the maximum number of objects that would fall in the same hash bucket  given that there is a total of 16 objects and the hash function provides a perfectly uniform hash into 16 buckets?

20100804, 17:22  #4 
Aug 2006
31×191 Posts 
The OP said that orientation and order don't matter, so that's what I assumed in my answer. Obviously if a different weighting was intended then the answer will be different.

20100804, 17:42  #5 
Jan 2005
Caught in a sieve
2×197 Posts 
That's a good question. I'm not quite sure what terminology to use.
Let me give an example where N=2, not 16. There are three possibilities: X X_ _X _X and just XX Technically, the boxes do have numbers, but I imagine what their number is doesn't matter. Let me explain #2: In nVIDIA's CUDA system, there's a usermanaged cache of memory called "shared memory". Threads access it 16 at a time. nVIDIA rather assumed that the user would access it linearly, so they set up 16 banks of memory, where the bank accessed is the address mod 16. If two threads access the same bank, it takes two accesses instead of one; three takes three accesses and so on. Well, for my application, I would need a randomaccess lookup table. If CRGreathouse is correct, that's over 6 accesses on average  not good. But thanks for solving that for me; it would have taken me hours writing an optimized recursive program. 
20100804, 17:58  #6 
Aug 2005
Seattle, WA
1,567 Posts 

20100804, 18:05  #7 
Aug 2006
1721_{16} Posts 

20100804, 18:25  #8 
Jan 2005
Caught in a sieve
2·197 Posts 
What's CLR? Common Language Runtime? My Googlefu is weak.
Edit: Found it. I may have that book; let me look. Edit2: Hm, hash chains, that's a good way to look at it, where n=m. Last fiddled with by Ken_g6 on 20100804 at 18:29 
20100804, 19:03  #9 
Jan 2005
Caught in a sieve
2×197 Posts 
OK, having looked over 123, that seems like the right problem, but I don't believe the solution (M=lg(16)/lg(lg(16) == 2 in this case). It seems to me that there's only one way to get M=1, and several ways to get M>=3.
Edit: Oh, I see, there's a constant. Anyone know what the constant is? Last fiddled with by Ken_g6 on 20100804 at 19:04 
20100804, 20:26  #11 
Jan 2005
Caught in a sieve
2×197 Posts 
That's darn close. What I'm looking for is based on that:
sum(k=1 to n, T(n,k)*k)/sum(k=1 to n, T(n,k)) Now how's that T(n,k) calculated? The "Formula" section is unclear to me. Edit: I'm also confused; shouldn't T(n,n) = 1 or n or something? But maybe I'm wrong about that? Last fiddled with by Ken_g6 on 20100804 at 20:28 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Combinatorics news  Nick  Combinatorics & Combinatorial Number Theory  7  20191214 15:25 
Finding primes using modular stacking  goatboy  Math  1  20071207 12:30 
Weight of boxes  victor  Puzzles  1  20070604 16:26 
Combinatorics  Kees  Puzzles  6  20060513 06:58 
Switching Boxes  Numbers  Hardware  7  20050912 19:10 