login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 10
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

Seems to approximate a Gaussian distribution, the sum of all 1+n^2 terms in a row equals the central binomial coefficients.

a(n,k) is the number of sequences of n 0s and n 1s having major index equal to k (the major index is the sum of the positions of the 1s that are immediately followed by 0s). 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 3 0s and 3 1s 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

Also, number of n-multisets in [0..n] whose elements sum up to n. - M. F. Hasler, Apr 12 2012

REFERENCES

G. E. Andrews and K. Eriksson, Integer partitions, Cambridge Univ. Press, 2004, pp. 67-69.

D. M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999; exercise 3.2.3.

A. V. Yurkin, On similarity of systems of geometrical and arithmetic triangles, in Mathematics, Computing, Education Conference XIX, 2012.  http://www.mce.biophys.msu.ru/eng/archive/abstracts/mce19/sect1138/doc150220/

A. V. Yurkin, New binomial and new view on light theory, (book), 2013, 78 pages, no publisher listed.

LINKS

Alois P. Heinz, Rows k = 0..31, flattened

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 45.

A. V. Yurkin, New view on the diffraction discovered by Grimaldi and Gaussian beams, arXiv preprint arXiv:1302.6287, 2013

FORMULA

Table[T[k, n, n], {n, 0, 9}, {k, 0, n^2}] with T[ ] defined as in A047993.

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

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

G.f. of row n = the q-binomial coefficient [2n,n]. - Emeric Deutsch, Apr 23 2007

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

T(n,2n) = A128552(n-2). - Geoffrey Critzer, Sep 27 2013

EXAMPLE

From M. F. Hasler, Apr 12 2012: (Start)

The table reads:

n=0: 1  _  (k=0)

n=1: 1 1  _  (k=0..1)

n=2: 1 1 2 1 1  _  (k=0..4)

n=3: 1 1 2 3 3 3 3  2  1  1  _  (k=0..9)

n=4: 1 1 2 3 5 5 7  7  8  7  7  5  5  3  2  1  1  _  (k=0..16)

n=5: 1 1 2 3 5 7 9 11 14 16 18 19 20 20 19 18 16 ...  _  (k=0..25)

etc. (End)

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.

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

MAPLE

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

# second Maple program:

b:= proc(n, i, k) option remember;

      `if`(n=0, 1, `if`(i<1 or k<1, 0, b(n, i-1, k)+

      `if`(i>n, 0, b(n-i, i, k-1))))

    end:

T:= n-> seq(b(k, min(n, k), n), k=0..n^2):

seq(T(n), n=0..8); # Alois P. Heinz, Apr 05 2012

MATHEMATICA

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

Table[CoefficientList[QBinomial[2n, n, q] // FunctionExpand, q], {n, 0, 6}] // Flatten (* Peter Luschny, Jul 22 2016 *)

PROG

(PARI) f1(x)=1+x*sum(j=0, 1, x^j); f2(x)=1+sum(i=1, 2, x^i*sum(j=0, i, x^j)); f3(x)=1+sum(i=1, 3, sum(k=0, i, x^(i+k)*sum(j=0, k, x^j))); f4(x)=1+sum(i=1, 4, sum(i1=0, i, sum(k=0, i1, x^(i+i1+k)*sum(j=0, k, x^j)))) f(x)=f1(x)+x^3*f2(x)+x^8*f3(x)+x^18*f4(x); for (i=0, 30, print1(", "polcoeff(f(x), i))) (Perry)

(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

CROSSREFS

Cf. A008968, A047971, A047993.

Row lengths are given by A002522. - M. F. Hasler, Apr 14 2012

Antidiagonal sums are given by A260894.

Sequence in context: A247378 A094102 A220091 * A293429 A201075 A131338

Adjacent sequences:  A063743 A063744 A063745 * A063747 A063748 A063749

KEYWORD

nonn,tabf

AUTHOR

Wouter Meeussen, Aug 14 2001

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 19 13:11 EDT 2019. Contains 324222 sequences. (Running on oeis4.)