login
Triangle read by rows: T(n,k) is the number of compositions of n without 2's and having k parts; 1<=k<=n.
11

%I #44 Jul 03 2020 14:55:05

%S 1,0,1,1,0,1,1,2,0,1,1,2,3,0,1,1,3,3,4,0,1,1,4,6,4,5,0,1,1,5,9,10,5,6,

%T 0,1,1,6,13,16,15,6,7,0,1,1,7,18,26,25,21,7,8,0,1,1,8,24,40,45,36,28,

%U 8,9,0,1,1,9,31,59,75,71,49,36,9,10,0,1,1,10,39,84,120,126,105,64,45,10,11,0,1

%N Triangle read by rows: T(n,k) is the number of compositions of n without 2's and having k parts; 1<=k<=n.

%C T(n,n) = 1; T(n,n-1) = 0; T(n,n-2) = n-2;

%C T(n,n-3) = n-3; T(n,n-4) = (n-4)(n-3)/2; T(n,n-5) = (n-5)^2.

%D P. Chinn and S. Heubach, Compositions of n with no occurrence of k, Congressus Numerantium, 164 (2003), pp. 33-51.

%D R.P. Grimaldi, Compositions without the summand 1, Congressus Numerantium, 152, 2001, 33-43.

%H Alois P. Heinz, <a href="/A180177/b180177.txt">Rows n = 1..141, flattened</a>

%H P. Chinn and S. Heubach, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL6/Heubach/heubach5.html">Integer Sequences Related to Compositions without 2's</a>, J. Integer Seqs., Vol. 6, 2003 (see Table 3).

%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html">Binomial Coefficients and Enumeration of Restricted Words</a>, Journal of Integer Sequences, 2016, Vol 19, #16.7.3

%F Number of compositions of n without p's and having k parts = Sum((-1)^{k-j} *binomial(k,j) *binomial(n-pk+pj-1,j-1), j=floor((pk-n)/(p-1))..k), (n>=p+1).

%F For n<p+1, the number of compositions of n is binomial(n-1,k-1), except in the case of compositions of p into 1 part, which number equals 0. - _Milan Janjic_, Aug 06 2015

%F For a given p, the g.f. of the number of compositions without p's is G(t,z)=tg(z)/[1-tg(z)], where g(z)=z/(1-z)-z^p; here z marks sum of parts and t marks number of parts.

%F G.f.: [(x-x^2+x^3)/(1-x)]^k=sum{n>0, T(n,k)*x^n}, T(n,k)=T(n-1,k)+T(n-1,k-1)-T(n-2,k-1)+T(n-3,k-1). - _Vladimir Kruchinin_, Sep 29 2014

%e T(7,4)=4 because we have (4,1,1,1), (1,4,1,1), (1,1,4,1), and (1,1,1,4).

%e Triangle starts:

%e 1;

%e 0,1;

%e 1,0,1;

%e 1,2,0,1;

%e 1,2,3,0,1;

%e 1,3,3,4,0,1;

%e 1,4,6,4,5,0,1;

%p p:= 2: T := proc (n, k) options operator, arrow: sum((-1)^(k-j)*binomial(k, j)*binomial(n-p*k+p*j-1, j-1), j = (p*k-n)/(p-1) .. k) end proc: for n to 13 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

%p p := 2: g := z/(1-z)-z^p: G := t*g/(1-t*g): Gser := simplify(series(G, z = 0, 15)): for n to 13 do P[n] := sort(coeff(Gser, z, n)) end do: for n to 13 do seq(coeff(P[n], t, k), k = 1 .. n) end do; # yields sequence in triangular form

%p with(combinat): m := 2: T := proc (n, k) local ct, i: ct := 0: for i to numbcomp(n, k) do if member(m, composition(n, k)[i]) = false then ct := ct+1 else end if end do: ct end proc: for n to 13 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

%t p = 2; max = 14; g = z/(1-z) - z^p; G = t*g/(1-t*g); Gser = Series[G, {z, 0, max+1}]; t[n_, k_] := SeriesCoefficient[Gser, {z, 0, n}, {t, 0, k}]; Table[t[n, k], {n, 1, max}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Jan 28 2014, after Maple *)

%o (Maxima)

%o T(n,k):=if n<0 then 0 else if n=k then 1 else if k=0 then 0 else T(n-1,k)+T(n-1,k-1)-T(n-2,k-1)+T(n-3,k-1); /* _Vladimir Kruchinin_, Sep 23 2014 */

%Y Cf. A011973, A180178, A180179, A180180, A180181, A180182, A180183.

%Y Cf. A097230 (same sequence with rows reversed).

%K nonn,tabl

%O 1,8

%A _Emeric Deutsch_, Aug 15 2010