cp's OEIS Frontend

A099594 Array read by antidiagonals: poly-Bernoulli numbers B(-k,n).

%I A099594 #155 Apr 02 2025 04:15:22
%S A099594 1,1,1,1,2,1,1,4,4,1,1,8,14,8,1,1,16,46,46,16,1,1,32,146,230,146,32,1,
%T A099594 1,64,454,1066,1066,454,64,1,1,128,1394,4718,6902,4718,1394,128,1,1,
%U A099594 256,4246,20266,41506,41506,20266,4246,256,1,1,512,12866,85310,237686,329462,237686,85310,12866,512,1
%N A099594 Array read by antidiagonals: poly-Bernoulli numbers B(-k,n).
%C A099594 B_n^{(-k)} is the number of distinct n by k "lonesum matrices" where a matrix of entries 0 or 1 is called lonesum when it is uniquely reconstructible from its row and column sums. [Brewbaker]
%C A099594 B_n^{(-k)} is the cardinality of the set { sigma in S_{n+k}: -k <= i-sigma(i) <= n for all i=1,2,...,n+k }. [Launois]
%C A099594 T(n,k) is also the number of permutations on [n+k] in which each substring whose support belongs to {1, 2, ..., n} or {n+1, n+2, ..., n+k} is increasing. For example, with n = 2 and k = 3, the permutation 41532 does not qualify because the substring 53 has support in {n+1, n+2, ..., n+k} = {3,4,5} but is not increasing. T(2,1) = 4 counts 123, 132, 231, 312 while the permutations satisfying Launois' condition above are 123, 132, 213, 231. A bijection between these sets of permutations would be interesting. - _David Callan_, Jul 22 2008. (Corrected by Norman Do, Sep 01 2008)
%C A099594 T(n,k) is also the number of acyclic orientations of the complete bipartite graph K_{n,k}. - _Vincent Pilaud_, Sep 15 2020
%C A099594 When indexed as a triangular array, T(n,k) is the number of permutations of [n] in which 1 is in position k and the excedance entries are precisely the entries to the left of 1. See link. - _David Callan_, Dec 12 2021
%C A099594 T(n,k) is also the number of max-closed relations between an ordered n-element set and an ordered k-element set (see the paper by Jeavons and Cooper 1995). -  _Don Knuth_, Feb 12 2024
%H A099594 Alois P. Heinz, <a href="/A099594/b099594.txt">Rows n = 0..140, flattened</a>
%H A099594 Arvind Ayyer and Beáta Bényi, <a href="https://arxiv.org/abs/2104.13654">Toppling on permutations with an extra chip</a>, arXiv:2104.13654 [math.CO], 2021. See Table 1 (a) p. 4.
%H A099594 Beáta Bényi, <a href="https://doi.org/10.14232/phd.2410">Advances in Bijective Combinatorics</a>, Ph. D. Dissertation, Doctoral School of Mathematics and Computer Science, University of Szeged, Bolyai Institute, 2014. See Table 1.
%H A099594 Beáta Bényi and Peter Hajnal, <a href="http://arxiv.org/abs/1510.05765">Combinatorics of poly-Bernoulli numbers</a>, arXiv:1510.05765 [math.CO], 2015.
%H A099594 Beata Bényi and Peter Hajnal, <a href="https://arxiv.org/abs/1602.08684">Combinatorial properties of poly-Bernoulli relatives</a>, arXiv preprint arXiv:1602.08684 [math.CO], 2016.
%H A099594 Beata Benyi and Peter Hajnal, <a href="https://arxiv.org/abs/1804.01868">Poly-Bernoulli Numbers and Eulerian Numbers</a>, arXiv:1804.01868 [math.CO], 2018.
%H A099594 Beáta Bényi and Matthieu Josuat-Vergès, <a href="https://arxiv.org/abs/2010.10060">Combinatorial proof of an identity on Genocchi numbers</a>, arXiv:2010.10060 [math.CO], 2020.
%H A099594 Beáta Bényi and Gábor V. Nagy, <a href="https://arxiv.org/abs/1707.06899">Bijective enumerations of Γ-free 0-1 matrices</a>, arXiv:1707.06899 [math.CO], 2017.
%H A099594 Beáta Bényi and José Luis Ramírez, <a href="https://arxiv.org/abs/1909.09949">On q-poly-Bernoulli numbers arising from combinatorial interpretations</a>, arXiv:1909.09949 [math.CO], 2019.
%H A099594 Beáta Bényi and José Luis Ramírez, <a href="https://arxiv.org/abs/2105.04791">Poly-Cauchy numbers - the combinatorics behind</a>, arXiv:2105.04791 [math.CO], 2021.
%H A099594 Beáta Bényi and José Luis Ramírez, <a href="http://ecajournal.haifa.ac.il/Volume2022/ECA2022_S2A1.pdf">Poly-Cauchy Numbers of the Second Kind-the Combinatorics Behind</a>, Enumerative Comb. Appl. (2022) Vol. 2, No. 1, Art. #S2R1.
%H A099594 Chad Brewbaker, <a href="http://www.emis.de/journals/INTEGERS/papers/i2/i2.Abstract.html">A combinatorial interpretation of the poly-Bernoulli numbers and two Fermat analogues</a>, INTEGERS Vol. 8 (2008), #A02.
%H A099594 David Callan, <a href="/A099594/a099594.pdf">Permutations whose excedance positions are those before 1</a>
%H A099594 Frédéric Chapoton and Vincent Pilaud, <a href="https://arxiv.org/abs/2201.06896">Shuffles of deformed permutahedra, multiplihedra, constrainahedra, and biassociahedra</a>, arXiv:2201.06896 [math.CO], 2022. See p. 12.
%H A099594 Peter G. Jeavons and Martin C. Cooper, <a href="https://doi.org/10.1016/0004-3702(95)00107-7">Tractable constraints on ordered domains</a>, Artificial Intelligence 79 (1995), 327-339.
%H A099594 Hyeong-Kwan Ju and Seunghyun Seo, <a href="http://dx.doi.org/10.1016/j.disc.2012.04.019">Enumeration of (0,1)-matrices avoiding some 2 X 2 matrices</a>, Discrete Math., 312 (2012), 2473-2481.
%H A099594 Ken Kamano, <a href="https://arxiv.org/abs/1701.07157">Lonesum decomposable matrices</a>, arXiv:1701.07157 [math.CO], 2017.
%H A099594 Masanobu Kaneko, <a href="http://www.numdam.org/item?id=JTNB_1997__9_1_221_0">Poly-Bernoulli numbers</a>, Journal de théorie des nombres de Bordeaux, 9 no. 1 (1997), Pages 221-228.
%H A099594 Anatol N. Kirillov, <a href="https://doi.org/10.3842/SIGMA.2016.002">On some quadratic algebras. I 1/2: Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials</a>, SIGMA, Symmetry Integrability Geom. Methods Appl. 12, Paper 002, 172 p. (2016).
%H A099594 Don Knuth, <a href="http://cs.stanford.edu/~knuth/papers/poly-Bernoulli.pdf">Parades and poly-Bernoulli bijections</a>, Mar 31 2024. See (0.1).
%H A099594 D. E. Knuth, <a href="/A372066/a372066.txt">Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints</a>, May 06 2024.  Mentions this sequence.
%H A099594 Stéphane Launois, <a href="http://dx.doi.org/10.1016/j.jalgebra.2006.10.023">Combinatorics of H-primes in quantum matrices</a>, Journal of Algebra, Volume 309, Issue 1, 2007, Pages 139-167.
%H A099594 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>
%H A099594 H. A. Witek, G. Mos and C.-P. Chou, <a href="http://match.pmf.kg.ac.rs/electronic_versions/Match73/n2/match73n2_427-442.pdf">Zhang-Zhang Polynomials of Regular 3-and 4-tier Benzenoid Strips</a>, MATCH Commun. Math. Comput. Chem. 73 (2015) 427-442.
%H A099594 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>
%F A099594 pB(k, n) = (-1)^n * Sum[i=0..n, (-1)^i * i! * Stirling2(n, i) / (i+1)^k ].
%F A099594 E.g.f.: e^(x+y) / [e^x + e^y - e^(x+y)].
%F A099594 T(n, k) = Sum_{j=0..n} (j+1)^k*Sum_{i=0..j} (-1)^(n+j-i)*C(j, i)*(j-i)^n. - _Paul D. Hanna_, Nov 04 2004
%F A099594 n-th row of the array = row sums of n-th power of triangle A210381. - _Gary W. Adamson_, Mar 21 2012
%e A099594 Square array begins:
%e A099594   1,  1,   1,    1,     1,      1, ...
%e A099594   1,  2,   4,    8,    16,     32, ...
%e A099594   1,  4,  14,   46,   146,    454, ...
%e A099594   1,  8,  46,  230,  1066,   4718, ...
%e A099594   1, 16, 146, 1066,  6902,  41506, ...
%e A099594   1, 32, 454, 4718, 41506, 329462, ...
%e A099594   ...
%p A099594 A:= (n, k)-> add(Stirling2(n+1, i+1)*Stirling2(k+1, i+1)*
%p A099594              i!^2, i=0..min(n, k)):
%p A099594 seq(seq(A(n, d-n), n=0..d), d=0..10);  # _Alois P. Heinz_, Jan 02 2016
%t A099594 T[n_, k_] := Sum[(-1)^(j+n)*(1+j)^k*j!*StirlingS2[n, j], {j, 0, n}]; Table[ T[n-k, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jan 30 2016 *)
%o A099594 (PARI) T(n,k)=sum(j=0,n,(j+1)^k*sum(i=0,j,(-1)^(n+j-i)*binomial(j,i)*(j-i)^n))
%o A099594 (PARI) T(n,k)=sum(j=0,min(n,k), j!^2*stirling(n+1, j+1, 2)*stirling(k+1, j+1, 2)); \\ _Michel Marcus_, Mar 05 2017
%Y A099594 Rows 0..9 are A000012, A000079, A027649, A027650, A027651, A283811, A283812, A283813, A284032, A284033.
%Y A099594 Main diagonal is A048163. Another diagonal is A188634.
%Y A099594 Antidiagonal sums are in A098830.
%Y A099594 Cf. A019538, A210381, A266695.
%K A099594 nonn,tabl
%O A099594 0,5
%A A099594 _Ralf Stephan_, Oct 27 2004