A344499 -id:A344499 - cp's OEIS frontend

A004248 Array read by ascending antidiagonals: A(n, k) = k^n.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 8, 9, 4, 1, 0, 1, 16, 27, 16, 5, 1, 0, 1, 32, 81, 64, 25, 6, 1, 0, 1, 64, 243, 256, 125, 36, 7, 1, 0, 1, 128, 729, 1024, 625, 216, 49, 8, 1, 0, 1, 256, 2187, 4096, 3125, 1296, 343, 64, 9, 1, 0, 1, 512, 6561, 16384, 15625, 7776, 2401, 512, 81, 10, 1

Offset: 0

David W. Wilson

This array transforms into A371761 using the Akiyama-Tanigawa algorithm for powers applied to the rows. - Peter Luschny, Apr 16 2024

This array transforms into A344499 using the Akiyama-Tanigawa algorithm for powers applied to the columns. - Peter Luschny, Apr 27 2024

			Seen as an array that is read by ascending antidiagonals:
[0] 1, 1,   1,    1,     1,     1,      1,      1,       1, ...
[1] 0, 1,   2,    3,     4,     5,      6,      7,       8, ...
[2] 0, 1,   4,    9,    16,    25,     36,     49,      64, ...
[3] 0, 1,   8,   27,    64,   125,    216,    343,     512, ...
[4] 0, 1,  16,   81,   256,   625,   1296,   2401,    4096, ...
[5] 0, 1,  32,  243,  1024,  3125,   7776,  16807,   32768, ...
[6] 0, 1,  64,  729,  4096, 15625,  46656, 117649,  262144, ...
[7] 0, 1, 128, 2187, 16384, 78125, 279936, 823543, 2097152, ...

T. D. Noe, Rows n=0..50 of triangle, flattened
Michelle Rudolph-Lilith, On the Product Representation of Number Sequences, with Application to the Fibonacci Family, arXiv preprint arXiv:1508.07894 [math.NT], 2015.

For other versions see A051129 and A009998.
Row sums are A026898, diagonal sums are A104872. [Paul Barry, Mar 28 2005]
Cf. A003992, A048723, A371761, A344499.

T[x_, y_] := If[y == 0, 1, (x - y)^y];
Table[T[x, y], {x, 0, 11}, {y, x, 0, -1}] // Flatten (* Jean-François Alcover, Dec 15 2017 *)

T(x, y) = x^y \\ Charles R Greathouse IV, Feb 07 2017

def Arow(n, len): return [k**n for k in range(len)]
for n in range(8): print([n], Arow(n, 9))  # Peter Luschny, Apr 16 2024

