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

%I #150 May 18 2024 14:51:27

%S 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 1,64,454,1066,1066,454,64,1,1,128,1394,4718,6902,4718,1394,128,1,1,

%U 256,4246,20266,41506,41506,20266,4246,256,1,1,512,12866,85310,237686,329462,237686,85310,12866,512,1

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

%C 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 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 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 T(n,k) is also the number of acyclic orientations of the complete bipartite graph K_{n,k}. - _Vincent Pilaud_, Sep 15 2020

%C 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 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 Alois P. Heinz, <a href="/A099594/b099594.txt">Rows n = 0..140, flattened</a>

%H 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 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 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 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 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 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 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 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 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 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 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 David Callan, <a href="/A099594/a099594.pdf">Permutations whose excedance positions are those before 1</a>

%H 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 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 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 Ken Kamano, <a href="https://arxiv.org/abs/1701.07157">Lonesum decomposable matrices</a>, arXiv:1701.07157 [math.CO], 2017.

%H 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>

%H 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Acyclic_orientation">Acyclic orientation</a>

%F pB(k, n) = (-1)^n * Sum[i=0..n, (-1)^i * i! * Stirling2(n, i) / (i+1)^k ].

%F E.g.f.: e^(x+y) / [e^x + e^y - e^(x+y)].

%F 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 n-th row of the array = row sums of n-th power of triangle A210381. - _Gary W. Adamson_, Mar 21 2012

%e 1, 1, 1, 1, 1, 1, ...

%e 1, 2, 4, 8, 16, 32, ...

%e 1, 4, 14, 46, 146, 454, ...

%e 1, 8, 46, 230, 1066, 4718, ...

%e 1, 16, 146, 1066, 6902, 41506, ...

%e 1, 32, 454, 4718, 41506, 329462, ...

%e ...

%p A:= (n, k)-> add(Stirling2(n+1, i+1)*Stirling2(k+1, i+1)*

%p i!^2, i=0..min(n, k)):

%p seq(seq(A(n, d-n), n=0..d), d=0..10); # _Alois P. Heinz_, Jan 02 2016

%t 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 (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 (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 Rows 0..9 are A000012, A000079, A027649, A027650, A027651, A283811, A283812, A283813, A284032, A284033.

%Y Main diagonal is A048163. Another diagonal is A188634.

%Y Antidiagonal sums are in A098830.

%Y Cf. A019538, A210381, A266695.

%K nonn,tabl

%O 0,5

%A _Ralf Stephan_, Oct 27 2004