cp's OEIS Frontend

A063746 Triangle read by rows giving number of partitions of k (k=0 .. n^2) with Ferrers plot fitting in an n X n box.

%I A063746 #87 Jan 09 2025 19:01:19
%S A063746 1,1,1,1,1,2,1,1,1,1,2,3,3,3,3,2,1,1,1,1,2,3,5,5,7,7,8,7,7,5,5,3,2,1,
%T A063746 1,1,1,2,3,5,7,9,11,14,16,18,19,20,20,19,18,16,14,11,9,7,5,3,2,1,1,1,
%U A063746 1,2,3,5,7,11,13,18,22,28,32,39,42,48,51,55,55,58,55,55,51,48,42,39,32,28
%N A063746 Triangle read by rows giving number of partitions of k (k=0 .. n^2) with Ferrers plot fitting in an n X n box.
%C A063746 Seems to approximate a Gaussian distribution, the sum of all 1+n^2 terms in a row equals the central binomial coefficients.
%C A063746 a(n,k) is the number of sequences of n 0's and n 1's having major index equal to k (the major index is the sum of the positions of the 1's that are immediately followed by 0's). Equivalently, a(n,k) is the number of Grand Dyck paths of length 2n for which the sum of the positions of the valleys is k. Example: a(3,7)=2 because the only sequences of three 0's and three 1's with major index 7 are 010110 and 110010. The corresponding Grand Dyck paths are obtained by replacing a 0 by a U=(1,1) step and a 1 by a D=(1,-1) step. - _Emeric Deutsch_, Oct 02 2007
%C A063746 Also, number of n-multisets in [0..n] whose elements sum up to n. - _M. F. Hasler_, Apr 12 2012
%C A063746 Let P be the poset [n] X [n] ordered by the product order.  Let J(P) be the set of all order ideals of P, ordered by inclusion.  Then J(P) is a finite sublattice of Young's lattice and T(n,k) is the number of elements in J(P) that have rank k. - _Geoffrey Critzer_, Mar 26 2020
%D A063746 G. E. Andrews and K. Eriksson, Integer partitions, Cambridge Univ. Press, 2004, pp. 67-69.
%D A063746 D. M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999; exercise 3.2.3.
%D A063746 A. V. Yurkin, New binomial and new view on light theory, (book), 2013, 78 pages, no publisher listed.
%H A063746 Alois P. Heinz, <a href="/A063746/b063746.txt">Rows k = 0..31, flattened</a>
%H A063746 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, 2009, page 45.
%H A063746 A. V. Yurkin, <a href="http://www.mce.biophys.msu.ru/eng/archive/abstracts/mce19/sect1138/doc150220/">On similarity of systems of geometrical and arithmetic triangles</a>, in Mathematics, Computing, Education Conference XIX, 2012.
%H A063746 A. V. Yurkin, <a href="http://arxiv.org/abs/1302.6287">New view on the diffraction discovered by Grimaldi and Gaussian beams</a>, arXiv preprint arXiv:1302.6287 [physics.optics], 2013.
%F A063746 Table[T[k, n, n], {n, 0, 9}, {k, 0, n^2}] with T[ ] defined as in A047993.
%F A063746 G.f.: Consider a function; f(n) = 1 + sum(i_1=1, n, sum(i_2=0, i_1, ..., sum(i_n=0, i_(n-1), x^(sum(j=1, n, i_j))*(1+...+x^i_n))...)) Then the GF is f(1)+x^3.f(2)+x^8.f(3)+..., where after x^3 the increase is n^2+1 from f(n). - _Jon Perry_, Jul 13 2004
%F A063746 G.f. for n-th row is obtained if we set x(i) = 1+x^i+x^(2*i)+...+x^(n*i), i=1, 2, ..., n, in the cycle index Z(S(n);x(1), x(2), ..., x(n)) of the symmetric group S(n) of degree n. - _Vladeta Jovovic_, Dec 17 2004
%F A063746 G.f. of row n: the q-binomial coefficient [2n,n]. - _Emeric Deutsch_, Apr 23 2007
%F A063746 T(n,k)=1 for k=0,1,n^2-1,n^2. For all m>n, T(m,n)=T(n,n)=A000041(n), i.e., below the diagonal the columns remain constant, because there cannot be more than n nonzero elements with sum <= n. - _M. F. Hasler_, Apr 12 2012
%F A063746 T(n,2n) = A128552(n-2). - _Geoffrey Critzer_, Sep 27 2013
%F A063746 From _Alois P. Heinz_, Jan 09 2025: (Start)
%F A063746 Sum_{k=0..n} T(n,k) = A000070(n).
%F A063746 Sum_{k=0..n} k * T(n,k) = A182738(n).
%F A063746 Sum_{k=0..n^2} k * T(n,k) = A002544(n-1) for n>=1.
%F A063746 Sum_{k=0..n^2} (-1)^k * T(n,k) = A126869(n). (End)
%e A063746 From _M. F. Hasler_, Apr 12 2012: (Start)
%e A063746 The table reads:
%e A063746 n=0: 1  _  (k=0)
%e A063746 n=1: 1 1  _  (k=0..1)
%e A063746 n=2: 1 1 2 1 1  _  (k=0..4)
%e A063746 n=3: 1 1 2 3 3 3 3  2  1  1  _  (k=0..9)
%e A063746 n=4: 1 1 2 3 5 5 7  7  8  7  7  5  5  3  2  1  1  _  (k=0..16)
%e A063746 n=5: 1 1 2 3 5 7 9 11 14 16 18 19 20 20 19 18 16 ...  _  (k=0..25)
%e A063746 etc. (End)
%e A063746 Cycle index of S(3) is (1/6)*(x(1)^3+3*x(1)*x(2)+2*x(3)), so g.f. for 3rd row is (1/6)*((1+x+x^2+x^3)^3+3*(1+x+x^2+x^3)*(1+x^2+x^4+x^6)+2*(1+x^3+x^6+x^9)) = x^9+x^8+2*x^7+3*x^6+3*x^5+3*x^4+3*x^3+2*x^2+x+1.
%e A063746 a(3,7)=2 because the only partitions of 7 with Ferrers plot fitting into a 3 X 3 box are [3,3,1] and [3,2,2].
%p A063746 for n from 0 to 15 do QBR[n]:=sum(q^i,i=0..n-1) od: for n from 0 to 15 do QFAC[n]:=product(QBR[j],j=1..n) od: qbin:=(n,k)->QFAC[n]/QFAC[k]/QFAC[n-k]: for n from 0 to 7 do P[n]:=sort(expand(simplify(qbin(2*n,n)))) od: for n from 0 to 7 do seq(coeff(P[n],q,j),j=0..n^2) od; # yields sequence in triangular form - _Emeric Deutsch_, Apr 23 2007
%p A063746 # second Maple program:
%p A063746 b:= proc(n, i, k) option remember;
%p A063746       `if`(n=0, 1, `if`(i<1 or k<1, 0, b(n, i-1, k)+
%p A063746       `if`(i>n, 0, b(n-i, i, k-1))))
%p A063746     end:
%p A063746 T:= n-> seq(b(k, min(n, k), n), k=0..n^2):
%p A063746 seq(T(n), n=0..8); # _Alois P. Heinz_, Apr 05 2012
%t A063746 Table[nn=n^2;CoefficientList[Series[Product[(1-x^(n+i))/(1-x^i),{i,1,n}],{x,0,nn}],x],{n,0,6}]//Grid (* _Geoffrey Critzer_, Sep 27 2013 *)
%t A063746 Table[CoefficientList[QBinomial[2n,n,q] // FunctionExpand, q], {n,0,6}] // Flatten (* _Peter Luschny_, Jul 22 2016 *)
%t A063746 b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1 || k < 1, 0, b[n, i - 1, k] + If[i > n, 0, b[n - i, i, k - 1]]]];
%t A063746 T[n_] := Table[b[k, Min[n, k], n], {k, 0, n^2}];
%t A063746 Table[T[n], {n, 0, 8}] // Flatten (* _Jean-François Alcover_, Nov 27 2020, after _Alois P. Heinz_ *)
%o A063746 (PARI) T(n,k)=polcoeff(prod(i=0,n,sum(j=0,n,x^(j*i*(n^2+n+1)+j),O(x^(k*(n^2+n+1)+n+1)))),k*(n^2+n+1)+n)  /* Based on a more general formula due to R. Gerbicz. _M. F. Hasler_, Apr 12 2012 */
%Y A063746 Cf. A000041, A000070, A002544, A008968, A047971, A047993, A126869, A182738.
%Y A063746 Row lengths are given by A002522. - _M. F. Hasler_, Apr 14 2012
%Y A063746 Antidiagonal sums are given by A260894.
%Y A063746 Row sums give A000984.
%K A063746 nonn,tabf
%O A063746 0,6
%A A063746 _Wouter Meeussen_, Aug 14 2001