|
%I #57 May 03 2020 06:03:28
%S 1,1,2,4,6,11,17,29,47,78,130,215,357,595,990,1651,2748,4584,7643,
%T 12744,21256,35451,59133,98636,164531,274463,457837,763746,1274060,
%U 2125356,3545491,5914545,9866602,16459421,27457549,45804648,76411272,127469285,212644336
%N Number of ordered positive integer solutions (m_1, m_2, ..., m_k) (for some k) to Sum_{i=1..k} m_i=n with |m_i-m_{i-1}| <= 1 for i = 2 ... k.
%C Compositions of n where successive parts differ by at most 1, see example. [_Joerg Arndt_, Dec 10 2012]
%H Alois P. Heinz, <a href="/A034297/b034297.txt">Table of n, a(n) for n = 0..4500</a>
%H Jia Huang, <a href="https://arxiv.org/abs/1812.11010">Compositions with restricted parts</a>, arXiv:1812.11010 [math.CO], 2018.
%F a(n) ~ c * d^n, where d = 1.668202067018461116361070469945501401879811945303435230637248..., c = 0.762436680050402638439806786781869262562176911054246754543346... . - _Vaclav Kotesovec_, Sep 02 2014
%e From _Joerg Arndt_, Dec 10 2012: (Start)
%e The a(6) = 17 such compositions of 6 are
%e [ #] composition
%e [ 1] [ 1 1 1 1 1 1 ]
%e [ 2] [ 1 1 1 1 2 ]
%e [ 3] [ 1 1 1 2 1 ]
%e [ 4] [ 1 1 2 1 1 ]
%e [ 5] [ 1 1 2 2 ]
%e [ 6] [ 1 2 1 1 1 ]
%e [ 7] [ 1 2 1 2 ]
%e [ 8] [ 1 2 2 1 ]
%e [ 9] [ 1 2 3 ]
%e [10] [ 2 1 1 1 1 ]
%e [11] [ 2 1 1 2 ]
%e [12] [ 2 1 2 1 ]
%e [13] [ 2 2 1 1 ]
%e [14] [ 2 2 2 ]
%e [15] [ 3 2 1 ]
%e [16] [ 3 3 ]
%e [17] [ 6 ]
%e (End)
%p b:= proc(n, i) option remember;
%p `if`(n=i, 1, `if`(n<0 or i<1, 0, add(b(n-i, i+j), j=-1..1)))
%p end:
%p a:= n-> add(b(n, k), k=0..n):
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jul 06 2012
%t b[n_, i_] := b[n, i] = If[n == i, 1, If[n<0 || i<1, 0, Sum[b[n-i, i+j], {j, -1, 1}] ]]; a[n_] := Sum[b[n, k], {k, 1, n}]; Array[a, 50] (* _Jean-François Alcover_, Mar 13 2015, after _Alois P. Heinz_ *)
%o (PARI)
%o N=70; nil=-1;
%o T = matrix(N, N, i, j, nil);
%o doIt(last, left) = my(c); c = T[last, left]; if (c == nil, c = 0; for (i = max(1, last - 1), last + 1, c += b(i, left - i)); T[last, left] = c); c;
%o b(last, left) = if (left == 0, return(1)); if (left < 0, return(0)); doIt(last, left);
%o a(n) = sum (i = 1, n, b(i, n - i));
%o vector(N,n,a(n)) \\ _David Wasserman_, Feb 02 2006
%o (Python)
%o from sympy.core.cache import cacheit
%o @cacheit
%o def b(n, i): return 1 if n==i else 0 if n<0 or i<1 else sum(b(n - i, i + j) for j in range(-1, 2))
%o def a(n): return sum(b(n, k) for k in range(n + 1))
%o print([a(n) for n in range(51)]) # _Indranil Ghosh_, Aug 14 2017, after Maple code
%Y Cf. A003116, A034296.
%Y Column k=1 of A214246, A214248.
%Y Row sums of A309939.
%K nonn
%O 0,3
%A _Erich Friedman_
%E More terms from _David Wasserman_, Feb 02 2006
%E a(0)=1 prepended by _Alois P. Heinz_, Aug 14 2017
|
