A227578 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one component such that for each point (p_1,p_2,...,p_k) we have p_1<=p_2<=...<=p_k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 4, 1, 1, 1, 14, 29, 8, 1, 1, 1, 42, 290, 185, 16, 1, 1, 1, 132, 3532, 7680, 1257, 32, 1, 1, 1, 429, 49100, 456033, 238636, 8925, 64, 1, 1, 1, 1430, 750325, 34426812, 77767945, 8285506, 65445, 128, 1

Offset: 0

Author

Alois P. Heinz, Jul 16 2013

Keywords

• nonn
• tabl

Comments

Conjecture: column k is asymptotic to c(k) * (k+1)^(k*n)/n^((k^2-1)/2), where c(k) is a constant dependent only on k. - Vaclav Kotesovec, Jul 21 2013

Examples

			A(4,0) = 1: [()].
A(3,1) = 4: [(3),(0)], [(3),(1),(0)], [(3),(2),(0)], [(3),(2),(1),(0)].
A(2,2) = 5: [(2,2),(0,2),(0,0)], [(2,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(0,2),(0,0)], [(2,2),(1,2),(0,2),(0,1),(0,0)], [(2,2),(1,2),(1,1),(0,1),(0,0)].
A(1,3) = 1: [(1,1,1),(0,1,1),(0,0,1),(0,0,0)].
A(0,4) = 1: [(0,0,0,0)].
Square array A(n,k) begins:
  1,  1,    1,      1,        1,           1, ...
  1,  1,    1,      1,        1,           1, ...
  1,  2,    5,     14,       42,         132, ...
  1,  4,   29,    290,     3532,       49100, ...
  1,  8,  185,   7680,   456033,    34426812, ...
  1, 16, 1257, 238636, 77767945, 36470203156, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..25, flattened
• Antonio Vera López, Luis Martínez, Antonio Vera Pérez, Beatriz Vera Pérez and Olga Basova, Combinatorics related to Higman's conjecture I: Parallelogramic digraphs and dispositions, Linear Algebra and its Applications, Volume 530, 1 October 2017, p. 414-444. This entry is mentioned in the Introduction, but it seems that actually they mean A181196.

Crossrefs

Columns k=0-10 give: A000012, A011782, A059231, A227580, A227583, A227596, A227597, A227598, A227599, A227600, A227601.

Rows n=0+1, 2-10 give: A000012, A000108(k+1), A181197(k+2), A227584, A227602, A227603, A227604, A227605, A227606, A227607.

Main diagonal gives: A227579.

Cf. A060854 (steps decrement one component by 1), A262809, A263159.

A181196 is a similar but different array.

Programs

Maple

b:= proc(l) option remember; `if`(l[-1]=0, 1, add(add(b(subsop(
      i=j, l)), j=`if`(i=1, 0, l[i-1])..l[i]-1), i=1..nops(l)))
    end:
A:= (n, k)-> `if`(k=0, 1, b([n$k])):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

b[l_] := b[l] = If[ l[[-1]] == 0, 1, Sum[ Sum[ b[ReplacePart[l, i -> j]], {j, If[i == 1, 0, l[[i-1]]], l[[i]]-1}], {i, 1, Length[l]}]]; a[n_, k_] := If[k == 0, 1, b[Array[n&, k]]]; Table[Table[a[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 09 2013, translated from Maple *)