OFFSET
0,8
COMMENTS
Let f be a function from [n] into [k]. Let C(f) be the weak composition of n, |(f^-1)(1)|, |(f^-1)(2)|, ... , |(f^-1)(k)|. A(n,k) is the number of ordered pairs (f,g) of functions from [n] into [k] such that C(f)=C(g). Also, let P_n be the poset of ordered pairs (S,T) of subsets of [n] such that |S|=|T| ordered by inclusion. A(n,k) is the number of length k multichains from bottom to top in P_n. - Geoffrey Critzer, Jan 10 2026
LINKS
Jeremy Tan, Antidiagonals n = 0..50, flattened
Nikolai Beluhov, Powers of 2 in High-Dimensional Lattice Walks, arXiv:2506.12789 [math.CO], 2025. See p. 19.
Ryan S. Bennink, Counting Abelian Squares for a Problem in Quantum Computing, arXiv:2208.02360 [quant-ph], 2022.
Jonathan M. Borwein, A short walk can be beautiful, preprint, Journal of Humanistic Mathematics, Volume 6 Issue 1 (January 2016), pages 86-109.
Jonathan M. Borwein and Armin Straub, Mahler measures, short walks and log-sine integrals, preprint, Theoretical Computer Science, Volume 479, 1 April 2013, Pages 4-21.
Jonathan M. Borwein, Dirk Nuyens, Armin Straub and James Wan, Some Arithmetic Properties of Short Random Walk Integrals, preprint, FPSAC 2010, San Francisco, USA.
L. Bruce Richmond and Jeffrey Shallit, Counting Abelian Squares, arXiv:0807.5028 [math.CO], 2008.
Armin Straub, Arithmetic aspects of random walks and methods in definite integration, Ph. D. Dissertation, School Of Science And Engineering, Tulane University, 2012.
FORMULA
A(n,k) = A287318(n,k) / binomial(2*n,n).
If a+b=k then A(n,k) = Sum_{i=0..n} A(i,a)*A(n-i,b)*binomial(n,i)^2 (Richmond and Shallit). In particular A(n,k) = Sum_{i=0..n} A(i,k-1)*binomial(n,i)^2. - Jeremy Tan, Dec 10 2021
EXAMPLE
Arrays start:
k\n| 0 1 2 3 4 5 6 7
---|----------------------------------------------------------------
k=0| 1, 0, 0, 0, 0, 0, 0, 0, ... A000007
k=1| 1, 1, 1, 1, 1, 1, 1, 1, ... A000012
k=2| 1, 2, 6, 20, 70, 252, 924, 3432, ... A000984
k=3| 1, 3, 15, 93, 639, 4653, 35169, 272835, ... A002893
k=4| 1, 4, 28, 256, 2716, 31504, 387136, 4951552, ... A002895
k=5| 1, 5, 45, 545, 7885, 127905, 2241225, 41467725, ... A169714
k=6| 1, 6, 66, 996, 18306, 384156, 8848236, 218040696, ... A169715
k=7| 1, 7, 91, 1645, 36715, 948157, 27210169, 844691407, ...
k=8| 1, 8, 120, 2528, 66424, 2039808, 70283424, 2643158400, ... A385286
k=9| 1, 9, 153, 3681, 111321, 3965409, 159700401, 7071121017, ...
MAPLE
A287316_row := proc(k, len) local b, ser;
b := k -> BesselI(0, 2*sqrt(x))^k: ser := series(b(k), x, len);
seq((i!)^2*coeff(ser, x, i), i=0..len-1) end:
for k from 0 to 6 do A287316_row(k, 9) od;
A287316_col := proc(n, len) local k, x;
sum(z^k/k!^2, k = 0..infinity); series(%^x, z=0, n+1):
unapply(n!^2*coeff(%, z, n), x); seq(%(j), j=0..len) end:
for n from 0 to 7 do A287316_col(n, 9) od;
MATHEMATICA
Table[Table[SeriesCoefficient[BesselI[0, 2 Sqrt[x]]^k, {x, 0, n}] (n!)^2, {n, 0, 6}], {k, 0, 9}]
PROG
(PARI)
A287316_row(K, N) = {
my(x='x + O('x^(2*N-1)));
Vec(serlaplace(serlaplace(substpol(besseli(0, 2*x)^K, 'x^2, 'x))));
};
N=8; concat([vector(N, n, n==1)], vector(9, k, A287316_row(k, N))) \\ Gheorghe Coserea, Jan 12 2018
(PARI) {A(n, k) = if(n<0 || k<0, 0, n!^2 * polcoeff(besseli(0, 2*x + x*O(x^(2*n)))^k, 2*n))}; /* Michael Somos, Dec 30 2021 */
(PARI) A(k, n) = my(x='x+O('x^(n+1))); n!^2*polcoeff(hypergeom([], [1], x)^k, n); \\ Peter Luschny, Jun 24 2025
(Python)
from math import comb
from functools import lru_cache
@lru_cache(maxsize=None)
def A(n, k):
if k <= 0: return 0**n
return sum(A(i, k-1)*comb(n, i)**2 for i in range(n+1))
for k in range(10): print([A(n, k) for n in range(8)])
# Jeremy Tan, Dec 10 2021
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, May 23 2017
STATUS
approved
