login
Number of integer partitions of n whose sequence of frequencies is strictly increasing.
17

%I #33 Sep 23 2019 03:38:44

%S 1,1,2,2,4,4,7,8,11,13,18,20,27,32,40,44,60,67,82,93,114,129,161,175,

%T 209,239,285,315,372,416,484,545,631,698,811,890,1027,1146,1304,1437,

%U 1631,1805,2042,2252,2539,2785,3143,3439,3846,4226,4722,5159

%N Number of integer partitions of n whose sequence of frequencies is strictly increasing.

%H Vaclav Kotesovec, <a href="/A100471/b100471.txt">Table of n, a(n) for n = 0..8000</a> (terms 0..1000 from Alois P. Heinz)

%e a(4) = 4 because of the 5 unrestricted partitions of 4, only one, 3+1 uses each of its summands just once and 1,1 is not an increasing sequence.

%e From _Gus Wiseman_, Jan 23 2019: (Start)

%e The a(1) = 1 through a(8) = 11 integer partitions:

%e (1) (2) (3) (4) (5) (6) (7) (8)

%e (11) (111) (22) (311) (33) (322) (44)

%e (211) (2111) (222) (511) (422)

%e (1111) (11111) (411) (4111) (611)

%e (3111) (22111) (2222)

%e (21111) (31111) (5111)

%e (111111) (211111) (41111)

%e (1111111) (221111)

%e (311111)

%e (2111111)

%e (11111111)

%e (End)

%p b:= proc(n,i,t) option remember;

%p if n<0 then 0

%p elif n=0 then 1

%p elif i=1 then `if`(n>t, 1, 0)

%p elif i=0 then 0

%p else b(n, i-1, t)

%p +add(b(n-i*j, i-1, j), j=t+1..floor(n/i))

%p fi

%p end:

%p a:= n-> b(n, n, 0):

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Feb 21 2011

%t b[n_, i_, t_] := b[n, i, t] = Which[n<0, 0, n==0, 1, i==1, If[n>t, 1, 0], i == 0, 0 , True, b[n, i-1, t] + Sum[b[n-i*j, i-1, j], {j, t+1, Floor[n/i]}]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 60}] (* _Jean-François Alcover_, Mar 16 2015, after _Alois P. Heinz_ *)

%t Table[Length[Select[IntegerPartitions[n],OrderedQ@*Split]],{n,20}] (* _Gus Wiseman_, Jan 23 2019 *)

%o (Haskell)

%o a100471 n = p 0 (n + 1) 1 n where

%o p m m' k x | x == 0 = if m < m' || m == 0 then 1 else 0

%o | x < k = 0

%o | m == 0 = p 1 m' k (x - k) + p 0 m' (k + 1) x

%o | otherwise = p (m + 1) m' k (x - k) +

%o if m < m' then p 0 m (k + 1) x else 0

%o -- _Reinhard Zumkeller_, Dec 27 2012

%Y Cf. A000219, A000837 (frequencies are relatively prime), A047966 (frequencies are equal), A098859 (frequencies are distinct), A100881, A100882, A100883, A304686 (Heinz numbers of these partitions).

%K nonn

%O 0,3

%A _David S. Newman_, Nov 21 2004

%E Corrected and extended by _Vladeta Jovovic_, Nov 24 2004

%E Name edited by _Gus Wiseman_, Jan 23 2019