|
|
A180177
|
|
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
|
|
|
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, 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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
Cf. A097230 (same sequence with rows reversed).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|