OFFSET
1,8
COMMENTS
T(n,n) = 1; T(n,n-1) = 0; T(n,n-2) = n-2;
T(n,n-3) = n-3; T(n,n-4) = (n-4)(n-3)/2; T(n,n-5) = (n-5)^2.
REFERENCES
P. Chinn and S. Heubach, Compositions of n with no occurrence of k, Congressus Numerantium, 164 (2003), pp. 33-51.
R.P. Grimaldi, Compositions without the summand 1, Congressus Numerantium, 152, 2001, 33-43.
LINKS
Alois P. Heinz, Rows n = 1..141, flattened
P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003 (see Table 3).
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3
FORMULA
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).
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
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.
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
EXAMPLE
T(7,4)=4 because we have (4,1,1,1), (1,4,1,1), (1,1,4,1), and (1,1,1,4).
Triangle starts:
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;
MAPLE
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 := 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
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
MATHEMATICA
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 *)
PROG
(Maxima)
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 */
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Aug 15 2010
STATUS
approved