A026794 - OEIS

%I #111 Aug 06 2024 00:02:46

%S 1,1,1,2,0,1,3,1,0,1,5,1,0,0,1,7,2,1,0,0,1,11,2,1,0,0,0,1,15,4,1,1,0,

%T 0,0,1,22,4,2,1,0,0,0,0,1,30,7,2,1,1,0,0,0,0,1,42,8,3,1,1,0,0,0,0,0,1,

%U 56,12,4,2,1,1,0,0,0,0,0,1,77,14,5,2,1,1,0,0,0,0,0,0,1,101,21,6,3,1,1,1,0,0,0,0,0,0,1

%N Triangular array T read by rows: T(n,k) = number of partitions of n in which least part is k, 1<=k<=n.

%C At least one part is k and each part is at least k.

%C From _Emeric Deutsch_, Feb 19 2006: (Start)

%C Also number of partitions of n in which the largest part occurs exactly k times. Example: T(6,2)=2 because we have [3,3] and [2,2,1,1].

%C G.f. of column k is x^k/prod(j>=k, 1-x^j ) (k>=1).

%C Row sums yield the partition numbers (A000041).

%C T(n,1) = A000041(n-1) (the partition numbers).

%C T(n,2) = A002865(n-2) (n>=2).

%C T(n,3)=A026796(n). T(n,4) = A026797(n). T(n,5) = A026798(n). T(n,6) = A026799(n). T(n,7) = A026800(n). T(n,8) = A026801(n). T(n,9) = A026802(n). T(n,10) = A026803(n).

%C Sum(k*T(n,k),k=1..n) = A046746(n). (End)

%C Triangle inverse = A161363. - _Gary W. Adamson_, Jun 07 2009

%C T(n,g) is also the number of not necessarily connected 2-regular graphs with girth exactly g: the part i corresponds to the i-cycle; addition of integers corresponds to disconnected union of cycles. - _Jason Kimberley_, Feb 05 2012

%C From _Bob Selcoe_, Jul 24 2014 (Start):

%C Below is a process to generate equations for column k.

%C Let P be the partition numbers A000041(n-j) and let f(k) denote equations which generate column k.

%C To find f(k), start with f(1) = P(n-j), j=1. Thus T(n,1) = f(1) = P(n-1). This is the equation for column 1.

%C To find f(k) k>1, first sum the terms of f(k-1) replacing the value j with j+1, and then subtract the terms of f(k-1) replacing the value j with j+k. So to find f(2) (i.e., the equation for column 2, where k=2), start with f(1) = P(n-1); first replace j with j+1 (yielding P(n-2)), and then replace j with j+2 (yielding P(n-3)).  Subtracting the second term from the first, we get: f(2) = P(n-2) - P(n-3).

%C To find f(3), start with f(2), replace j with j+1 (yielding P(n-3) - P(n-4)) and then replace j with j+3 (yielding P(n-5) - P(n-6)). Subtracting the second group of terms from the first, we get: f(3) = P(n-3) - P(n-4) - P(n-5) + P(n-6). This is the equation for column 3; also the equation for T(n,3) = A026796(n). So for example, T(13,3) = 5 because P(13-3) - P(13-4) - P(13-5) + P(13-6) = 42 - 30 - 22 + 15 = 5.

%C Continue as above to find f(k) k={4..inf.}.  This will generate equations for T(n,4) = A026797(n), T(n,5) = A026798(n), T(n,6) = A026799(n), ad inf.

%C (End)

%H Alois P. Heinz, <a href="/A026794/b026794.txt">Rows n = 1..141, flattened</a>

%H Kevin Brown, <a href="http://www.mathpages.com/home/kmath623/kmath623.htm">On Euler's Pentagonal Theorem</a>, 1994-2008.

%H Jason Kimberley, <a href="/wiki/User:Jason_Kimberley/E_k-reg_girth_eq_g_index">Index of sequences counting not necessarily connected k-regular simple graphs with girth exactly g</a>.

%H Johannes W. Meijer, Euler's ship on the Pentagonal Sea, <a href="/A026794/a026794.pdf">pdf</a> and <a href="/A026794/a026794.jpg">jpg</a>.

%H J. W. Meijer and M. Nepveu, <a href="http://www.ucbcba.edu.bo/Publicaciones/revistas/actanova/documentos/v4n1/v4.n1.Meijer.pdf">Euler's ship on the Pentagonal Sea</a>, Acta Nova, Volume 4, No. 1, December 2008. pp. 176-187.

%H Tilman Piesk, <a href="http://paste.watchduck.net/1602/intpart/A026794.html">First 50 rows</a> and illustrations of columns n = <a href="http://paste.watchduck.net/1602/intpart/addends_ge_2.html">2</a>, <a href="http://paste.watchduck.net/1602/intpart/addends_ge_3.html">3</a>, <a href="http://paste.watchduck.net/1602/intpart/addends_ge_4.html">4</a>, <a href="http://paste.watchduck.net/1602/intpart/addends_ge_5.html">5</a>, <a href="http://paste.watchduck.net/1602/intpart/addends_ge_6.html">6</a>, <a href="http://paste.watchduck.net/1602/intpart/addends_ge_7.html">7</a>, <a href="http://paste.watchduck.net/1602/intpart/addends_ge_8.html">8</a>. a(n, k) is the number of gray fields in row n of table k.

%F T(n, k) = sum{T(n-k, i), k<=i<=n-k} for k=1, 2, ..., m, T(n, k)=0 for k=m+1, ..., n-1, where m=floor(n/2); T(n, n)=1 for n >= 1.

