|
%I #26 Oct 28 2018 11:05:52
%S 1,1,0,1,1,0,1,2,2,0,1,3,7,4,0,1,4,15,24,8,0,1,5,26,73,82,16,0,1,6,40,
%T 164,354,280,32,0,1,7,57,310,1031,1716,956,64,0,1,8,77,524,2395,6480,
%U 8318,3264,128,0,1,9,100,819,4803,18501,40728,40320,11144,256,0
%N Number A(n,k) of compositions of n where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%C Also the number of k-compositions of n: matrices with k rows of nonnegative integers with positive column sums and total element sum n.
%C A(2,2) = 7: (matrices and corresponding marked compositions are given)
%C [1 1] [0 0] [1 0] [0 1] [1] [2] [0]
%C [0 0] [1 1] [0 1] [1 0] [1] [0] [2]
%C 1a1a, 1b1b, 1a1b, 1b1a, 2ab, 2aa, 2bb.
%H Alois P. Heinz, <a href="/A261780/b261780.txt">Antidiagonals n = 0..140, flattened</a>
%H E. Grazzini, E. Munarini, M. Poneti, S. Rinaldi, <a href="http://www.mat.unisi.it/newsito/puma/public_html/17_1_2/grazzini.pdf">m-compositions and m-partitions: exhaustive generation and Gray code</a>, Pure Math. Appl. 17 (2006), 111-121.
%H G. Louchard, <a href="http://www.ulb.ac.be/di/mcs/louchard/louchard.papers/compmat.ps">Matrix Compositions: a Probabilistic analysis</a>, Proc. GASCOM'08, Pure Mathematics and Applications, 19, 2-3, 127-146, 2008.
%H E. Munarini, M. Poneti, S. Rinaldi, <a href="http://www.emis.de/journals/JIS/VOL12/Rinaldi/rinaldi.html">Matrix compositions</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.4.8
%F G.f. of column k: (1-x)^k/(2*(1-x)^k-1).
%F A(n,k) = Sum_{i=0..k} C(k,i) * A261781(n,k-i).
%e A(3,2) = 24: 3aaa, 3aab, 3abb, 3bbb, 2aa1a, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 2bb1b, 1a2aa, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1b2bb, 1a1a1a, 1a1a1b, 1a1b1a, 1a1b1b, 1b1a1a, 1b1a1b, 1b1b1a, 1b1b1b.
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 2, 3, 4, 5, 6, ...
%e 0, 2, 7, 15, 26, 40, 57, ...
%e 0, 4, 24, 73, 164, 310, 524, ...
%e 0, 8, 82, 354, 1031, 2395, 4803, ...
%e 0, 16, 280, 1716, 6480, 18501, 44022, ...
%e 0, 32, 956, 8318, 40728, 142920, 403495, ...
%p A:= proc(n, k) option remember; `if`(n=0, 1,
%p add(A(n-j, k)*binomial(j+k-1, k-1), j=1..n))
%p end:
%p seq(seq(A(n, d-n), n=0..d), d=0..12);
%t a[n_, k_] := SeriesCoefficient[(1-x)^k/(2*(1-x)^k-1), {x, 0, n}]; Table[ a[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* _Jean-François Alcover_, Feb 07 2017 *)
%Y Columns k=0-10 give: A000007, A011782, A003480, A145839, A145840, A145841, A161434, A261799, A261800, A261801, A261802.
%Y Rows n=0-2 give: A000012, A001477, A005449.
%Y Main diagonal gives A261783.
%Y Cf. A261718 (same for partitions), A261781.
%K nonn,tabl
%O 0,8
%A _Alois P. Heinz_, Aug 31 2015
|
