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

%I #31 May 17 2024 05:21:56

%S 1,0,1,1,2,1,5,3,10,10,21,22,49,51,105,126,233,292,529,678,1181,1585,

%T 2654,3654,6016,8416,13606,19395,30840,44517,70087,102070,159304,

%U 233941,362429,535520,825358,1225117,1880220,2801749,4285086,6404354,9769782,14634907

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

%H Alois P. Heinz, <a href="/A114901/b114901.txt">Table of n, a(n) for n = 0..4000</a>

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

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

%F 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

%e 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.

%e From _Gus Wiseman_, Nov 25 2019: (Start)

%e The a(2) = 1 through a(9) = 10 compositions:

%e (11) (111) (22) (11111) (33) (11122) (44) (333)

%e (1111) (222) (22111) (1133) (11133)

%e (1122) (1111111) (2222) (33111)

%e (2211) (3311) (111222)

%e (111111) (11222) (222111)

%e (22211) (1111122)

%e (111122) (1112211)

%e (112211) (1122111)

%e (221111) (2211111)

%e (11111111) (111111111)

%e (End)

%p g:= proc(n, i) option remember; add(b(n-i*j, i), j=2..n/i) end:

%p b:= proc(n, l) option remember; `if`(n=0, 1,

%p add(`if`(i=l, 0, g(n,i)), i=1..n/2))

%p end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Nov 29 2019

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Min@@Length/@Split[#]>1&]],{n,0,10}] (* _Gus Wiseman_, Nov 25 2019 *)

%t g[n_, i_] := g[n, i] = Sum[b[n - i*j, i], {j, 2, n/i}] ;

%t b[n_, l_] := b[n, l] = If[n==0, 1, Sum[If[i==l, 0, g[n, i]], {i, 1, n/2}]];

%t a[n_] := b[n, 0];

%t a /@ Range[0, 50] (* _Jean-François Alcover_, May 23 2021, after _Alois P. Heinz_ *)

%o (PARI)

%o 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)}

%o A_x(50,1) \\ _John Tyler Rascoe_, May 17 2024

%Y The case of partitions is A007690.

%Y Compositions with no adjacent parts equal are A003242.

%Y Compositions with all multiplicities > 1 are A240085.

%Y Compositions with minimum multiplicity 1 are A244164.

%Y Compositions with at least two adjacent parts equal are A261983.

%Y Cf. A178470, A238130, A274174, A329863.

%K nonn

%O 0,5

%A _Christian G. Bower_, Jan 05 2006