A238351 Number of compositions p(1)+p(2)+...+p(k) = n such that for no part p(i) = i (compositions without fixed points).

1, 0, 1, 2, 3, 6, 11, 22, 42, 82, 161, 316, 624, 1235, 2449, 4864, 9676, 19267, 38399, 76582, 152819, 305085, 609282, 1217140, 2431992, 4860306, 9714696, 19419870, 38824406, 77624110, 155208405, 310352615, 620601689, 1241036325, 2481803050, 4963170896

Offset: 0

Author

Joerg Arndt and Alois P. Heinz, Feb 25 2014

Keywords

• nonn

Comments

Column k=0 of A238349 and of A238350.

Examples

			The a(7) = 22 such compositions are:
01:  [ 2 1 1 1 1 1 ]
02:  [ 2 1 1 1 2 ]
03:  [ 2 1 1 2 1 ]
04:  [ 2 1 1 3 ]
05:  [ 2 1 2 1 1 ]
06:  [ 2 1 2 2 ]
07:  [ 2 1 4 ]
08:  [ 2 3 1 1 ]
09:  [ 2 3 2 ]
10:  [ 2 4 1 ]
11:  [ 2 5 ]
12:  [ 3 1 1 1 1 ]
13:  [ 3 1 1 2 ]
14:  [ 3 1 2 1 ]
15:  [ 3 3 1 ]
16:  [ 3 4 ]
17:  [ 4 1 1 1 ]
18:  [ 4 1 2 ]
19:  [ 4 3 ]
20:  [ 5 1 1 ]
21:  [ 6 1 ]
22:  [ 7 ]
		

References

• M. Archibald, A. Blecher and A. Knopfmacher, Fixed points in compositions and words, accepted by the Journal of Integer Sequences

Links

• Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..1000
• M. Archibald, A. Blecher, and A. Knopfmacher, Fixed Points in Compositions and Words, J. Int. Seq., Vol. 23 (2020), Article 20.11.1.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, 1,
       add(`if`(i=j, 0, b(n-j, i+1)), j=1..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..50);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[If[i == j, 0, b[n-j, i+1]], {j, 1, n}]]; a[n_] := b[n, 1]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 06 2014, after Maple *)

Formula

a(n) ~ c * 2^n, where c = A048651/2 = 0.14439404754330121... - Vaclav Kotesovec, May 01 2014