%I #64 Oct 06 2024 10:53:24

%S 1,0,0,0,1,0,0,1,1,0,0,1,5,1,0,0,1,13,13,1,0,0,1,29,73,29,1,0,0,1,61,

%T 301,301,61,1,0,0,1,125,1081,2069,1081,125,1,0,0,1,253,3613,11581,

%U 11581,3613,253,1,0,0,1,509,11593,57749,95401,57749,11593,509,1,0

%N Array read by antidiagonals: The number of parades with n girls and k boys that begin with a girl and end with a boy.

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

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

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

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

%H Peter Luschny, <a href="/A371761/b371761.txt">Table of n, a(n) for antidiagonals 0..140</a>.

%H Beáta Bényi, <a href="https://doi.org/10.1007/s00373-021-02442-2">A Bijection for the Boolean Numbers of Ferrers Graphs</a>, Graphs and Combinatorics (2022) Vol. 38, No. 10.

%H Beáta Bényi and Péter Hajnal, <a href="https://arxiv.org/abs/1602.08684">Combinatorial properties of poly-Bernoulli relatives</a>, arXiv preprint arXiv:1602.08684 [math.CO], 2016. See D_{n, k}.

%H Don Knuth, <a href="http://cs.stanford.edu/~knuth/papers/poly-Bernoulli.pdf">Parades and poly-Bernoulli bijections</a>, Mar 31 2024. See (16.2).

%H Brian Parsonnet, <a href="/A136301/a136301.pdf">Probability of Derangements</a>.

%F A(n, k) = k! * [z^k] (n! * [w^n] 1/(exp(w) + exp(z) - exp(w + z))).

%F A(n, k) = k! * [w^k] (Sum_{j=0..n} A075263(n, n - j) * exp(j*w)).

%F A(n, k) = Sum_{j=0..k} (-1)^(j-k) * Stirling2(k + 1, j + 1) * j! * j^n.

%F A(n, k) = Sum_{j=0..min(n,k)} (j!)^2 * Stirling2(n, j) * Stirling2(k, j).

%F A(n, k) = Sum_{j=0..n} (-1)^(n-j)*A028246(n, j) * j^k; this is explicit:

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

%F A(n, k) = Sum_{j=0..k} binomial(k + [j>0], j+1)*A(n-1, k-j) for n > 0.

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

%F Row n (>=1) satisfies a linear recurrence:

%F A(n, k) = -Sum_{j=1..n} Stirling1(n + 1, n + 1 - j)*A(n, k - j) if k > n.

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

%F A(n, k) = A(k, n). (From the symmetry of the bivariate exponential g.f.)

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

%e Array starts:

%e [0] 1, 0, 0, 0, 0, 0, 0, 0, 0, ...

%e [1] 0, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e [2] 0, 1, 5, 13, 29, 61, 125, 253, 509, ...

%e [3] 0, 1, 13, 73, 301, 1081, 3613, 11593, 36301, ...

%e [4] 0, 1, 29, 301, 2069, 11581, 57749, 268381, 1191989, ...

%e [5] 0, 1, 61, 1081, 11581, 95401, 673261, 4306681, 25794781, ...

%e [6] 0, 1, 125, 3613, 57749, 673261, 6487445, 55213453, 431525429, ...

%e [7] 0, 1, 253, 11593, 268381, 4306681, 55213453, 610093513, 6077248381, ...

%e .

%e Seen as triangle T(n, k) = A(n - k, k):

%e [0] 1;

%e [1] 0, 0;

%e [2] 0, 1, 0;

%e [3] 0, 1, 1, 0;

%e [4] 0, 1, 5, 1, 0;

%e [5] 0, 1, 13, 13, 1, 0;

%e [6] 0, 1, 29, 73, 29, 1, 0;

%e [7] 0, 1, 61, 301, 301, 61, 1, 0;

%e .

%e A(n, k) as sum of powers:

%e A(2, k) = -3+ 2*2^k;

%e A(3, k) = 7- 12*2^k+ 6*3^k;

