|
|
A077042
|
|
Square array read by falling antidiagonals of central polynomial coefficients: largest coefficient in expansion of (1 + x + x^2 + ... + x^(n-1))^k = ((1-x^n)/(1-x))^k, i.e., the coefficient of x^floor(k*(n-1)/2) and of x^ceiling(k*(n-1)/2); also number of compositions of floor(k*(n+1)/2) into exactly k positive integers each no more than n.
|
|
12
|
|
|
1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 3, 3, 1, 1, 0, 1, 6, 7, 4, 1, 1, 0, 1, 10, 19, 12, 5, 1, 1, 0, 1, 20, 51, 44, 19, 6, 1, 1, 0, 1, 35, 141, 155, 85, 27, 7, 1, 1, 0, 1, 70, 393, 580, 381, 146, 37, 8, 1, 1, 0, 1, 126, 1107, 2128, 1751, 780, 231, 48, 9, 1, 1, 0, 1, 252, 3139
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,13
|
|
COMMENTS
|
A pair of numbers written in base n are said to be comparable if all digits of the first number are at least as big as the corresponding digit of the second number, or vice versa. Otherwise, this pair will be defined as uncomparable. A set of pairwise uncomparable integers will be called anti-hierarchic.
T(n,k) is the size of the maximal anti-hierarchic set of integers written with k digits in base n.
For example, for base n=2 and k=4 digits:
- 0 (0000) and 15 (1111) are comparable, while 6 (0110) and 9 (1001) are uncomparable,
- the maximal antihierarchic set is {3 (0011), 5 (0101), 6 (0110), 9 (1001), 10 (1010), 12 (1100)} with 6 elements that are all pairwise uncomparable. (End)
|
|
LINKS
|
|
|
FORMULA
|
By the central limit theorem, T(n,k) is roughly n^(k-1)*sqrt(6/(Pi*k)).
T(n,k) = Sum{j=0,h/n} (-1)^j*binomial(k,j)*binomial(k-1+h-n*j,k-1) with h=floor(k*(n-1)/2), k>0. - Michel Marcus, Dec 01 2012
|
|
EXAMPLE
|
Rows of square array start:
1, 0, 0, 0, 0, 0, 0, ...
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 2, 3, 6, 10, 20, ...
1, 1, 3, 7, 19, 51, 141, ...
1, 1, 4, 12, 44, 155, 580, ...
1, 1, 5, 19, 85, 381, 1751, ...
...
Read by antidiagonals:
1;
0, 1;
0, 1, 1;
0, 1, 1, 1;
0, 1, 2, 1, 1;
0, 1, 3, 3, 1, 1;
0, 1, 6, 7, 4, 1, 1;
...
|
|
MATHEMATICA
|
t[n_, k_] := Max[ CoefficientList[ Series[ ((1-x^n) / (1-x))^k, {x, 0, k*(n-1)}], x]]; t[0, 0] = 1; t[0, _] = 0; Flatten[ Table[ t[n-k, k], {n, 0, 12}, {k, n, 0, -1}]] (* Jean-François Alcover, Nov 04 2011 *)
|
|
PROG
|
(PARI) T(n, k)=if(n<1 || k<1, k==0, vecmax(Vec(((1-x^n)/(1-x))^k)))
|
|
CROSSREFS
|
Rows include A000007, A000012, A001405, A002426, A005190, A005191, A018901, A025012, A025013, A025014, A025015, A201549, A225779, A201550. Columns include A000012, A000012, A001477, A077043, A005900, A077044, A071816, A133458.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|