A261718 Number A(n,k) of partitions 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.
1, 1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 3, 7, 3, 0, 1, 4, 15, 18, 5, 0, 1, 5, 26, 55, 50, 7, 0, 1, 6, 40, 124, 216, 118, 11, 0, 1, 7, 57, 235, 631, 729, 301, 15, 0, 1, 8, 77, 398, 1470, 2780, 2621, 684, 22, 0, 1, 9, 100, 623, 2955, 8001, 12954, 8535, 1621, 30, 0
Offset: 0
Examples
A(3,2) = 18: 3aaa, 3aab, 3abb, 3bbb, 2aa1a, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 2bb1b, 1a1a1a, 1a1a1b, 1a1b1a, 1a1b1b, 1b1a1a, 1b1a1b, 1b1b1a, 1b1b1b. Square array A(n,k) begins: 1, 1, 1, 1, 1, 1, 1, 1, ... 0, 1, 2, 3, 4, 5, 6, 7, ... 0, 2, 7, 15, 26, 40, 57, 77, ... 0, 3, 18, 55, 124, 235, 398, 623, ... 0, 5, 50, 216, 631, 1470, 2955, 5355, ... 0, 7, 118, 729, 2780, 8001, 19158, 40299, ... 0, 11, 301, 2621, 12954, 45865, 130453, 317905, ... 0, 15, 684, 8535, 55196, 241870, 820554, 2323483, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
Crossrefs
Programs
-
Maple
b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0, b(n, i-1, k)+`if`(i>n, 0, b(n-i, i, k)*binomial(i+k-1, k-1)))) end: A:= (n, k)-> b(n, n, k): seq(seq(A(n, d-n), n=0..d), d=0..12); -
Mathematica
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1, k] + If[i > n, 0, b[n - i, i, k]*Binomial[i + k - 1, k - 1]]]]; A[n_, k_] := b[n, n, k]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Feb 22 2016, after Alois P. Heinz *)
Formula
A(n,k) = Sum_{i=0..k} C(k,i) * A261719(n,k-i).