Stacking boxes - combinatorics?

[Ken_g6]

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?

[CRGreathouse]

For 1, I get 19/3. I'm using inefficient code based on Sloane's A008284 (my code has trouble even getting to n = 60).

For 2, I have no idea.

[Wacky]

Question: When you take an "average", it matters how many times you count each possible combination of stack sizes. So, do you consider 8-7-1 and 8-1-7 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?

[CRGreathouse]

Originally Posted by Wacky

Question: When you take an "average", it matters how many times you count each possible combination of stack sizes.

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.

[Ken_g6]

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 user-managed 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 random-access 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.

[jyb]

Originally Posted by Ken_g6

Question 2: Can you guess what problem I'm trying to solve here?

I'd guess you're trying to solve problem 12-3 in CLR (though that only gives you an upper bound on the expected maximum, not an exact value).

[CRGreathouse]

Originally Posted by Ken_g6

If CRGreathouse is correct, that's over 6 accesses on average - not good.

You described a different weighting scheme in your last post than I used, so my result (while correct for what it was) does not directly apply to you.

[Ken_g6]

What's CLR? Common Language Runtime? My Google-fu 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.

[Ken_g6]

OK, having looked over 12-3, 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?

[CRGreathouse]

Maybe what you want is Sloane's A019575? Look at that and tell me what you think.

[Ken_g6]

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?