login
Number of partitions of n into factorial parts (0! not allowed).
22

%I #53 Jun 04 2020 19:31:50

%S 1,1,2,2,3,3,5,5,7,7,9,9,12,12,15,15,18,18,22,22,26,26,30,30,36,36,42,

%T 42,48,48,56,56,64,64,72,72,82,82,92,92,102,102,114,114,126,126,138,

%U 138,153,153,168,168,183,183,201,201,219,219,237,237,258,258,279,279

%N Number of partitions of n into factorial parts (0! not allowed).

%C a(2*n+1) = a(2*n) = A117930(n). [_Reinhard Zumkeller_, Dec 04 2011]

%H Seiichi Manyama, <a href="/A064986/b064986.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..250 from Reinhard Zumkeller)

%H Youkow Homma, Jun Hwan Ryu and Benjamin Tong, <a href="http://sumry.yale.edu/sites/default/files/files/Sequence_nonsquashing_partitions.pdf">Sequence non-squashing partitions</a>, Slides from a talk, Jul 24 2014.

%H Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.

%H <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>

%F G.f.: 1/Product_{i>=1} (1-x^(i!)).

%F G.f.: 1 + Sum_{n>0} x^(n!) / Product_{k=1..n} (1 - x^(k!)). - _Seiichi Manyama_, Oct 12 2019

%F G.f.: 1 + x/(1-x) + x^2/((1-x)*(1-x^2)) + x^6/((1-x)*(1-x^2)*(1-x^6)) + ... . - _Seiichi Manyama_, Oct 12 2019

%e a(3) = 2 because we can write 3 = 2!+1! = 1!+1!+1!.

%e a(10) = 9 because 10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 = 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 = 1 + 1 + 1 + 1 + 2 + 2 + 2 = 1 + 1 + 2 + 2 + 2 + 2 = 2 + 2 + 2 + 2 + 2 = 1 + 1 + 1 + 1 + 6 = 1 + 1 + 2 + 6 = 2 + 2 + 6.

%t b[n_, i_] := b[n, i] = If[n==0 || i==1, 1, b[n, i-1] + If[i!>n, 0, b[n-i!, i]]];

%t c[n_] := Module[{i}, For[i = 1, i!<2n, i++]; b[2n, i]];

%t a[n_] := If[OddQ[n], c[(n-1)/2], c[n/2]];

%t a /@ Range[0, 100] (* _Jean-François Alcover_, Feb 04 2020, after _Alois P. Heinz_ in A117930 *)

%t Table[Length@IntegerPartitions[n, All, Factorial[Range[6]]], {n, 0, 63}] (* _Robert Price_, Jun 04 2020 *)

%o (Haskell)

%o a064986 = p (tail a000142_list) where

%o p _ 0 = 1

%o p fs'@(f:fs) m | m < f = 0

%o | otherwise = p fs' (m - f) + p fs m

%o -- _Reinhard Zumkeller_, Dec 04 2011

%o (PARI) N=66; x='x+O('x^N); m=1; while(N>=m!, m++); Vec(1/prod(k=1, m-1, 1-x^k!)) \\ _Seiichi Manyama_, Oct 13 2019

%o (PARI) N=66; x='x+O('x^N); m=1; while(N>=m!, m++); Vec(1+sum(i=1, m-1, x^i!/prod(j=1, i, 1-x^j!))) \\ _Seiichi Manyama_, Oct 13 2019

%Y Cf. A000142, A064985, A115944, A197182.

%Y Bisection gives A090632.

%K easy,nonn

%O 0,3

%A _Naohiro Nomoto_, Oct 30 2001

%E More terms from _Vladeta Jovovic_ and _Don Reble_, Nov 02 2001