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
Examples
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;
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.
Crossrefs
Programs
-
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 -
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)) -
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)])
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).
Comments