A342336 Number of compositions of n with all adjacent parts (x, y) satisfying x > 2y or y = 2x.

1, 1, 1, 2, 2, 2, 4, 6, 5, 6, 8, 10, 12, 15, 19, 22, 25, 28, 37, 41, 46, 62, 72, 79, 95, 113, 123, 144, 176, 200, 232, 268, 311, 363, 412, 485, 577, 658, 743, 875, 999, 1126, 1338, 1562, 1767, 2034, 2365, 2691, 3088, 3596, 4152, 4785, 5479, 6310, 7273, 8304, 9573, 11136, 12799, 14619, 16910, 19425, 22142, 25579

Offset

0,4

Comments

Also the number of compositions of n with all adjacent parts (x, y) satisfying x = 2y or y > 2x.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 121 terms from David A. Corneth)

David A. Corneth, PARI program

Example

The a(1) = 1 through a(12) = 12 compositions (A = 10, B = 11, C = 12):
  1   2   3    4    5    6     7     8      9      A       B       C
          21   13   14   15    16    17     18     19      1A      1B
                         42    25    26     27     28      29      2A
                         213   142   215    63     37      38      39
                               214   1421   216    163     137     84
                               421          2142   217     218     138
                                                   4213    263     219
                                                   21421   425     426
                                                           4214    1425
                                                           14213   2163
                                                                   4215
                                                                   14214

Maple

b:= proc(n, x) option remember; `if`(n=0, 1, add(
     `if`(x=0 or x>2*y or y=2*x, b(n-y, y), 0), y=1..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..80);  # Alois P. Heinz, Mar 14 2021

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], And@@Table[#[[i]]>2*#[[i-1]]||#[[i-1]]==2*#[[i]], {i, 2, Length[#]}]&]], {n, 0, 15}]
(* Second program: *)
b[n_, x_] := b[n, x] = If[n == 0, 1, Sum[
     If[x == 0 || x > 2y || y == 2x, b[n-y, y], 0], {y, 1, n}]];
a[n_] := b[n, 0];
a /@ Range[0, 80] (* Jean-François Alcover, May 09 2021, after Alois P. Heinz *)

Prog

(PARI) See PARI link \\ David A. Corneth, Mar 12 2021
(PARI)
C(n, pred)={my(M=matid(n)); for(k=1, n, for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); sum(q=1, n, M[q, ])}
seq(n)={concat([1], C(n, (i, j)->i>2*j || j==2*i))} \\ Andrew Howroyd, Mar 13 2021

Crossrefs

The first condition alone gives A274199, or A342098 for partitions.

The second condition alone gives A154402 for partitions.

The case of equality is A342331.

The version allowing equality (i.e., non-strict relations) is A342335.

A000929 counts partitions with adjacent parts x >= 2y.

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

A224957 counts compositions with x <= 2y and y <= 2x (strict: A342342).

A342094 counts partitions with adjacent parts x <= 2y (strict: A342095).

A342096 counts partitions without adjacent x >= 2y (strict: A342097).

A342330 counts compositions with x < 2y and y < 2x (strict: A342341).

A342332 counts compositions with adjacent parts x > 2y or y > 2x.

A342333 counts compositions with adjacent parts x >= 2y or y >= 2x.

A342337 counts partitions with adjacent parts x = y or x = 2y.

A342338 counts compositions with adjacent parts x < 2y and y <= 2x.

A342342 counts strict compositions with adjacent parts x <= 2y and y <= 2x.

Cf. A003114, A003242, A034296, A167606, A342083, A342084, A342087, A342191, A342334, A342340.

Sequence in context: A231544 A086420 A328106 * A320908 A356692 A361404

Adjacent sequences: A342333 A342334 A342335 * A342337 A342338 A342339

Keyword

nonn

Author

Gus Wiseman, Mar 10 2021

Extensions

More terms from Joerg Arndt, Mar 12 2021

Status

approved