%F G.f.: G(t,x)=sum(t^i*x^i/product(1-x^j, j=i..infinity), i=1..infinity). - _Emeric Deutsch_, Feb 19 2006

%F G.f.: Sum_{k>=1} tx^k/(1-tx^k)/product(1-x^j,j=1..k-1). - _Emeric Deutsch_, Mar 13 2006

%F T(n,k) = T(n-1,k-1) - T(n-k,k-1) for n>=2 and 2<=k<=(n-1) with T(n,1) = A000041(n-1), T(n,n) = 1 for n>=1 and T(n,k) = 0 for k>n. - _Johannes W. Meijer_, Jun 21 2010

%F T(k,k) = 1 and T(n,1) = row sum (n-1); thus Meijer's 2010 formula generates the triangle without a priori reference to A000041 (the partition sequence). - _Bob Selcoe_, Sep 03 2016

%e T(12,3) = 4 because we have [9,3], [6,3,3], [5,4,3] and [3,3,3,3]. - Edited by _Bob Selcoe_, Sep 03 2016

%e Triangle starts:

%e     1;

%e     1,  1;

%e     2,  0, 1;

%e     3,  1, 0, 1;

%e     5,  1, 0, 0, 1;

%e     7,  2, 1, 0, 0, 1;

%e    11,  2, 1, 0, 0, 0, 1;

%e    15,  4, 1, 1, 0, 0, 0, 1;

%e    22,  4, 2, 1, 0, 0, 0, 0, 1;

%e    30,  7, 2, 1, 1, 0, 0, 0, 0, 1;

%e    42,  8, 3, 1, 1, 0, 0, 0, 0, 0, 1;

%e    56, 12, 4, 2, 1, 1, 0, 0, 0, 0, 0, 1;

%e    77, 14, 5, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1;

%e   101, 21, 6, 3, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1;

%e   135, 24, 9, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1;

%e   ...

%p g:=sum(t^i*x^i/product(1-x^j,j=i..30),i=1..30): gser:=simplify(series(g,x=0,19)): for n from 1 to 15 do P[n]:=coeff(gser,x^n) od: for n from 1 to 15 do seq(coeff(P[n],t^j),j=1..n) od; # _Emeric Deutsch_, Feb 19 2006

%p nmax:=13; for n from 1 to nmax do T(n,n):=1 od: for n from 1 to nmax do for k from floor(n/2)+1 to n-1 do T(n,k):=0 od: od: for n from 2 to nmax do for k from 1 to floor(n/2) do T(n,k):=sum(T(n-k,i),i=k..n-k) od: od: seq(seq(T(n,k),k=1..n), n=1..nmax); # _Johannes W. Meijer_, Jun 21 2010

%p nmax:=13; with(combinat): for n from 1 to nmax do for k from n+1 to nmax do T(n,k):=0 od: od: for n from 1 to nmax do T(n,1):=numbpart(n-1) od: for n from 1 to nmax do T(n,n):=1 od: for n from 2 to nmax do for k from 2 to n-1 do T(n,k) := T(n-1,k-1) - T(n-k,k-1) od: od: seq(seq(T(n,k),k=1..n), n=1..nmax); # _Johannes W. Meijer_, Jun 21 2010

%p #

%p p:= (f, g)-> zip((x,y)-> x+y, f, g, 0):

%p b:= proc(n, i) option remember; local h;

%p       h:= `if`(n=i and i>0, [0$(i-1), 1], []);

%p       `if`(i<1, h, p(p(h, b(n, i-1)), `if`(n<i, [], b(n-i, i))))

%p     end:

%p T:= n-> b(n, n)[]:

%p seq(T(n), n=1..14); # _Alois P. Heinz_, Mar 28 2012

%t t[n_, k_] /; k<1 || k>n = 0; t[n_, n_] = 1; t[n_, k_] := t[n, k] = Sum[t[n-k, i], {i, k, n-k}]; Flatten[ Table[t[n, k], {n, 1, 14}, {k, 1, n}]] (* _Jean-François Alcover_, May 11 2012, after PARI *)

%o (PARI) {T(n, k) = if( k<1 || k>n, 0, if( n==k, 1, sum(i=k, n-k, T(n-k, i))))} \\ _Michael Somos_, Feb 06 2003

%o (PARI) A026794(n,k)=#select(p->p[1]==k,partitions(n,[k,n])) \\ For illustration: Creates the list of all partitions of n with smallest part equal to k. - _M. F. Hasler_, Jun 14 2018

%Y Row sums give A000041.

%Y Cf. A000041, A046746, A008284, A161363, A161364, A238341.

%Y Not necessarily connected 2-regular graphs with girth at least g [partitions into parts >= g]: A026807 (triangle); chosen g: A000041 (g=1 -- multigraphs with loops allowed), A002865 (g=2 -- multigraphs with loops forbidden), A008483 (g=3), A008484 (g=4), A185325(g=5), A185326 (g=6), A185327 (g=7), A185328 (g=8), A185329 (g=9). For g >= 3, girth at least g implies no loops or parallel edges. - _Jason Kimberley_, Feb 05 2012

%Y Not necessarily connected 2-regular graphs with girth exactly g [partitions with smallest part g]: this sequence (triangle); chosen g: A002865 (g=2), A026796 (g=3), A026797 (g=4), A026798 (g=5), A026799 (g=6), A026800(g=7), A026801 (g=8), A026802 (g=9), A026803 (g=10). - _Jason Kimberley_, Feb 05 2012

%K nonn,tabl,easy

%O 1,4

%A _Clark Kimberling_

%E More terms from _Emeric Deutsch_, Feb 19 2006