A225114 - OEIS

%I #32 Sep 22 2024 03:08:32

%S 1,1,3,9,28,87,272,850,2659,8318,26025,81427,254777,797175,2494307,

%T 7804529,24419909,76408475,239077739,748060606,2340639096,7323726778,

%U 22915525377,71701378526,224349545236,701976998795,2196446204672,6872555567553,21503836486190,67284284442622,210528708959146

%N Number of skew partitions of n whose diagrams have no empty rows and columns.

%C A skew partition S of size n is a pair of partitions [p1,p2] where p1 is a partition of the integer n1, p2 is a partition of the integer n2, p2 is an inner partition of p1, and n=n1-n2. We say that p1 and p2 are respectively the inner and outer partitions of S. A skew partition can be depicted by a diagram made of rows of cells, in the same way as a partition. Only the cells of the outer partition p1 which are not in the inner partition p2 appear in the picture. [from the Sage manual, see links]

%H Sage Development Team, <a href="http://www.sagemath.org/doc/reference/combinat/sage/combinat/skew_partition.html">Skew Partitions</a>, Sage Reference Manual.

%F Conjectured g.f.: 1/(2 - 1/(1 - x/(1 - x/(1 - x^2/(1 - x^2/(1 - x^3/(1 - x^3/(1 - ...)))))))). - _Mikhail Kurkov_, Sep 03 2024

%e The a(4)=28 skew partitions of 4 are

%e 01:  [[4], []]

%e 02:  [[3, 1], []]

%e 03:  [[4, 1], [1]]

%e 04:  [[2, 2], []]

%e 05:  [[3, 2], [1]]

%e 06:  [[4, 2], [2]]

%e 07:  [[2, 1, 1], []]

%e 08:  [[3, 2, 1], [1, 1]]

%e 09:  [[3, 1, 1], [1]]

%e 10:  [[4, 2, 1], [2, 1]]

%e 11:  [[3, 3], [2]]

%e 12:  [[4, 3], [3]]

%e 13:  [[2, 2, 1], [1]]

%e 14:  [[3, 3, 1], [2, 1]]

%e 15:  [[3, 2, 1], [2]]

%e 16:  [[4, 3, 1], [3, 1]]

%e 17:  [[2, 2, 2], [1, 1]]

%e 18:  [[3, 3, 2], [2, 2]]

%e 19:  [[3, 2, 2], [2, 1]]

%e 20:  [[4, 3, 2], [3, 2]]

%e 21:  [[1, 1, 1, 1], []]

%e 22:  [[2, 2, 2, 1], [1, 1, 1]]

%e 23:  [[2, 2, 1, 1], [1, 1]]

%e 24:  [[3, 3, 2, 1], [2, 2, 1]]

%e 25:  [[2, 1, 1, 1], [1]]

%e 26:  [[3, 2, 2, 1], [2, 1, 1]]

%e 27:  [[3, 2, 1, 1], [2, 1]]

%e 28:  [[4, 3, 2, 1], [3, 2, 1]]

%o (Sage) [SkewPartitions(n).cardinality() for n in range(16)]

%o (PARI) \\ The following program is significantly faster.

%o A225114(n)=

%o {

%o     my( C=vector(n, j, 1) );

%o     my(m=n, z, t, ret);

%o     while ( 1,  /* for all compositions C[1..m] of n */

%o \\        print( vector(m, n, C[n] ) ); /* print composition */

%o         t = prod(j=2,m, min(C[j-1], C[j]) + 1 );  /* A225114 */

%o \\        t = prod(j=2,m, min(C[j-1], C[j]) + 0 );  /* A006958 */

%o \\        t = prod(j=2,m, C[j-1] + C[j] + 0 );  /* A059716 */

%o \\        t = prod(j=2,m, C[j-1] + C[j] + 1 );  /* A187077 */

%o \\        t = sum(j=2,m, C[j-1] > C[j] );  /* A045883 */

%o         ret += t;

%o         if ( m<=1, break() ); /* last composition? */

%o         /* create next composition: */

%o         C[m-1] += 1;

%o         z = C[m];

%o         C[m] = 1;

%o         m += z - 2;

%o     );

%o     return(ret);

%o }

%o for (n=0, 30, print1(A225114(n),", "));

%o \\ _Joerg Arndt_, Jul 09 2013

%K nonn

%O 0,3

%A _Joerg Arndt_, Apr 29 2013

%E Edited by _Max Alekseyev_, Dec 22 2015