1
$\begingroup$

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. :(

  • 0
    @MarcvanLeeuwen You have to make a single tower with a N disks and count in how many possible ways you can do it. Answer for N = 3 is 5. Possible ways are: [1,1,1], [1,1,2], [1,2,1], [1,2,2], [1,2,3] Here, first disk is the bottom disk, second is just above that and 3rd one is top disk. See the constraints are followed. We can't have an arrangement like: [1,3,2] or [1,3,1] Since, maximum radius below second disk is 1. So second disk can have a maximum radius of 1+1 i.e. 2. Hope I'm clear now.2012-04-05

2 Answers 2

1

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.

enter image description here

  • 0
    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.2012-04-05
1

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.

  • 0
    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... :)2012-04-05