login
A176572
Count the ones in the binary representation of the partitions of n; then add vertically yielding a triangular array T(n,k).
1
1, 2, 1, 3, 1, 2, 5, 1, 3, 3, 7, 1, 3, 4, 5, 11, 1, 4, 5, 7, 7, 15, 1, 4, 6, 8, 9, 11, 22, 1, 5, 7, 11, 10, 15, 15, 30, 1, 5, 9, 12, 13, 17, 19, 22, 42, 1, 6, 10, 16, 15, 22, 21, 29, 30, 56, 1, 6, 12, 18, 19, 25, 26, 32, 38, 42, 77, 1, 7, 14, 23, 22, 33, 29, 41, 42, 54, 56, 101, 1, 7, 16, 26, 28, 37, 37, 45, 52, 59, 70, 77, 135, 1, 8, 18, 32, 33, 47, 42, 58, 57, 74, 76, 98, 101
OFFSET
1,2
COMMENTS
Each partition of n is converted into a binary representation with n bits by concatenating binary representations of the parts p_1(n)+p_2(n)+p_3(n)+..., p_1(n)>=p_2(n)>=p_3(n),
larger parts contributing the higher significant bits, the individual part p_i(n) represented by a 1 followed by p_i(n)-1 zeros.
These A000041(n) binary representations are stacked, and the total count of 1's in each column is one entry T(n,k).
Together with table A130321, T(n,k) can be used to generate the check sequence
A173871: sum_{k=0..n-1} 2^(n-k)*T(n,k) = A173871(n). For example, multiplying the terms on the fifth row by 16 8 4 2 1
yields
7 1 3 4 5 by 16 8 4 2 1 yielding 112+8+12+8+5 = 145 which is A173871(5).
EXAMPLE
Consider the seven partitions of Five, 5=(10000), 41=(1000)(1), 32=(100)(10), 311=(100)(1)(1), 221=(10)(10)(1), 2111=(10)(1)(1)(1) and 11111=(1)(1)(1)(1)(1),
the corresponding seven concatenated binary representations are
1 0 0 0 0
1 0 0 0 1
1 0 0 1 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 1 1 1
summing by column yields
7 1 3 4 5 the fifth row of the table. The table starts
1;
2,1;
3,1,2;
5,1,3,3;
7,1,3,4,5;
11,1,4,5,7,7;
15,1,4,6,8,9,11;
MAPLE
A176572row := proc(n) L := array(1..n, [seq(0, i=1..n)]) ; for pi in combinat[partition](n) do p := sort(pi) ; p2 := [] ; for i from 1 to nops(p) do p2 := [op(p2), op(convert(2^(op(i, p)-1), base, 2))] ; end do: for i from 1 to n do L[i] := L[i]+ op(n-i+1, p2) ; end do: end do: L ; end proc:
for n from 1 to 14 do A176572row(n) ; print(%) ; end do:
CROSSREFS
KEYWORD
easy,nonn,tabl,base
AUTHOR
Alford Arnold, Apr 22 2010
STATUS
approved