A277504 Array read by descending antidiagonals: T(n,k) is the number of unoriented strings with n beads of k or fewer colors.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 6, 6, 1, 0, 1, 5, 10, 18, 10, 1, 0, 1, 6, 15, 40, 45, 20, 1, 0, 1, 7, 21, 75, 136, 135, 36, 1, 0, 1, 8, 28, 126, 325, 544, 378, 72, 1, 0, 1, 9, 36, 196, 666, 1625, 2080, 1134, 136, 1, 0, 1, 10, 45, 288, 1225, 3996, 7875, 8320, 3321, 272, 1, 0

Offset

0,8

Comments

From Petros Hadjicostas, Jul 07 2018: (Start)

Column k of this array is the "BIK" (reversible, indistinct, unlabeled) transform of k,0,0,0,....

Consider the input sequence (c_k(n): n >= 1) with g.f. C_k(x) = Sum_{n>=1} c_k(n)*x^n. Let a_k(n) = BIK(c_k(n): n >= 1) be the output sequence under Bower's BIK transform. It can proved that the g.f. of BIK(c_k(n): n >= 1) is A_k(x) = (1/2)*(C_k(x)/(1-C_k(x)) + (C_k(x^2) + C_k(x))/(1-C_k(x^2))). (See the comments for sequence A001224.)

For column k of this two-dimensional array, the input sequence is defined by c_k(1) = k and c_k(n) = 0 for n >= 1. Thus, C_k(x) = k*x, and hence the g.f. of column k is (1/2)*(C_k(x)/(1-C_k(x)) + (C_k(x^2) + C_k(x))/(1-C_k(x^2))) = (1/2)*(k*x/(1-k*x) + (k*x^2 + k*x)/(1-k*x^2)) = (2 + (1-k)*x - 2*k*x^2)*k*x/(2*(1-k*x^2)*(1-k*x)).

Using the first form the g.f. above and the expansion 1/(1-y) = 1 + y + y^2 + ..., we can easily prove J.-F. Alcover's formula T(n,k) = (k^n + k^((n + mod(n,2))/2))/2.

(End)

References

See A005418.

Links

Robert A. Russell, Antidiagonals n=0..52, flattened (antidiagonals 1..50 from Andrew Howroyd)

C. G. Bower, Transforms (2)

Formula

T(n,k) = [n==0] + [n>0] * (k^n + k^ceiling(n/2)) / 2. [Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018]

G.f. for column k: (1 - binomial(k+1,2)*x^2) / ((1-k*x)*(1-k*x^2)). - Petros Hadjicostas, Jul 07 2018 [Adapted to T(0,k)=1 by Robert A. Russell, Nov 13 2018]

From Robert A. Russell, Nov 13 2018: (Start)

T(n,k) = (A003992(k,n) + A321391(n,k)) / 2.

T(n,k) = A003992(k,n) - A293500(n,k) = A293500(n,k) + A321391(n,k).

G.f. for row n: (Sum_{j=0..n} S2(n,j)*j!*x^j/(1-x)^(j+1) + Sum_{j=0..ceiling(n/2)} S2(ceiling(n/2),j)*j!*x^j/(1-x)^(j+1)) / 2, where S2 is the Stirling subset number A008277.

G.f. for row n>0: x*Sum_{k=0..n-1} A145882(n,k) * x^k / (1-x)^(n+1).

E.g.f. for row n: (Sum_{k=0..n} S2(n,k)*x^k + Sum_{k=0..ceiling(n/2)} S2(ceiling(n/2),k)*x^k) * exp(x) / 2, where S2 is the Stirling subset number A008277.

T(0,k) = 1; T(1,k) = k; T(2,k) = binomial(k+1,2); for n>2, T(n,k) = k*(T(n-3,k)+T(n-2,k)-k*T(n-1,k)).

For k>n, T(n,k) = Sum_{j=1..n+1} -binomial(j-n-2,j) * T(n,k-j). (End)

Example

Array begins with T(0,0):
1 1   1     1      1       1        1         1         1          1 ...
0 1   2     3      4       5        6         7         8          9 ...
0 1   3     6     10      15       21        28        36         45 ...
0 1   6    18     40      75      126       196       288        405 ...
0 1  10    45    136     325      666      1225      2080       3321 ...
0 1  20   135    544    1625     3996      8575     16640      29889 ...
0 1  36   378   2080    7875    23436     58996    131328     266085 ...
0 1  72  1134   8320   39375   140616    412972   1050624    2394765 ...
0 1 136  3321  32896  195625   840456   2883601   8390656   21526641 ...
0 1 272  9963 131584  978125  5042736  20185207  67125248  193739769 ...
0 1 528 29646 524800 4884375 30236976 141246028 536887296 1743421725 ...
...

Mathematica

Table[If[n>0, ((n-k)^k + (n-k)^Ceiling[k/2])/2, 1], {n, 0, 15}, {k, 0, n}] // Flatten (* updated Jul 10 2018 *) (* Adapted to T(0, k)=1 by Robert A. Russell, Nov 13 2018 *)

Prog

(PARI) for(n=0, 15, for(k=0, n, print1(if(n==0, 1, ((n-k)^k + (n-k)^ceil(k/2))/2), ", "))) \\ G. C. Greubel, Nov 15 2018
(PARI) T(n, k) = {(k^n + k^ceil(n/2)) / 2} \\ Andrew Howroyd, Sep 13 2019
(Magma) [[n le 0 select 1 else ((n-k)^k + (n-k)^Ceiling(k/2))/2: k in [0..n]]: n in [0..15]]; // G. C. Greubel, Nov 15 2018

Crossrefs

Columns 0-6 are A000007, A000012, A005418(n+1), A032120, A032121, A032122, A056308.

Rows 0-20 are A000012, A001477, A000217 (triangular numbers), A002411 (pentagonal pyramidal numbers), A037270, A168178, A071232, A168194, A071231, A168372, A071236, A168627, A071235, A168663, A168664, A170779, A170780, A170790, A170791, A170801, A170802.

Main diagonal is A275549.

Transpose is A284979.

Cf. A284871, A284949.

Cf. A003992 (oriented), A293500 (chiral), A321391 (achiral).

Sequence in context: A339779 A373449 A373424 * A167763 A277666 A274581

Adjacent sequences: A277501 A277502 A277503 * A277505 A277506 A277507

Keyword

nonn,tabl,easy

Author

Jean-François Alcover, Oct 18 2016

Extensions

Array transposed for greater consistency by Andrew Howroyd, Apr 04 2017

Origin changed to T(0,0) by Robert A. Russell, Nov 13 2018

Status

approved