Counting Fountains

Question

A fountain is arrangement of coins in rows so that each coin touches two coins in the row below it, or is in the bottom row, and the bottom row is connected. Here's a 21 coin fountain:

---

Your challenge is to count how many different fountains can be made with a given number of coins.

You will be given as input a positive integer n. You must output the number of different n-coin fountains that exist.

Standard I/O rules, standard loopholes banned. Solutions should be able to calculate n = 10 in under a minute.

---

Desired output for n = 1 ... 10:

1, 1, 2, 3, 5, 9, 15, 26, 45, 78

This sequence is OEIS A005169.

---

This is code golf. Fewest bytes wins.

Answer 1

Python, 57 bytes

f=lambda n,i=0:sum(f(n-j,j)for j in range(1,i+2)[:n])or 1

As observed on OEIS, if you shift each row half a step relative to the row below it, the column sizes form a sequence of positive integers with a maximum upward step of 1.

The function f(n,i) counts the sequences with sum n and last number i. These can be recursively summed for each choice of the next column size from 1 to i+1, which is range(1,i+2). Truncating to range(1,i+2)[:n] prevents columns from using more coins than remain, avoiding needing to say that negative n's give 0. Moreover, it avoids an explicit base case, since the empty sum is 0 and doesn't recurse, but f(0) needs to be set to 1 instead, for which or 1 suffices (as would +0**n).

Answer 2

Mathematica, 59 bytes

SeriesCoefficient[1-Fold[1-x^#2/#&,Range[#,0,-1]],{x,0,#}]&

Based on the Mathematica program on OEIS by Jean-François Alcover.

Answer 3

Haskell, 60 48 bytes

Thanks to @nimi for providing a way shorter solution!

n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1
(#1)

Old version.

t n p|p>n=0|p==n=1|p<n=sum[t (n-q) q|q<-[1..p+1]]
s n=t n 1

The function calculating the value is s, implementation of the recursive formula found here: https://oeis.org/A005169

Answer 4

Pyth, 21 20 bytes

Ms?>GHgL-GHShHqGHgQ1

Try it online. Test suite.

This is a direct implementation of the recursive formula on the OEIS page, like the Matlab answer.

Answer 5

Haskell, 43 bytes

n%i=sum[(n-j)%j|j<-take n[1..i+1]]+0^n
(%0)

See Python answer for explanation.

Same length with min rather than take:

n%i=sum[(n-j)%j|j<-[1..min(i+1)n]]+0^n
(%0)

Answer 6

Matlab, 115 105 bytes

function F=t(n,varargin);p=1;if nargin>1;p=varargin{1};end;F=p==n;if p<n;for q=1:p+1;F=F+t(n-p,q);end;end

Implementation of the recursive formula found here: https://oeis.org/A005169

function F=t(n,varargin);
p=1;
if nargin>1
    p=varargin{1};
end;
F=p==n;
if p<n;
    for q=1:p+1;
        F=F+t(n-p,q);
    end;
end;

Answer 7

Julia, 44 43 bytes

f(a,b=1)=a>b?sum(i->f(a-b,i),1:b+1):1(a==b)

This uses recursive formula on OEIS.

Explanation

function f(a, b=1)
    if a > b
        # Sum of recursing
        sum(i -> f(a-b, i), 1:b+1)
    else
        # Convert bool to integer
        1 * (a == b)
    end
end

Has anyone else noticed that strike through 44 is regular 44??

Answer 8

Python 3, 88 bytes

f=lambda n,p:sum([f(n-p,q)for q in range(1,p+2)])if p<n else int(p==n)
t=lambda n:f(n,1)

Answer 9

JavaScript (ES6), 63

Implementing the recursive formula at OEIS page

F=(n,p=1,t=0,q=0)=>p<n?eval("for(;q++<=p;)t+=F(n-p,q)"):p>n?0:1