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

1, 1, 2, 2, 4, 4, 7, 8, 11, 13, 18, 20, 27, 32, 40, 44, 60, 67, 82, 93, 114, 129, 161, 175, 209, 239, 285, 315, 372, 416, 484, 545, 631, 698, 811, 890, 1027, 1146, 1304, 1437, 1631, 1805, 2042, 2252, 2539, 2785, 3143, 3439, 3846, 4226, 4722, 5159

Offset: 0

Author

David S. Newman, Nov 21 2004

Keywords

• nonn

Examples

			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.
From _Gus Wiseman_, Jan 23 2019: (Start)
The a(1) = 1 through a(8) = 11 integer partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (111)  (22)    (311)    (33)      (322)      (44)
                    (211)   (2111)   (222)     (511)      (422)
                    (1111)  (11111)  (411)     (4111)     (611)
                                     (3111)    (22111)    (2222)
                                     (21111)   (31111)    (5111)
                                     (111111)  (211111)   (41111)
                                               (1111111)  (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
(End)
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..8000 (terms 0..1000 from Alois P. Heinz)

Crossrefs

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

Programs

Haskell

a100471 n = p 0 (n + 1) 1 n where
   p m m' k x | x == 0    = if m < m' || m == 0 then 1 else 0
              | x < k     = 0
              | m == 0    = p 1 m' k (x - k) + p 0 m' (k + 1) x
              | otherwise = p (m + 1) m' k (x - k) +
                            if m < m' then p 0 m (k + 1) x else 0
-- Reinhard Zumkeller, Dec 27 2012

Maple

b:= proc(n,i,t) option remember;
      if n<0 then 0
    elif n=0 then 1
    elif i=1 then `if`(n>t, 1, 0)
    elif i=0 then 0
    else      b(n, i-1, t)
         +add(b(n-i*j, i-1, j), j=t+1..floor(n/i))
      fi
    end:
a:= n-> b(n, n, 0):
seq(a(n), n=0..60);  # Alois P. Heinz, Feb 21 2011

Mathematica

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 *)
Table[Length[Select[IntegerPartitions[n],OrderedQ@*Split]],{n,20}] (* Gus Wiseman, Jan 23 2019 *)

Extensions

Corrected and extended by Vladeta Jovovic, Nov 24 2004

Name edited by Gus Wiseman, Jan 23 2019