A344920 -id:A344920 - cp's OEIS frontend

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

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, 301, 301, 61, 1, 0, 0, 1, 125, 1081, 2069, 1081, 125, 1, 0, 0, 1, 253, 3613, 11581, 11581, 3613, 253, 1, 0, 0, 1, 509, 11593, 57749, 95401, 57749, 11593, 509, 1, 0

Offset: 0

Peter Luschny, Apr 05 2024

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

			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;

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.

Variant: A272644.
Rows include: A344920 (row 2, signed), A006230 (row 3).
Row sums of triangle (n>=2): A297195, alternating row sums: A226158.
Diagonal of array: A048144.
Cf. A004248, A075263, A028246, A173018, A136301, A371762, A136126 (similar), A099594, A344499.

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:

(* 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

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)])

# 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))

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)])

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

A371763 Triangle read by rows: Trace of the Akiyama-Tanigawa algorithm for powers x^2.

Original entry on oeis.org

0, 1, 1, 5, 6, 4, 13, 18, 15, 9, 29, 42, 39, 28, 16, 61, 90, 87, 68, 45, 25, 125, 186, 183, 148, 105, 66, 36, 253, 378, 375, 308, 225, 150, 91, 49, 509, 762, 759, 628, 465, 318, 203, 120, 64, 1021, 1530, 1527, 1268, 945, 654, 427, 264, 153, 81

Offset: 0

Peter Luschny, Apr 15 2024

The Akiyama-Tanigawa is a sequence-to-sequence transformation AT := A -> B. If A(n) = 1/(n + 1) then B(n) are the Bernoulli numbers. Tracing the algorithm generates a triangle where the right edge is sequence A and the left edge is its transform B.
Here we consider the sequence A(n) = n^2 that is transformed into sequence B(n) = |A344920(n)|. The case A(n) = n^3 is A371764. Sequence [1, 1, 1, ...] generates A023531 and sequence [0, 1, 2, 3, ...] generates A193738.
In their general form, the AT-transforms of the powers are closely related to the poly-Bernoulli numbers A099594 and generate the rows of the array A371761.

			Triangle starts:
0:                  0
1:               1,   1
2:             5,   6,   4
3:          13,  18,  15,   9
4:        29,  42,  39,  28,  16
5:      61,  90,  87,  68,  45,  25
6:    125, 186, 183, 148, 105,  66, 36
7:  253, 378, 375, 308, 225, 150, 91, 49

Family of triangles: A023531 (n=0), A193738 (n=1), this triangle (n=2), A371764 (n=3).

Cf. A371761, A344920, A099594.

function ATPtriangle(k::Int, len::Int)
    A = Vector{BigInt}(undef, len)
    B = Vector{Vector{BigInt}}(undef, len)
    for n in 0:len-1
        A[n+1] = n^k
        for j = n:-1:1
            A[j] = j * (A[j+1] - A[j])
        end
        B[n+1] = A[1:n+1]
    end
    return B
end
for (n, row) in enumerate(ATPtriangle(2, 9))
    println("$(n-1): ", row)
end

ATProw := proc(k, n) local m, j, A;
   for m from 0 by 1 to n do
      A[m] := m^k;
      for j from m by -1 to 1 do
         A[j - 1] := j * (A[j] - A[j - 1])
   od od; convert(A, list) end:
ATPtriangle := (p, len) -> local k;
     ListTools:-Flatten([seq(ATProw(p, k), k = 0..len)]):
ATPtriangle(2, 9);

T[n,k] := If[n==k, n^2, (k+1)*(2^(n-k)*(k+2)-3)]; Flatten[Table[T[n,k],{n,0,9},{k,0,n}]] (* Detlef Meya, Apr 19 2024 *)

Python
```
# See function ATPowList in A371761.
```

T(n, k) = n^2 if n=k, otherwise (k + 1)*(2^(n - k)*(k + 2) - 3). - Detlef Meya, Apr 19 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

SageMath

Formula

A371763 Triangle read by rows: Trace of the Akiyama-Tanigawa algorithm for powers x^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Julia

Maple

Mathematica

Python

Formula