login
Number of compositions of n avoiding three consecutive parts in arithmetic progression.
16

%I #31 Jun 03 2019 09:15:36

%S 1,1,2,3,7,13,22,42,81,149,278,516,971,1812,3374,6297,11770,21970,

%T 41002,76523,142901,266779,497957,929563,1735418,3239698,6047738,

%U 11289791,21076118,39344992,73448769,137113953,255965109,477835991,892023121,1665227859

%N Number of compositions of n avoiding three consecutive parts in arithmetic progression.

%C These are compositions of n whose second-differences are nonzero. - _Gus Wiseman_, Jun 03 2019

%H Joerg Arndt and Alois P. Heinz, <a href="/A238423/b238423.txt">Table of n, a(n) for n = 0..400</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Arithmetic_progression">Arithmetic progression</a>

%F a(n) ~ c * d^n, where d = 1.866800016014240677813344121155900699..., c = 0.540817940878009616510727217687704495... - _Vaclav Kotesovec_, May 01 2014

%e The a(5) = 13 such compositions are:

%e 01: [ 1 1 2 1 ]

%e 02: [ 1 1 3 ]

%e 03: [ 1 2 1 1 ]

%e 04: [ 1 2 2 ]

%e 05: [ 1 3 1 ]

%e 06: [ 1 4 ]

%e 07: [ 2 1 2 ]

%e 08: [ 2 2 1 ]

%e 09: [ 2 3 ]

%e 10: [ 3 1 1 ]

%e 11: [ 3 2 ]

%e 12: [ 4 1 ]

%e 13: [ 5 ]

%p # b(n, r, d): number of compositions of n where the leftmost part j

%p # does not have distance d to the recent part r

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

%p add(`if`(j=r+d, 0, b(n-j, j, j-r)), j=1..n))

%p end:

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

%p seq(a(n), n=0..45);

%t b[n_, r_, d_] := b[n, r, d] = If[n == 0, 1, Sum[If[j == r + d, 0, b[n - j, j, j - r]], {j, 1, n}]]; a[n_] := b[n, Infinity, 0]; Table[a[n], {n, 0, 45}] (* _Jean-François Alcover_, Nov 06 2014, after Maple *)

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Differences[#,2],0]&]],{n,0,10}] (* _Gus Wiseman_, Jun 03 2019 *)

%Y Cf. A238424 (equivalent for partitions).

%Y Cf. A238569 (equivalent for any 3-term arithmetic progression).

%Y Cf. A238686, A295370.

%Y Cf. A007862, A049988, A175342, A325545, A325849, A325851, A325874, A325875.

%K nonn

%O 0,3

%A _Joerg Arndt_ and _Alois P. Heinz_, Feb 26 2014