A114901 Number of compositions of n such that each part is adjacent to an equal part.

1, 0, 1, 1, 2, 1, 5, 3, 10, 10, 21, 22, 49, 51, 105, 126, 233, 292, 529, 678, 1181, 1585, 2654, 3654, 6016, 8416, 13606, 19395, 30840, 44517, 70087, 102070, 159304, 233941, 362429, 535520, 825358, 1225117, 1880220, 2801749, 4285086, 6404354, 9769782, 14634907

Offset

0,5

Links

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

N. J. A. Sloane, Transforms

Formula

INVERT(iMOEBIUS(iINVERT(A000012 shifted right 2 places)))

G.f.: A(x,1) is the k = 1 case of A(x,k) = 1/(1 - Sum_{i>0} ( (Sum_{j>k} x^(i*j))/(1 + Sum_{j>k} x^(i*j)) ) where A(x,k) is the g.f. for compositions of n with all run-lengths > k. - John Tyler Rascoe, May 16 2024

Example

The 5 compositions of 6 are 3+3, 2+2+2, 2+2+1+1, 1+1+2+2, 1+1+1+1+1+1.
From Gus Wiseman, Nov 25 2019: (Start)
The a(2) = 1 through a(9) = 10 compositions:
  (11)  (111)  (22)    (11111)  (33)      (11122)    (44)        (333)
               (1111)           (222)     (22111)    (1133)      (11133)
                                (1122)    (1111111)  (2222)      (33111)
                                (2211)               (3311)      (111222)
                                (111111)             (11222)     (222111)
                                                     (22211)     (1111122)
                                                     (111122)    (1112211)
                                                     (112211)    (1122111)
                                                     (221111)    (2211111)
                                                     (11111111)  (111111111)
(End)

Maple

g:= proc(n, i) option remember; add(b(n-i*j, i), j=2..n/i) end:
b:= proc(n, l) option remember; `if`(n=0, 1,
      add(`if`(i=l, 0, g(n, i)), i=1..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 29 2019

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Min@@Length/@Split[#]>1&]], {n, 0, 10}] (* Gus Wiseman, Nov 25 2019 *)
g[n_, i_] := g[n, i] = Sum[b[n - i*j, i], {j, 2, n/i}] ;
b[n_, l_] := b[n, l] = If[n==0, 1, Sum[If[i==l, 0, g[n, i]], {i, 1, n/2}]];
a[n_] := b[n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, May 23 2021, after Alois P. Heinz *)

Prog

(PARI)
A_x(N, k) = { my(x='x+O('x^N), g=1/(1-sum(i=1, N, sum(j=k+1, N, x^(i*j))/(1+ sum(j=k+1, N, x^(i*j)))))); Vec(g)}
A_x(50, 1) \\ John Tyler Rascoe, May 17 2024

Crossrefs

The case of partitions is A007690.

Compositions with no adjacent parts equal are A003242.

Compositions with all multiplicities > 1 are A240085.

Compositions with minimum multiplicity 1 are A244164.

Compositions with at least two adjacent parts equal are A261983.

Cf. A178470, A238130, A274174, A329863.

Sequence in context: A085261 A179218 A131119 * A355562 A194809 A113178

Adjacent sequences: A114898 A114899 A114900 * A114902 A114903 A114904

Keyword

nonn

Author

Christian G. Bower, Jan 05 2006

Status

approved