login
A105552
Irregular triangle T(n,k) read down columns: the number of compositions c of n with largest_part(c)+length(c)=k+1 in row n, column k.
7
1, 2, 4, 1, 7, 5, 2, 11, 14, 12, 5, 1, 16, 30, 39, 32, 18, 7, 2, 22, 55, 95, 113, 101, 71, 41, 18, 6, 1, 29, 91, 195, 299, 357, 350, 292, 207, 126, 64, 27, 9, 2, 37, 140, 357, 664, 978, 1204, 1283, 1198, 992, 731, 482, 284, 148, 66, 25, 7, 1, 46, 204, 602, 1309, 2274, 3329, 4253
OFFSET
1,2
COMMENTS
For each of the A000041(n) partitions of n, one can assign a weight to the partition which counts the permutations of that partition, given by the multinomial coefficient derived from the frequency representation of the parts.
An equivalent representation is given by writing down all compositions of n.
The entries count those partitions multiplied by their weights (=compositions) of n where the sum of the largest addend plus number of parts equals k+1. Only nonzero counts are entered into the sequence.
Each entry can also be interpreted as counting a subset of numbers in A055932, because there is a 1-to-1 correspondence between their prime signature and ordered partitions.
Each diagonal of T(n,k) can be decomposed into p(n) sequences. For example,
A086602 = 2 12 39 95 195 ... is the sum of
A000330 = 1 5 14 30 55 ... plus
A001296 = 1 7 25 65 140 ...
The main diagonal and subdiagonals in order of appearance are A000124, A000330, A086602, A089574, A107600, A107601, A109125, ...
LINKS
FORMULA
Row sums: Sum_{k=0..n} T(n,k) = 2^(n-1).
Column sums: Sum_{n>=k} T(n,k) = A047970(n).
EXAMPLE
The row n=7 starts from the partitions (weights in parentheses) 7 (1), 6+1 (2), 5+2 (2), 4+3 (2), 5+1+1 (3), 4+2+1 (6=3!/1!/1!/1!), 3+3+1 (3), 3+2+2 (3), 4+1+1+1 (4=4!/1!/3!), 3+2+1+1 (12 = 4!/1!/1!/2!), 2+2+2+1 (4), 3+1+1+1+1+1 (5), 2+2+1+1+1 (10=5!/2!/3!), 2+1+1+1+1 (6), 1+1+1+1+1+1 (1).
Then T(7,7) = 1+2+3+4+5+6+1 = 22 is the sum of the weights of partitions with largest part 7 and length 1, largest part 6 and length 2,... largest part 1 and length 7.
T(7,6) = 2+6+12+10 = 30 is the sum of the weights of the partitions with largest part 6 and length 1, largest part 5 and length 2, ..., largest part 1 and length 6.
T(7,5) = 2+3+3+4 = 12 collects all the partitions with largest part 5 and length 1 down to largest part 1 and length 5.
The array has A033638(k) nonzero entries per column, starting at n=1 as :
1
..2
....4
....1..7
.......5..11
.......2..14..16
..........12..30..22
...........5..39..55..29
...........1..32..95..91..37
..............18.113.195.140
...............7.101.299.357
...............2
MAPLE
A033638 := proc(n) ( (7+(-1)^n)/2 + n^2 )/4 ; end proc:
freq := proc(L, n) local a, p; a := 0 ; for p in L do if p = n then a := a+1 ; end if; end do: a ; end proc:
M3 := proc(L) local a, i; a := factorial(nops(L)) ; for i in convert(L, set) do a := a/factorial(freq(L, i)) ; end do: a ; end proc:
A105552 := proc(n, k) local p, a, l ; a := 0 ; for p in combinat[partition](n) do if max(op(p)) + nops(p) = k+1 then a := a+ M3(p); end if; end do ; a ; end proc:
for k from 1 to 15 do for n from k to k+A033638(k)+1 do T := A105552(n, k) ; if T >0 then printf("%d, ", A105552(n, k)) ; end if; end do: printf("\n") ; end do: # R. J. Mathar, Jun 26 2010
# second Maple program:
b:= proc(n, k, p) option remember; `if`(n=0 and k=0, 1,
`if`(k<1, 0, add(b(n-j, k-1-max(p, j)+p, max(p, j)), j=1..n)))
end:
T:= k-> seq(b(n, k+1, 0), n=k..k+floor((k-1)^2/4)):
seq(T(k), k=1..10); # Alois P. Heinz, Jul 24 2013
MATHEMATICA
b[n_, k_, p_] := b[n, k, p] = If[n == 0 && k == 0, 1, If[k < 1, 0, Sum[b[n - j, k - 1 - Max[p, j] + p, Max[p, j]], {j, 1, n}]]]; T[k_] := Table[b[n, k + 1, 0], {n, k, k + Floor[(k - 1)^2/4]}]; Table[T[k], {k, 1, 10}] // Flatten (* Jean-François Alcover, Jan 08 2016, after Alois P. Heinz *)
CROSSREFS
Cf. A047969, A047970, A055932, A057335, A083480, A083906, A089349, A033638, A086602 (subdiagonal), A089574 (subdiagonal).
Sequence in context: A256107 A207610 A207616 * A112852 A121531 A367065
KEYWORD
nonn,tabf
AUTHOR
Alford Arnold, May 03 2005
EXTENSIONS
Definition clarified by R. J. Mathar, Jun 26 2010
STATUS
approved