A079124 Number of ways to partition n into distinct positive integers <= phi(n), where phi is Euler's totient function (A000010).

1, 1, 0, 1, 0, 2, 0, 4, 1, 5, 1, 11, 0, 17, 4, 13, 13, 37, 2, 53, 13, 51, 35, 103, 10, 135, 78, 167, 89, 255, 4, 339, 253, 378, 306, 542, 121, 759, 558, 872, 498, 1259, 121, 1609, 1180, 1677, 1665, 2589, 808, 3250, 1969, 3844, 3325, 5119, 1850, 6268, 4758, 7546, 7070

Offset: 0

Author

Reinhard Zumkeller, Dec 27 2002

Keywords

• nonn

References

• Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000
• Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17. Zentralblatt MATH, Zbl 1071.05501.

Crossrefs

Cf. A079126, A000009, A079122, A079125, A067953.

Cf. A227296, A036998.

Programs

Haskell

a079124 n = p [1 .. a000010 n] n where
   p _      0 = 1
   p []     _ = 0
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m
-- Reinhard Zumkeller, Jul 05 2013

Maple

with(numtheory):
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, b(n, i-1)+`if`(i>n, 0, b(n-i, i-1))))
    end:
a:= n-> b(n, phi(n)):
seq(a(n), n=0..100);  # Alois P. Heinz, May 11 2015

Mathematica

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, b[n-i, i-1]]]]; a[n_] := b[n, EulerPhi[n]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jun 30 2015, after Alois P. Heinz *)

Formula

a(n) = b(0, n), b(m, n) = 1 + sum(b(i, j): m

Extensions

a(0)=1 prepended by Alois P. Heinz, May 11 2015

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.