A180174 Triangle read by rows of the numbers C(n,k) of k-subsets of a quadratically populated n-multiset M.

1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 3, 5, 7, 9, 10, 10, 10, 10, 10, 9, 7, 5, 3, 1, 1, 4, 9, 16, 25, 35, 45, 55, 65, 75, 84, 91, 96, 99, 100, 100, 100, 99, 96, 91, 84, 75, 65, 55, 45, 35, 25, 16, 9, 4, 1, 1, 5, 14, 30, 55, 90, 135, 190, 255, 330, 414, 505, 601, 700, 800, 900, 1000, 1099

Offset: 0

Author

Thomas Wieder, Aug 15 2010

Keywords

• nonn
• tabf

Comments

The multiplicity m(i) of the i-th element with 1 <= i <= n is m(i)=i^2.

Thus M=[1,2,2,2,2,...,i^2 x i,...,n^2 x n].

Row sum is equal to A028361.

Column for k=2 is equal to AA000096.

Column for k=3 is equal to AA005581.

Column for k=4 is equal to AA005582.

The number of coefficients C(n,k) for given n is equal to A056520.

Examples

			For n=4 one has M=[1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4].
For k=7 we have 55 subsets from M:
[1, 2, 2, 3, 3, 4, 4], [1, 2, 3, 3, 4, 4, 4], [1, 2, 3, 3, 3, 4, 4],
[1, 2, 2, 3, 4, 4, 4], [1, 2, 2, 3, 3, 3, 4], [1, 2, 2, 2, 3, 4, 4],
[1, 2, 2, 2, 3, 3, 4], [2, 2, 3, 3, 4, 4, 4], [2, 2, 3, 3, 3, 4, 4],
[2, 2, 2, 3, 3, 4, 4], [1, 2, 2, 2, 3, 3, 3], [1, 2, 2, 2, 4, 4, 4],
[1, 3, 3, 3, 4, 4, 4], [2, 3, 3, 3, 4, 4, 4], [2, 2, 2, 3, 4, 4, 4],
[2, 2, 2, 3, 3, 3, 4], [1, 2, 3, 4, 4, 4, 4], [1, 2, 3, 3, 3, 3, 4],
[1, 2, 2, 2, 2, 3, 4], [1, 2, 2, 3, 3, 3, 3], [1, 2, 2, 2, 2, 3, 3],
[1, 2, 2, 4, 4, 4, 4], [1, 2, 2, 2, 2, 4, 4], [1, 3, 3, 4, 4, 4, 4],
[1, 3, 3, 3, 3, 4, 4], [2, 3, 3, 4, 4, 4, 4], [2, 3, 3, 3, 3, 4, 4],
[2, 2, 3, 4, 4, 4, 4], [2, 2, 3, 3, 3, 3, 4], [2, 2, 2, 2, 3, 4, 4],
[2, 2, 2, 2, 3, 3, 4], [2, 2, 2, 3, 3, 3, 3], [2, 2, 2, 2, 3, 3, 3],
[2, 2, 2, 4, 4, 4, 4], [2, 2, 2, 2, 4, 4, 4], [3, 3, 3, 4, 4, 4, 4],
[3, 3, 3, 3, 4, 4, 4], [1, 2, 3, 3, 3, 3, 3], [1, 2, 4, 4, 4, 4, 4],
[1, 3, 4, 4, 4, 4, 4], [1, 3, 3, 3, 3, 3, 4], [2, 3, 4, 4, 4, 4, 4],
[2, 3, 3, 3, 3, 3, 4], [2, 2, 3, 3, 3, 3, 3], [2, 2, 4, 4, 4, 4, 4],
[3, 3, 4, 4, 4, 4, 4], [3, 3, 3, 3, 3, 4, 4], [1, 3, 3, 3, 3, 3, 3],
[1, 4, 4, 4, 4, 4, 4], [2, 3, 3, 3, 3, 3, 3], [2, 4, 4, 4, 4, 4, 4],
[3, 4, 4, 4, 4, 4, 4], [3, 3, 3, 3, 3, 3, 4], [3, 3, 3, 3, 3, 3, 3],
[4, 4, 4, 4, 4, 4, 4].
		

Crossrefs

Cf. A007318, A008302, A028361, A056520, A000096, A005581, A005582.

Programs

Maple

with(combinat)
kend := 4;
Liste := NULL;
for k from 0 to kend do
Liste := Liste, `$`(k, k^2)
end do;
Liste := [Liste];
for k from 0 to 2^(kend+1)-1 do
Teilergebnis[k] := choose(Liste, k)
end do;
seq(nops(Teilergebnis[k]), k = 0 .. 2^(kend+1)-1)
' Excel VBA
Sub A180174()
Dim n As Long, nend As Long, k As Long, kk As Long, length_row As Long, length_sum As Long
Dim ATable(10, -1000 To 1000) As Double, Summe As Double
Dim offset_row As Integer, offset_column As Integer
Worksheets("Tabelle2").Select
Cells.Select
Selection.ClearContents
Range("A1").Select
offset_row = 1
offset_column = 1
nend = 7
ATable(0, 0) = 1
Cells(0 + offset_row, 0 + offset_column) = 1
For n = 1 To nend
length_row = n * (n + 1) * (2 * n + 1) / 6
length_sum = n ^ 2 + 1
For k = 0 To length_row / 2
Summe = 0
For kk = k - length_sum + 1 To k
Summe = Summe + ATable(n - 1, kk)
Next kk
ATable(n, k) = Summe
Cells(n + offset_row, k + offset_column) = ATable(n, k)
ATable(n, length_row - k) = Summe
Cells(n + offset_row, length_row - k + 0 + offset_column) = ATable(n, k)
Next k
Next n
End Sub

Formula

C(0,0) = 0.

C(n,k) = sum_{j=(k-LS+1)}^{k} C(n-1,j).

for n > 0 and k=1,...,LR with LS = n^2+1 and LR = n*(n+1)*(2*n+1)/6.

C(n,k) = C(n,LR-k).