Table of x^y, where (x,y) = (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...
As a number triangle, columns have g.f. x^k/(1 - kx). - Paul Barry, Mar 28 2005
From Paul Barry, Jul 13 2005: (Start)
T(n, k) = if(k <= n, k^(n - k), 0).
T(n, k) = Sum_{j=0..floor((n-k)/2)} (-1)^j*C(n-k, j)*C(n-k-j, n-k)*k^(n-k-2j).
(End)

New name by Peter Luschny, Apr 16 2024.

A094416 Array read by antidiagonals: generalized ordered Bell numbers Bo(r,n).

Original entry on oeis.org

1, 2, 3, 3, 10, 13, 4, 21, 74, 75, 5, 36, 219, 730, 541, 6, 55, 484, 3045, 9002, 4683, 7, 78, 905, 8676, 52923, 133210, 47293, 8, 105, 1518, 19855, 194404, 1103781, 2299754, 545835, 9, 136, 2359, 39390, 544505, 5227236, 26857659, 45375130, 7087261

Offset: 1

Ralf Stephan, May 02 2004

Also, r times the number of (r+1)-level labeled linear rooted trees with n leaves.
"AIJ" (ordered, indistinct, labeled) transform of {r,r,r,...}.
Stirling transform of r^n*n!, i.e. of e.g.f. 1/(1-r*x).
Also, Bo(r,s) is ((x*d/dx)^n)(1/(1+r-r*x)) evaluated at x=1.
r-th ordered Bell polynomial (A019538) evaluated at n.
Bo(r,n) is the n-th moment of a geometric distribution with probability parameter = 1/(r+1).  Here, geometric distribution is the number of failures prior to the first success. - Geoffrey Critzer, Jan 01 2019
Row r (starting at r=0), Bo(r+1, n), is the Akiyama-Tanigawa algorithm applied to the powers of r+1. See Python program below. - Shel Kaphan, May 03 2024

			Array begins as:
  1,  3,   13,    75,     541,     4683,      47293, ...
  2, 10,   74,   730,    9002,   133210,    2299754, ...
  3, 21,  219,  3045,   52923,  1103781,   26857659, ...
  4, 36,  484,  8676,  194404,  5227236,  163978084, ...
  5, 55,  905, 19855,  544505, 17919055,  687978905, ...
  6, 78, 1518, 39390, 1277646, 49729758, 2258233998, ...

G. C. Greubel, Antidiagonals n = 1..50, flattened
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
P. Blasiak, K. A. Penson and A. I. Solomon, Dobinski-type relations and the log-normal distribution, arXiv:quant-ph/0303030, 2003.
C. G. Bower, Transforms

Rows 1-10 are A000670, A004123, A032033, A094417, A094418, A094419, A238464, A238465, A238466, A238467.
Columns include A014105, A094421.
Main diagonal is A094420.
Antidiagonal sums are A094422.
Cf. A019538, A131689, A344499.

A094416:= func< n,k | (&+[Factorial(j)*n^j*StirlingSecond(k,j): j in [0..k]]) >;
[A094416(n-k+1,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Jan 12 2024

Bo[, 0]=1; Bo[r, n_]:= Bo[r, n]= r*Sum[Binomial[n,k] Bo[r,n-k], {k, n}];
Table[Bo[r-n+1, n], {r, 10}, {n, r}] // Flatten (* Jean-François Alcover, Nov 03 2018 *)

# The Akiyama-Tanigawa algorithm applied to the powers of r + 1
# generates the rows. Adds one row (r=0) and one column (n=0).
# Adapted from Peter Luschny on A371568.
def f(n, r): return (r + 1)**n
def ATtransform(r, len, f):
  A = [0] * len
  R = [0] * len
  for n in range(len):
      R[n] = f(n, r)
      for j in range(n, 0, -1):
          R[j - 1] = j * (R[j] - R[j - 1])
      A[n] = R[0]
  return A
for r in range(8): print([r], ATtransform(r, 8, f)) # Shel Kaphan, May 03 2024

def A094416(n,k): return sum(factorial(j)*n^j*stirling_number2(k,j) for j in range(k+1)) # array
flatten([[A094416(n-k+1,k) for k in range(1,n+1)] for n in range(1,13)]) # G. C. Greubel, Jan 12 2024

E.g.f.: 1/(1 + r*(1 - exp(x))).
Bo(r, n) = Sum_{k=0..n} k!*r^k*Stirling2(n, k) = 1/(r+1) * Sum_{k>=1} k^n * (r/(r+1))^k, for r>0, n>0.
Recurrence: Bo(r, n) = r * Sum_{k=1..n} C(n, k)*Bo(r, n-k), with Bo(r, 0) = 1.
Bo(r,0) = 1, Bo(r,n) = r*Bo(r,n-1) - (r+1)*Sum_{j=1..n-1} (-1)^j * binomial(n-1,j) * Bo(r,n-j). - Seiichi Manyama, Nov 17 2023

Offset corrected by Geoffrey Critzer, Jan 01 2019

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.

Original entry on oeis.org

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

A094420 Generalized ordered Bell numbers Bo(n,n).

Original entry on oeis.org

1, 1, 10, 219, 8676, 544505, 49729758, 6232661239, 1026912225160, 215270320769109, 55954905981282210, 17662898483917308083, 6655958151527584785900, 2951503248457748982755953, 1521436331153097968932487206, 902143190212525713006814917615, 609729139653483641913607434550800

Offset: 0

Ralf Stephan, May 02 2004

nonn

Main diagonal of array A094416.

Seiichi Manyama, Table of n, a(n) for n = 0..200

Cf. A094416, A321189.
The coefficients of the Fubini polynomials are A131689.
Central column of A344499.

A094420:= func< n | (&+[Factorial(k)*n^k*StirlingSecond(n,k): k in [0..n]]) >;
[A094420(n): n in [0..25]]; // G. C. Greubel, Jan 12 2024

F := proc(n) option remember; if n = 0 then return 1 fi;
expand(add(binomial(n, k)*F(n-k)*x, k=1..n)) end:
a := n -> subs(x = n, F(n)):
seq(a(n), n = 0..16); # Peter Luschny, May 21 2021

Table[Sum[k!*n^k*StirlingS2[n, k], {k, 0, n}], {n, 1, 20}] (* Vaclav Kotesovec, Jul 23 2018 *)

{a(n) = sum(k=0, n, k!*n^k*stirling(n, k, 2))} \\ Seiichi Manyama, Jun 12 2020

def aList(len):
    R. = PowerSeriesRing(QQ)
    f = lambda n: R(1/(1 + n * (1 - exp(x))))
    return [factorial(n)*f(n).list()[n] for n in (0..len-1)]
print(aList(17)) # Peter Luschny, May 21 2021

a(n) ~ sqrt(2*Pi) * n^(2*n + 5/2) / exp(n - 3/2). - Vaclav Kotesovec, Jul 23 2018
a(n) = Sum_{k=0..n} k!*n^k*Stirling2(n, k). - Seiichi Manyama, Jun 12 2020
From Peter Luschny, May 21 2021: (Start)
a(n) = F_{n}(n), the Fubini polynomial F_{n}(x) evaluated at x = n.
a(n) = n! * [x^n] (1 / (1 + n * (1 - exp(x)))).  (End)

More terms from Seiichi Manyama, Jun 12 2020

cp's OEIS Frontend

A372346 a(n) = Sum_{j=0..n} p(n - j, j) where p(n, x) = Sum_{k=0..n} k! * Stirling2(n, k) * x^k. Row sums of A344499.

Views

Author

Keywords

Crossrefs

Programs

Maple

Formula

A004248 Array read by ascending antidiagonals: A(n, k) = k^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

Extensions

A094416 Array read by antidiagonals: generalized ordered Bell numbers Bo(r,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Python

SageMath

Formula

Extensions

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

A094420 Generalized ordered Bell numbers Bo(n,n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions