# Find number of possible arrangements of N disks with given constraint

In how many ways you can make a stack of N disks, such that:

1. Bottom disk always has radius 1

2. A disk can be placed on the stack if it radius is <= (maximum of all disk radii below it + 1)

You are given an infinite supply of disks with all radius.

I thought of couple of counting approach but that has lots of overlapping in the already counted solution and I am not able to get rid of it. :(

-
This isn’t quite clear. (1) Do all the disks have integer radii? (2) Do you have an infinite supply of disks of each radius, or do you have only one disk for each of the infinitely many possible radii? – Brian M. Scott Apr 5 '12 at 7:00
@Brian : I think it is the Towers of Hanoi – Arjang Apr 5 '12 at 7:05
@Arjang: No, it very clearly is not the Towers of Hanoi. – Brian M. Scott Apr 5 '12 at 7:12
@Arjang: Definitely not Hanoi. There the largest disk go below, here disks may be bigger than the one below. Login: A lot is not clear though. Is there exactly one disk below each non-bottom disk or can one stack like a pyramid? Maybe just give the solutions for $N=3$ to clarify the rules. – Marc van Leeuwen Apr 5 '12 at 7:14
@BrianM.Scott Disk radii are all positive integers (i.e. 1,2,3,...) and each disk is available in abundance (i.e. infinite supply of disks with radius 1,2,3,...) Hope now I make sense. – Login Test Apr 5 '12 at 11:15

I think you are looking at the Bell numbers. Henry already succinctly explained how to get this result by finding the recurrence of the Stirling numbers of the second kind (which count partitions of an $n$-set into $k$ unlabelled blocks), but I will add a bit more detail. When going from an $N-1$ stack to an $N$ stack, one of two situations arises: either the new disk is larger than any previous one, or at least one previous disk is at least as large. Designate by $k$ the size of the largest disk, then in the first situation the $N-1$ stack has $k-1$ as its largest size (and there is only one way to extend it to a stack with $k$ as largest size), while in the second situation the $N-1$ stack has $k$ as its largest size, and it can be extended by any disk of size from $1$ to $k$. Denoting by $S(N,k)$ the number of stacks of height $N$ with $k$ the size of the largest disk, we get the recurrence relation $$S(N,k) = S(N-1,k-1) + kS(N-1,k)$$ that Henry gave. You can recognise this (together with $S(N,1)=1$ and $S(1,k)=0$ for $k>1$) as the relation defining the Stirling numbers of the second kind, or in case you "forgot" that, you can compute an initial part of the (triangular) array of numbers, and recognise them, for instance by looking up in the OEIS.

Also let me clarify how you can relate your stacks to such paritions, with $k$ variable (so as to get the sum of the Stirling numbers over all $k$, giving the Bell number).

A stack partitions the set of the $N$ positions of disks (say $1$ for the bottom, up to $N$ for the top) into blocks of positions which hold disks of the same size $i$, with $i$ varying from $1$ to some maximal size $k$. To recover the stack from this partition (of which the parts are unlabelled), just label with $1$ the block that contains the bottom position $1$, then by $2$ the block with the lowest remaining position (i.e., not already in the first block), if any, then by $3$ the block with the lowest remaining position (i.e., not already in the first two blocks), if any, and so forth until labelling the last block $k$. Then put a disk of size $i$ into each position of the block labelled $i$, and that for $i=1,\ldots,k$. Clearly this satisfies your constraint, and establishes a bijection between stacks and partitions into blocks.

-
Thank You so much sir! Now I understand the solution. Sir if someone like me doesn't know all these already existing derivations (Stirling, Bell etc.) how would he work out this problem using basic theory of counting? You have already solved the problem I just need it as a food for my thinking process. I thought of a solution that was like "on position 'x' we have 'k' choices of disks but given that disks below that position have a disk with radius 'k-1'." But this way I was up to nothing. :( – Login Test Apr 5 '12 at 12:34
I've added some clarification of how one can solve this in the way close to what you tried (and which approach Henry no doubt used). Of course it does help to have seen some similar problems before. – Marc van Leeuwen Apr 5 '12 at 13:03
Thank You once again. I found where I slipped. I was not treating the tower as pieces of stacks, rather I was concentrating on ever element individually and that led me to nothing. :( Should have thought broader... :) – Login Test Apr 5 '12 at 13:25

My interpretation is that for $N=3$ the possible towers are

1   2   1   2   3
1   1   2   2   2
1   1   1   1   1


Let $k$ be the largest radius in the tower, and so the next disk can be wider at $k+1$ or can be one of the existing radii.

Let $S_2(N,k)$ be the number of towers with $N$ disks and largest radius $k$. Then $$S_2(N,k) = S_2(N-1,k-1) + k S_2(N-1,k)$$ which is the recurrence for Stirling numbers of the second kind.

Their sum over $k$ gives the Bell numbers $B_N$, which has no simple closed formula, though Dobinski's $$\frac{1}{e}\sum_{j=0}^{\infty} \frac{j^N}{j!}$$ is quite pretty.

This picture from OEIS A000110 may give an idea of why the questions are equivalent: each labelled ball is the next level up, while each new unlabelled box is the next radius up.

-
Thank You so much! You got me very correct but I think it's my bad that I couldn't get you in the first go. And probably it lacked the explanation of reducing the problem to Bell's Number calculation. I am saying this because I am weak at it. :( Thanks to Marc who shown me how to reduce the problem to calculating Bell's Number below. – Login Test Apr 5 '12 at 12:25