0
$\begingroup$

The biggest challenge to solve the problem is that I can't really picture a pyramid. And it is hard to make a model. The pyramids I am trying to find include those on all tiers.

$\endgroup$
  • $\begingroup$ Say the base is a n by n square $\endgroup$ – most venerable sir Apr 19 '14 at 22:10
1
$\begingroup$

Some clarification first, to make sure I understand your question correctly: I assume that you mean a step pyramid which has a single unit cube at its pinnacle. Every lower tier will be one unit in height and have edges which are two units longer than the tier above, so that you get a constant one unit step width all around.

I assume that you mean a pyramid is included in another pyramid if all the cubes which make up the smaller pyramid are also included in the larger pyramid, and if the vertical directions of the two pyramids are the same. In other words, your smaller pyramids need not necessarily stand on the same ground plane as the larger pyramid, but they are not allowed to lie on their side.

At level $i$ of the pyramid, counting from the top and starting at $1$, the edge length will be $2i-1$ so there will be $(2i-1)^2$ cubes in that level. These cubes can each be the pinnacle of different smaller pyramids, ranging from the single cube minimal one to the one which extends up to the base of the big pyramid. So if the big pyramid has $n$ tiers, then you get $n-i+1$ smaller pyramids with that cube at its pinnacle. Now you can count pyramids:

$$\sum_{i=1}^n(n-i+1)(2i-1)^2=\tfrac16n(2n^3+4n^2+n-1)$$

This is A006324: 1, 11, 46, 130, 295, 581, 1036, 1716, 2685, 4015, 5786, 8086…

Of course, it might be that a smaller pyramid is only a pyramid if it starts at ground level. Then things are even easier, since for every cube there is exactly one pyramid which has that cube as its pinnacle and extends all the way down to the ground. So in fact you only have to count cubes.

$$\sum_{i=1}^n(2i-1)^2=\tfrac13n(4n^2-1)$$

This is A000447: 1, 10, 35, 84, 165, 286, 455, 680, 969, 1330, 1771, 2300…

$\endgroup$
  • $\begingroup$ Are you sure that the formula include those that are upside down? $\endgroup$ – most venerable sir Apr 22 '14 at 17:11
  • $\begingroup$ @user139024: I am sure that it does not contain upside-down ones. I should make that fact more explicit. Do you need those as well? $\endgroup$ – MvG Apr 22 '14 at 17:33
  • $\begingroup$ Yes, it would be nice if you can include those in your formula. $\endgroup$ – most venerable sir Apr 22 '14 at 17:47
  • $\begingroup$ Oh wait I got it. The second part of the formula 2i-1 is only counting the number of one by one square that can be seen as pinnacles. Ok, the formula does not repeat in fact. $\endgroup$ – most venerable sir Apr 22 '14 at 18:08
  • $\begingroup$ You basically make a pyramids that is composed of cubes. But the problem with this is that then, it would be hard for me to see where are the pinnacle of upside down pyramids. $\endgroup$ – most venerable sir Apr 22 '14 at 18:11
2
$\begingroup$

If a pyramid is defined as stacking squares of $n^2$ squares on top of each other for $n=n_0$ to $n=n_1$, then for a pyramid with base side length $N$ the only question is how many square bases can you find at level $n$ in the original pyramid with base side length $N$. Note for $n = N$ this is one. For $n = N - 1$ this is $2^2 + 1 =5$, because you have two choices for where to start each side of the smaller pyramid if you start at the base, and one choice if you start one level higher. For $n = N- k$ the answer is $\sum_{k=0}^n (k+1)^2$. So you get $\sum_{n=0}^N \sum_{k=0}^n (k + 1)^2$. You can find a formula for sum-of-conesecutive-squares, and then apply formulas for sums of consecutive powers for powers up to $3$ to get a closed form formula.

$\endgroup$
  • $\begingroup$ +1, This is a really nice solution. Not even a model is required, you can visualize it all pretty well in your head. $\endgroup$ – recursive recursion Apr 19 '14 at 22:46
  • $\begingroup$ n=$n_0$ and n=$n_1$ I am not very clear about this part. $\endgroup$ – most venerable sir Apr 19 '14 at 23:12
  • $\begingroup$ The value of n has to be smaller as go up towards the peak. $\endgroup$ – most venerable sir Apr 20 '14 at 2:31
  • $\begingroup$ $$\sum_{n=0}^N \sum_{k=0}^n (k + 1)^2=\frac1{12}(N+1)(N+2)^2(N+3)$$ which gives a count of 6 for $N=1$. That looks incorrect to me. Apart from that you get oeis.org/A002415, which I'm adding just for reference. $\endgroup$ – MvG Apr 22 '14 at 7:47
  • $\begingroup$ Note: OP asked for details about this answer in a separate post. $\endgroup$ – MvG Apr 22 '14 at 12:45
1
$\begingroup$

For pyramids with a $1\times 1$ base (not sure if that counts) there are $1+2^2+3^2+\cdots+n^2$ possible.

For those with a $2\times 2$ base there are $1+2^2+\cdots+(n-1)^2$ possible.

And so on. The total sum is therefore $$(1^2+\cdots +n^2)+(1^2+\cdots +(n-1)^2)+\cdots+(1^2)$$ $${1\over 6}\sum_{k=1}^n{k(k+1)(2k+1)}={1\over 6}\left(2\sum{k^3}+3\sum{k^2}+\sum{k}\right)$$ $$={1\over 6}\left(2\left(\frac{n(n+1)}{2}\right)+3\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right)$$ And you can simplify from there. PS I strongly encourage you to build that model you were talking about. Just use some Legos or something.

$\endgroup$
  • $\begingroup$ Why is it that there are that many possibilities for those with a 2 by 2 base? $\endgroup$ – most venerable sir Apr 21 '14 at 21:47
  • $\begingroup$ See also oeis.org/A000292 $\endgroup$ – MvG Apr 22 '14 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.