cp's OEIS Frontend

A232464 Number of compositions of n avoiding the pattern 1111.

%I A232464 #26 Nov 20 2023 16:03:19
%S A232464 1,1,2,4,7,15,26,52,93,173,310,556,1041,1789,3098,5620,9725,16377,
%T A232464 28764,48518,82889,137161,237502,390084,646347,1055975,1774036,
%U A232464 2907822,4698733,7581093,12381660,19891026,32113631,51110319,80777888,130175410,204813395
%N A232464 Number of compositions of n avoiding the pattern 1111.
%C A232464 Number of compositions of n into parts with multiplicity <= 3.
%H A232464 Alois P. Heinz, <a href="/A232464/b232464.txt">Table of n, a(n) for n = 0..3000</a>
%e A232464 a(5) = 15: [5], [4,1], [3,2], [2,3], [1,4], [1,2,2], [2,1,2], [1,1,3], [3,1,1], [2,2,1], [1,3,1], [1,2,1,1], [2,1,1,1], [1,1,2,1], [1,1,1,2].
%e A232464 a(6) = 26: [6], [3,3], [5,1], [4,2], [2,4], [1,5], [4,1,1], [3,2,1], [2,3,1], [1,4,1], [3,1,2], [2,2,2], [1,3,2], [1,2,3], [2,1,3], [1,1,4], [1,2,2,1], [2,1,2,1], [1,1,3,1], [3,1,1,1], [2,2,1,1], [1,3,1,1], [1,2,1,2], [2,1,1,2], [1,1,2,2], [1,1,1,3].
%p A232464 b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
%p A232464       add(b(n-i*j, i-1, p+j)/j!, j=0..min(n/i, 3))))
%p A232464     end:
%p A232464 a:= n-> b(n$2, 0):
%p A232464 seq(a(n), n=0..50);
%t A232464 f[list_]:=Apply[And,Table[Count[list,i]<4,{i,1,Max[list]}]];
%t A232464 g[list_]:=Length[list]!/Apply[Times,Table[Count[list,i]!,{i,1,Max[list]}]];
%t A232464 a[n_] := If[n == 0, 1, Total[Map[g, Select[IntegerPartitions[n], f]]]];
%t A232464 Table[a[n], {n, 0, 40}] (* _Geoffrey Critzer_, Nov 25 2013, updated by _Jean-François Alcover_, Nov 20 2023 *)
%Y A232464 Cf. A001935 (partitions avoiding 1111), A032020 (pattern 11), A232432 (pattern 111), A232394 (consecutive pattern 1111).
%Y A232464 Column k=3 of A243081.
%K A232464 nonn
%O A232464 0,3
%A A232464 _Alois P. Heinz_, Nov 24 2013