login
Triangle of numbers C^(6)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 6 appearances allowed.
4

%I #22 Apr 24 2013 12:24:55

%S 1,1,1,1,2,3,1,3,6,10,1,4,10,20,35,1,5,15,35,70,126,1,6,21,56,126,252,

%T 462,1,7,28,84,210,462,924,1709,1,8,36,120,330,792,1716,3424,6371,1,9,

%U 45,165,495,1287,3003,6426,12789,23905,1,10

%N Triangle of numbers C^(6)(n,k) of combinations with repetitions from n different elements over k for each of them not more than 6 appearances allowed.

%C For k<=5, the triangle coincides with triangle A213744.

%C We have over columns of the triangle: T(n,0)=1, T(n,1)=n, T(n,2)=A000217(n) for n>1, T(n,3)=A000292(n) for n>=3, T(n,4)=A000332(n) for n>=7, T(n,5)=A000389(n) for n>=9, T(n,6)=A000579(n) for n>=11, T(n,7)=A063267 for n>=5, T(n,8)=A063417 for n>=6, T(n,9)=A063418 for n>=7.

%H Peter J. C. Moses, <a href="/A213745/b213745.txt">Rows n = 0..50 of triangle, flattened</a>

%F C^(6)(n,k)=sum{r=0,...,floor(k/7)}(-1)^r*C(n,r)*C(n-7*r+k-1, n-1).

%F A generalization. The numbers C^(t)(n,k) of combinations with repetitions from n different elements over k, for each of them not more than t>=1 appearances allowed, are enumerated by the formula:

%F C^(t)(n,k)=sum{r=0,...,floor(k/(t+1))}(-1)^r*C(n,r)*C(n-(t+1)*r+k-1, n-1).

%F In case t=1, it is binomial coefficient C^(t)(n,k)=C(n,k), and we have the combinatorial identity: sum{r=0,...,floor(k/2)}(-1)^r*C(n,r)*C(n-2*r+k-1, n-1)=C(n,k). On the other hand, if t=n, then r=0, and for the corresponding numbers of combinations with repetitions without a restriction on appearances of elements we obtain a well known formula C(n+k-1, n-1) (cf. triangle A059481).

%F In addition, note that, if k<=t, then C^(t)(n,k)=C(n+k-1, n-1). Therefore, triangle {C^(t+1)(n,k)} coincides with the previous triangle {C^(t)(n,k)} for k<=t.

%e Triangle begins

%e n/k.|..0.....1.....2.....3.....4.....5.....6.....7

%e ==================================================

%e .0..|..1

%e .1..|..1.....1

%e .2..|..1.....2.....3

%e .3..|..1.....3.....6....10

%e .4..|..1.....4....10....20....35

%e .5..|..1.....5....15....35....70....126

%e .6..|..1.....6....21....56...126....252...462

%e .7..|..1.....7....28....84...210....462...924....1709

%t Flatten[Table[Sum[(-1)^r Binomial[n,r] Binomial[n-# r+k-1,n-1],{r,0,Floor[k/#]}],{n,0,15},{k,0,n}]/.{0}->{1}]&[7] (* _Peter J. C. Moses_, Apr 16 2013 *)

%Y Cf. A007318, A005725, A059481, A111808, A187925, A213742, A213743, A213744, A000217, A000292, A000332, A000389, A000579, A063267, A063417, A063418.

%K nonn,tabl

%O 0,5

%A _Vladimir Shevelev_ and _Peter J. C. Moses_, Jun 19 2012