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,3

Links

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

Example

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)

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

Prog

(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

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

Sequence in context: A011142 A232047 A060029 * A266777 A248518 A095700

Adjacent sequences: A100468 A100469 A100470 * A100472 A100473 A100474

Keyword

nonn

Author

David S. Newman, Nov 21 2004

Extensions

Corrected and extended by Vladeta Jovovic, Nov 24 2004

Name edited by Gus Wiseman, Jan 23 2019

Status

approved