%e A(4, k) = -15+ 50*2^k- 60*3^k+ 24*4^k;

%e A(5, k) = 31- 180*2^k+ 390*3^k- 360*4^k+ 120*5^k;

%e A(6, k) = -63+ 602*2^k- 2100*3^k+ 3360*4^k- 2520*5^k+ 720*6^k;

%e A(7, k) = 127-1932*2^k+10206*3^k-25200*4^k+31920*5^k-20160*6^k+5040*7^k;

%p egf := 1/(exp(w) + exp(z) - exp(w + z)): serw := n -> series(egf, w, n + 1):

%p # Returns row n (>= 0) with length len (> 0):

%p R := n -> len -> local k;

%p seq(k!*coeff(series(n!*coeff(serw(n), w, n), z, len), z, k), k = 0..len - 1):

%p seq(lprint(R(n)(9)), n = 0..7);

%p # Explicit with Stirling2 :

%p 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);

%p # Using the unsigned Worpitzky transform.

%p WT := (a, len) -> local n, k;

%p seq(add((-1)^(n - k)*k!*Stirling2(n + 1, k + 1)*a(k), k=0..n), n = 0..len-1):

%p Arow := n -> WT(x -> x^n, 8): seq(lprint(Arow(n)), n = 0..8);

%p # Two recurrences:

%p A := proc(n, k) option remember; local j; if k = 0 then return k^n fi;

%p add(binomial(n, j)*(A(n-j, k-1) + A(n-j+1, k-1)), j = 1..n) end:

%p A := proc(n, k) option remember; local j; if n = 0 then 0^k else

%p add(binomial(k + `if`(j=0,0,1), j+1)*A(n-1, k-j), j = 0..k) fi end:

%t (* Using the unsigned Worpitzky transform. *)

%t Unprotect[Power]; Power[0, 0] = 1;

%t W[n_, k_] := (-1)^(n - k) k! StirlingS2[n + 1, k + 1];

%t WT[a_, len_] := Table[Sum[W[n, k] a[k], {k, 0, n}], {n, 0, len-1}];

%t A371761row[n_, len_] := WT[#^n &, len];

%t Table[A371761row[n, 9], {n, 0, 8}] // MatrixForm

%t (* Row n >= 1 by linear recurrence: *)

%t RowByLRec[n_, len_] := LinearRecurrence[Table[-StirlingS1[n+1, n+1-k], {k, 1, n}],

%t A371761row[n, n+1], len]; Table[RowByLRec[n, 9], {n, 1, 8}] // MatrixForm

%o (SageMath)

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

%o for n in range(9): print([A371761(n, k) for k in range(8)])

%o (Python)

%o from functools import cache

%o from math import comb as binomial

%o @cache

%o def A(n, k):

%o if n == 0: return int(k == 0)

%o return sum(binomial(k + int(j > 0), j + 1) * A(n - 1, k - j)

%o for j in range(k + 1))

%o for n in range(8): print([A(n, k) for k in range(8)])

%o (Python)

%o # The Akiyama-Tanigawa algorithm for powers generates the rows.

%o def ATPowList(n, len):

%o A = [0] * len

%o R = [0] * len

%o for k in range(len):

%o R[k] = k**n # Changing this to R[k] = (n + 1)**k generates A344499.

%o for j in range(k, 0, -1):

%o R[j - 1] = j * (R[j] - R[j - 1])

%o A[k] = R[0]

%o return A

%o for n in range(8): print([n], ATPowList(n, 9))

%Y Variant: A272644.

%Y Rows include: A344920 (row 2, signed), A006230 (row 3).

%Y Row sums of triangle (n>=2): A297195, alternating row sums: A226158.

%Y Diagonal of array: A048144.

%Y Cf. A004248, A075263, A028246, A173018, A136301, A371762, A136126 (similar), A099594, A344499.

%K nonn,tabl,nice,changed

%O 0,13

%A _Peter Luschny_, Apr 05 2024