login
Three-dimensional array written by antidiagonals in k,n: T(k,n,h) with k >= 1, n >= 0, 0 <= h <= n*(k-1) is the coefficient of x^h in the polynomial (1 + x + ... + x^(k-1))^n = ((x^k-1)/(x-1))^n.
6

%I #74 Mar 21 2024 21:10:53

%S 1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,2,3,2,1,1,3,3,1,1,1,1,1,1,

%T 1,1,1,2,3,4,3,2,1,1,3,6,7,6,3,1,1,4,6,4,1,1,1,1,1,1,1,1,1,1,2,3,4,5,

%U 4,3,2,1,1,3,6,10,12,12,10,6,3,1,1,4,10

%N Three-dimensional array written by antidiagonals in k,n: T(k,n,h) with k >= 1, n >= 0, 0 <= h <= n*(k-1) is the coefficient of x^h in the polynomial (1 + x + ... + x^(k-1))^n = ((x^k-1)/(x-1))^n.

%C Equivalently, T(k,n,h) is the number of ordered sets of n nonnegative integers < k with the sum equal to h.

%C From _Juan Pablo Herrera P._, Nov 21 2016: (Start)

%C T(k,n,h) is the number of possible ways of randomly selecting h cards from k-1 sets, each with n different playing cards. It is also the number of lattice paths from (0,0) to (n,h) using steps (1,0), (1,1), (1,2), ..., (1,k-1).

%C Shallow diagonal sums of each triangle with fixed k give the k-bonacci numbers. (End)

%C T(k,n,h) is the number of n-dimensional grid points of a k X k X ... X k grid, which are lying in the (n-1)-dimensional hyperplane which is at an L1 distance of h from one of the grid's corners, and normal to the corresponding main diagonal of the grid. - _Eitan Y. Levine_, Apr 23 2023

%H Andrey Zabolotskiy, <a href="/A273975/b273975.txt">slices with k+n = 1..20, flattened</a>

%H Florentin Smarandache, <a href="https://arxiv.org/abs/math/0612062">K-Nomial Coefficients</a>, arXiv:math/0612062 [math.GM], 2006 (originally published in French in: F. Smarandache, Généralisations et Généralités, Ed. Nouvelle, 1984, pp. 24-26).

%F T(k,n,h) = Sum_{i = 0..floor(h/k)} (-1)^i*binomial(n,i)*binomial(n+h-1-k*i,n-1). [Corrected by _Eitan Y. Levine_, Apr 23 2023]

%F From _Eitan Y. Levine_, Apr 23 2023: (Start)

%F (T(k,n,h))_{h=0..n*(k-1)} = f(f(...f(g(P))...)), where:

%F (x_i)_{i=0..m} denotes a tuple (in particular, the LHS contains the values for 0 <= h <= n*(k-1)),

%F f repeats n times,

%F f((x_i)_{i=0..m}) = (Sum_{j=0..i} x_j)_{i=0..m} is the cumulative sum function,

%F g((x_i)_{i=0..m}) = (x_(i/k) if k|i, otherwise 0)_{i=0..m*k} is adding k-1 zeros between adjacent elements,

%F and P=((-1)^i*binomial(n,i))_{i=0..n} is the n-th row of Pascal's triangle, with alternating signs. (End)

%F From _Eitan Y. Levine_, Jul 27 2023: (Start)

%F Recurrence relations, the first follows from the sequence's defining polynomial as mentioned in the Smarandache link:

%F T(k,n+1,h) = Sum_{i = 0..s-1} T(k,n,h-i)

%F T(k+1,n,h) = Sum_{i = 0..n} binomial(n,i)*T(k,n-i,h-i*k) (End)

%e For first few k and for first few n, the rows with h = 0..n*(k-1) are given:

%e k=1: 1; 1; 1; 1; 1; ...

%e k=2: 1; 1, 1; 1, 2, 1; 1, 3, 3, 1; 1, 4, 6, 4, 1; ...

%e k=3: 1; 1, 1, 1; 1, 2, 3, 2, 1; 1, 3, 6, 7, 6, 3, 1; ...

%e k=4: 1; 1, 1, 1, 1; 1, 2, 3, 4, 3, 2, 1; ...

%e For example, (1 + x + x^2)^3 = 1 + 3*x + 6*x^2 + 7*x^3 + 6*x^4 + 3*x^5 + x^6, hence T(3,3,2) = T(3,3,4) = 6.

%e From _Eitan Y. Levine_, Apr 23 2023: (Start)

%e Example for the repeated cumulative sum formula, for (k,n)=(3,3) (each line is the cumulative sum of the previous line, and the first line is the padded, alternating 3rd row from Pascal's triangle):

%e 1 0 0 -3 0 0 3 0 0 -1

%e 1 1 1 -2 -2 -2 1 1 1

%e 1 2 3 1 -1 -3 -2 -1

%e 1 3 6 7 6 3 1

%e which is T(3,3,h). (End)

%t a = Table[CoefficientList[Sum[x^(h-1),{h,k}]^n,x],{k,10},{n,0,9}];

%t Flatten@Table[a[[s-n,n+1]],{s,10},{n,0,s-1}]

%t (* alternate program *)

%t row[k_, n_] := Nest[Accumulate,Upsample[Table[((-1)^j)*Binomial[n,j],{j,0,n}],k],n][[;;n*(k-1)+1]] (* _Eitan Y. Levine_, Apr 23 2023 *)

%Y k-nomial arrays for fixed k=1..10: A000012, A007318, A027907, A008287, A035343, A063260, A063265, A171890, A213652, A213651.

%Y Arrays for fixed n=0..6: A000012, A000012, A004737, A109439, A277949, A277950, A277951.

%Y Central n-nomial coefficients for n=1..9, i.e., sequences with h=floor(n*(k-1)/2) and fixed n: A000012, A000984 (A001405), A002426, A005721 (A005190), A005191, A063419 (A018901), A025012, (A025013), A025014, A174061 (A025015), A201549, (A225779), A201550. Arrays: A201552, A077042, see also cfs. therein.

%Y Triangle n=k-1: A181567. Triangle n=k: A163181.

%K nonn,tabf,easy

%O 1,13

%A _Andrey Zabolotskiy_, Nov 10 2016