# Counting Fountains

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.

• Is there an n for which the program must be guaranteed to work? (i.e. after which it may break) – quintopia Dec 26 '15 at 19:42
• @quintopia It should work for all n, up to limitations of datatype, hardware, etc. – isaacg Dec 26 '15 at 19:47

## 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).

• 17 bytes in Pyth: M|sgL-Gd<ShHG1gQ0 – isaacg Dec 27 '15 at 7:09

# 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.

• Can you rewrite this as a formula (I just want to compare with the formula I found)? I just cannot read Mathematica=) – flawr Dec 26 '15 at 11:32
• @flawr The generating function of the sequence is 1/(1-x/(1-x^2/(1-x^3/(1-x^4/(1-x^5/(...)))))). – alephalpha Dec 26 '15 at 11:35
• Thanks for the explanation, that is indeed a nice approach if you have such a powerfull CAS=) – flawr Dec 26 '15 at 11:37

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 • A bug: the recursive call is t (n-p) q. Golfing tips: use an infix operator for t, swap the guards and use map instead of the list comprehension: n#p|p>n=0|p<n=sum$map((n-p)#)[1..p+1]|1<2=1. s becomes s=(#1), but you don't have to give the main function a name at all, so (#1) is enough. 48 bytes. – nimi Dec 26 '15 at 21:04
• Thanks you very much for the hints! I just started learning the basics of Haskell. I'm going to have to learn about that how the usage of # and $ here first=) – flawr Dec 26 '15 at 21:09 • A little bit of explanation: # is a user defined infix function just like +, *, etc. are predefined infix functions. $ is another way to adjust precedence (besides parentheses) f (g (h x))-> f$g$h x or in our case sum(map(...)[...]) -> sum\$map(...)[...]. – nimi Dec 26 '15 at 21:17
• Thank you, that is quite useful to know, I appreciate your explanation! – flawr Dec 26 '15 at 21:27

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


Same length with min rather than take:

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


# Pyth, 21 20 bytes

Ms?>GHgL-GHShHqGHgQ1


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

# 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;


# 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??

# 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)


# 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