A213745 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.

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, 462, 1, 7, 28, 84, 210, 462, 924, 1709, 1, 8, 36, 120, 330, 792, 1716, 3424, 6371, 1, 9, 45, 165, 495, 1287, 3003, 6426, 12789, 23905, 1, 10

Offset: 0

Author

Vladimir Shevelev and Peter J. C. Moses, Jun 19 2012

Keywords

• nonn
• tabl

Comments

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

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.

Examples

			Triangle begins
n/k.|..0.....1.....2.....3.....4.....5.....6.....7
==================================================
.0..|..1
.1..|..1.....1
.2..|..1.....2.....3
.3..|..1.....3.....6....10
.4..|..1.....4....10....20....35
.5..|..1.....5....15....35....70....126
.6..|..1.....6....21....56...126....252...462
.7..|..1.....7....28....84...210....462...924....1709
		

Links

• Peter J. C. Moses, Rows n = 0..50 of triangle, flattened

Crossrefs

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

Programs

Mathematica

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 *)

Formula

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

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:

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).

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).

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.