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

%I #52 Sep 08 2022 08:46:17

%S 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,

%T 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,

%U 36,196,666,1625,2080,1134,136,1,0,1,10,45,288,1225,3996,7875,8320,3321,272,1,0

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

%C From _Petros Hadjicostas_, Jul 07 2018: (Start)

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

%C 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.)

%C 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)).

%C 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.

%C (End)

%D See A005418.

%H Robert A. Russell, <a href="/A277504/b277504.txt">Antidiagonals n=0..52, flattened </a> (antidiagonals 1..50 from Andrew Howroyd)

%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>

%F 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]

%F 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]

%F From _Robert A. Russell_, Nov 13 2018: (Start)

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

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

%F 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.

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

%F 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.

%F 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)).

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

%e Array begins with T(0,0):

%e 1 1 1 1 1 1 1 1 1 1 ...

%e 0 1 2 3 4 5 6 7 8 9 ...

%e 0 1 3 6 10 15 21 28 36 45 ...

%e 0 1 6 18 40 75 126 196 288 405 ...

%e 0 1 10 45 136 325 666 1225 2080 3321 ...

%e 0 1 20 135 544 1625 3996 8575 16640 29889 ...

%e 0 1 36 378 2080 7875 23436 58996 131328 266085 ...

%e 0 1 72 1134 8320 39375 140616 412972 1050624 2394765 ...

%e 0 1 136 3321 32896 195625 840456 2883601 8390656 21526641 ...

%e 0 1 272 9963 131584 978125 5042736 20185207 67125248 193739769 ...

%e 0 1 528 29646 524800 4884375 30236976 141246028 536887296 1743421725 ...

%e ...

%t 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 *)

%o (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

%o (PARI) T(n,k) = {(k^n + k^ceil(n/2)) / 2} \\ _Andrew Howroyd_, Sep 13 2019

%o (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

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

%Y 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.

%Y Main diagonal is A275549.

%Y Transpose is A284979.

%Y Cf. A284871, A284949.

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

%K nonn,tabl,easy

%O 0,8

%A _Jean-François Alcover_, Oct 18 2016

%E Array transposed for greater consistency by _Andrew Howroyd_, Apr 04 2017

%E Origin changed to T(0,0) by _Robert A. Russell_, Nov 13 2018