A069916 Number of log-concave compositions (ordered partitions) of n.

1, 1, 2, 4, 6, 9, 14, 20, 26, 36, 47, 60, 80, 102, 127, 159, 194, 236, 291, 355, 425, 514, 611, 718, 856, 1009, 1182, 1381, 1605, 1861, 2156, 2496, 2873, 3299, 3778, 4301, 4902, 5574, 6325, 7176, 8116, 9152, 10317, 11610, 13028, 14611, 16354, 18259, 20365

Offset

0,3

Comments

These are compositions with weakly decreasing first quotients, where the first quotients of a sequence are defined as if the sequence were an increasing divisor chain, so for example the first quotients of (6,3,1) are (1/2,1/3). - Gus Wiseman, Mar 16 2021

Links

Alois P. Heinz, Table of n, a(n) for n = 0..300

Sean A. Irvine, Java program (github)

Eric Weisstein's World of Mathematics, Logarithmically Concave Sequence.

Gus Wiseman, Sequences counting and ranking integer partitions by the differences of their successive parts.

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

Example

Out of the 8 compositions of 4, only 2+1+1 and 1+1+2 are not log-concave, so a(4)=6.
From Gus Wiseman, Mar 15 2021: (Start)
The a(1) = 1 through a(6) = 14 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (12)   (13)    (14)     (15)
             (21)   (22)    (23)     (24)
             (111)  (31)    (32)     (33)
                    (121)   (41)     (42)
                    (1111)  (122)    (51)
                            (131)    (123)
                            (221)    (132)
                            (11111)  (141)
                                     (222)
                                     (231)
                                     (321)
                                     (1221)
                                     (111111)
(End)

Mathematica

(* This program is not suitable for computing a large number of terms *)
compos[n_] := Permutations /@ IntegerPartitions[n] // Flatten[#, 1]&;
logConcaveQ[p_] := And @@ Table[p[[i]]^2 >= p[[i-1]]*p[[i+1]], {i, 2, Length[p]-1}]; a[n_] := Count[compos[n], p_?logConcaveQ]; Table[an = a[n]; Print["a(", n, ") = ", an]; a[n], {n, 0, 25}] (* Jean-François Alcover, Feb 29 2016 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], GreaterEqual@@Divide@@@Reverse/@Partition[#, 2, 1]&]], {n, 0, 15}] (* Gus Wiseman, Mar 15 2021 *)

Prog

(Sage) def A069916(n) : return sum(all(p[i]^2 >= p[i-1] * p[i+1] for i in range(1, len(p)-1)) for p in Compositions(n)) # Eric M. Schmidt, Sep 29 2013

Crossrefs

The version for differences instead of quotients is A070211.

A000005 counts constant compositions.

A000009 counts strictly increasing (or strictly decreasing) compositions.

A000041 counts weakly increasing (or weakly decreasing) compositions.

A001055 counts factorizations.

A002843 counts compositions with adjacent parts x <= 2y.

A003238 counts chains of divisors summing to n-1, with strict case A122651.

A003242 counts anti-run compositions.

A074206 counts ordered factorizations.

A167865 counts strict chains of divisors summing to n.

Cf. A008965, A048004, A059966, A167606, A175342, A325547.

Sequence in context: A218004 A346634 A034748 * A153140 A295341 A139135

Adjacent sequences: A069913 A069914 A069915 * A069917 A069918 A069919

Keyword

nonn,nice

Author

Pontus von Brömssen, Apr 24 2002

Status

approved