|
| |
|
|
A277504
|
|
Array read by descending antidiagonals: T(n,k) is the number of unoriented strings with n beads of k or fewer colors.
|
|
33
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,8
|
|
|
COMMENTS
|
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
|
|
|
|
LINKS
|
|
|
|
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 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
|
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Array transposed for greater consistency by Andrew Howroyd, Apr 04 2017
|
|
|
STATUS
|
approved
|
| |
|
|
