OFFSET
0,13
COMMENTS
The name derives from a proposition by Donald Knuth, who describes the setup of a "girls and boys parade" as follows: "There are m girls {g_1, ..., g_m} and n boys {b_1, ..., b_n}, where g_i is younger than g_{i+1} and b_j is younger than b_{j+1}, but we know nothing about the relative ages of g_i and b_j. In how many ways can they all line up in a sequence such that no girl is directly preceded by an older girl and no boy is directly preceded by an older boy?" [Our notation: A <- D, n <- m, k <- n].
In A344920, the Worpitzky transform is defined as a sequence-to-sequence transformation WT := A -> B, where B(n) = Sum_{k=0..n} A163626(n, k)*A(k). (If A(n) = 1/(n + 1) then B(n) are the Bernoulli numbers (with B(1) = 1/2.)) The rows of the array are the Worpitzky transforms of the powers up to the sign (-1)^k.
The array rows are recursively generated by applying the Akiyama-Tanigawa algorithm to the powers (see the Python implementation below). In this way the array becomes the image of A004248 under the AT-transformation when applied to the rows of A004248. This makes the array closely linked to A344499, which is generated in the same way, but applied to the columns of A004248.
Conjecture: Row n + 1 is row 2^n in table A136301, where a probabilistic interpretation is given (see the link to Parsonnet's paper below).
LINKS
Peter Luschny, Table of n, a(n) for antidiagonals 0..140.
Beáta Bényi, A Bijection for the Boolean Numbers of Ferrers Graphs, Graphs and Combinatorics (2022) Vol. 38, No. 10.
Beáta Bényi and Péter Hajnal, Combinatorial properties of poly-Bernoulli relatives, arXiv preprint arXiv:1602.08684 [math.CO], 2016. See D_{n, k}.
Don Knuth, Parades and poly-Bernoulli bijections, Mar 31 2024. See (16.2).
Brian Parsonnet, Probability of Derangements.
FORMULA
A(n, k) = k! * [z^k] (n! * [w^n] 1/(exp(w) + exp(z) - exp(w + z))).
A(n, k) = k! * [w^k] (Sum_{j=0..n} A075263(n, n - j) * exp(j*w)).
A(n, k) = Sum_{j=0..k} (-1)^(j-k) * Stirling2(k + 1, j + 1) * j! * j^n.
A(n, k) = Sum_{j=0..min(n,k)} (j!)^2 * Stirling2(n, j) * Stirling2(k, j).
A(n, k) = Sum_{j=0..n} (-1)^(n-j)*A028246(n, j) * j^k; this is explicit:
A(n, k) = Sum_{j=0..n} Sum_{m=0..n} binomial(n-m, n-j) * Eulerian1(n, m) * j^k *(-1)^(n-j), where Eulerian1 = A173018.
A(n, k) = Sum_{j=0..k} binomial(k + [j>0], j+1)*A(n-1, k-j) for n > 0.
A(n, k) = Sum_{j=1..n} binomial(n, j)*(A(n-j, k-1) + A(n-j+1, k-1)) for n,k >= 1.
Row n (>=1) satisfies a linear recurrence:
A(n, k) = -Sum_{j=1..n} Stirling1(n + 1, n + 1 - j)*A(n, k - j) if k > n.
A(n, k) = [x^k] (Sum_{j=0..n} A371762(n, j)*x^j) / (Sum_{j=0..n} Stirling1(n + 1, n + 1 - j)*x^j).
A(n, k) = A(k, n). (From the symmetry of the bivariate exponential g.f.)
Let T(n, k) = A(n - k, k) and G(n) = Sum_{k=0..n} (-1)^k*T(n, k) the alternating row sums of the triangle. Then G(n) = (n + 2)*Euler(n + 1, 1) and as shifted Genocchi numbers G(n) = -2*(n + 2)*PolyLog(-n - 1, -1) = -A226158(n + 2).
EXAMPLE
Array starts:
[0] 1, 0, 0, 0, 0, 0, 0, 0, 0, ...
[1] 0, 1, 1, 1, 1, 1, 1, 1, 1, ...
[2] 0, 1, 5, 13, 29, 61, 125, 253, 509, ...
[3] 0, 1, 13, 73, 301, 1081, 3613, 11593, 36301, ...
[4] 0, 1, 29, 301, 2069, 11581, 57749, 268381, 1191989, ...
[5] 0, 1, 61, 1081, 11581, 95401, 673261, 4306681, 25794781, ...
[6] 0, 1, 125, 3613, 57749, 673261, 6487445, 55213453, 431525429, ...
[7] 0, 1, 253, 11593, 268381, 4306681, 55213453, 610093513, 6077248381, ...
.
Seen as triangle T(n, k) = A(n - k, k):
[0] 1;
[1] 0, 0;
[2] 0, 1, 0;
[3] 0, 1, 1, 0;
[4] 0, 1, 5, 1, 0;
[5] 0, 1, 13, 13, 1, 0;
[6] 0, 1, 29, 73, 29, 1, 0;
[7] 0, 1, 61, 301, 301, 61, 1, 0;
.
A(n, k) as sum of powers:
A(2, k) = -3+ 2*2^k;
A(3, k) = 7- 12*2^k+ 6*3^k;
A(4, k) = -15+ 50*2^k- 60*3^k+ 24*4^k;
A(5, k) = 31- 180*2^k+ 390*3^k- 360*4^k+ 120*5^k;
A(6, k) = -63+ 602*2^k- 2100*3^k+ 3360*4^k- 2520*5^k+ 720*6^k;
A(7, k) = 127-1932*2^k+10206*3^k-25200*4^k+31920*5^k-20160*6^k+5040*7^k;
MAPLE
egf := 1/(exp(w) + exp(z) - exp(w + z)): serw := n -> series(egf, w, n + 1):
# Returns row n (>= 0) with length len (> 0):
R := n -> len -> local k;
seq(k!*coeff(series(n!*coeff(serw(n), w, n), z, len), z, k), k = 0..len - 1):
seq(lprint(R(n)(9)), n = 0..7);
# Explicit with Stirling2 :
A := (n, k) -> local j; add(j!^2*Stirling2(n, j)*Stirling2(k, j), j = 0..min(n, k)): seq(lprint(seq(A(n, k), k = 0..8)), n = 0..7);
# Using the unsigned Worpitzky transform.
WT := (a, len) -> local n, k;
seq(add((-1)^(n - k)*k!*Stirling2(n + 1, k + 1)*a(k), k=0..n), n = 0..len-1):
Arow := n -> WT(x -> x^n, 8): seq(lprint(Arow(n)), n = 0..8);
# Two recurrences:
A := proc(n, k) option remember; local j; if k = 0 then return k^n fi;
add(binomial(n, j)*(A(n-j, k-1) + A(n-j+1, k-1)), j = 1..n) end:
A := proc(n, k) option remember; local j; if n = 0 then 0^k else
add(binomial(k + `if`(j=0, 0, 1), j+1)*A(n-1, k-j), j = 0..k) fi end:
MATHEMATICA
(* Using the unsigned Worpitzky transform. *)
Unprotect[Power]; Power[0, 0] = 1;
W[n_, k_] := (-1)^(n - k) k! StirlingS2[n + 1, k + 1];
WT[a_, len_] := Table[Sum[W[n, k] a[k], {k, 0, n}], {n, 0, len-1}];
A371761row[n_, len_] := WT[#^n &, len];
Table[A371761row[n, 9], {n, 0, 8}] // MatrixForm
(* Row n >= 1 by linear recurrence: *)
RowByLRec[n_, len_] := LinearRecurrence[Table[-StirlingS1[n+1, n+1-k], {k, 1, n}],
A371761row[n, n+1], len]; Table[RowByLRec[n, 9], {n, 1, 8}] // MatrixForm
PROG
(SageMath)
def A371761(n, k): return sum((-1)^(j - k) * factorial(j) * stirling_number2(k + 1, j + 1) * j^n for j in range(k + 1))
for n in range(9): print([A371761(n, k) for k in range(8)])
(Python)
from functools import cache
from math import comb as binomial
@cache
def A(n, k):
if n == 0: return int(k == 0)
return sum(binomial(k + int(j > 0), j + 1) * A(n - 1, k - j)
for j in range(k + 1))
for n in range(8): print([A(n, k) for k in range(8)])
(Python)
# The Akiyama-Tanigawa algorithm for powers generates the rows.
def ATPowList(n, len):
A = [0] * len
R = [0] * len
for k in range(len):
R[k] = k**n # Changing this to R[k] = (n + 1)**k generates A344499.
for j in range(k, 0, -1):
R[j - 1] = j * (R[j] - R[j - 1])
A[k] = R[0]
return A
for n in range(8): print([n], ATPowList(n, 9))
CROSSREFS
KEYWORD
AUTHOR
Peter Luschny, Apr 05 2024
STATUS
approved