login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A093695 Number of one-element transitions among partitions of the integer n for unlabeled parts. 9
0, 0, 2, 4, 10, 18, 34, 56, 94, 146, 228, 340, 506, 730, 1050, 1476, 2066, 2844, 3896, 5268, 7090, 9442, 12518, 16454, 21534, 27980, 36210, 46572, 59674, 76056, 96594, 122106, 153852, 193048, 241492, 300974, 374038, 463286, 572304, 704826, 865874, 1060766 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

It appears that a(n) = 2 * A000097(n-2). - George Beck, Sep 05 2014

It appears that a(n) = A135348(n+1) - A000070(n). - Thomas Baruchel, May 12 2018

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..5000

FORMULA

a(n) = Sum_p=1^P(n) Sum_i=1^D(p) Sum_j=1^D(p) 1 [subject to: i <> j and d(i,p) <= d(j,p) and d(i,p) <> d(i-1,p) (if i > 1) and d(j,i) <> d(j-1,i) (if j > 1 and if d(j-1,p) has given a contribution to the sum) ]; P(n) = number of partitions of n, D(p) = number of digits in partition p, d(i,p) and d(j,p) = digits number i and j in partition p of integer n.

See the corresponding formula for a(n) for the labeled case A094533.

a(n) = Sum_i=1^P(n+1) S(i, n+1)^2 - S(i, n+1), where P(n+1) is the number of integer partitions of n+1 and S(i, n+1) is the number of digits in the set of digits of the i-th partition of n+1. (E.g. the partition [1111233] has the set of digits {1, 2, 3} and would contribute 3^2 - 3 = 6 to the sum.)

G.f.: 2*x^2 / (x^3-x^2-x+1) * Product_{m>=1} (1/(1-x^m))  (conjectured). - Thomas Baruchel, May 12 2018

EXAMPLE

In the unlabeled case we have 10 one-element transitions among all partitions of n=4: [1,1,1,1] -> [1,1,2]; [1,1,2] -> [2,2]; [1,1,2] -> [1,3]; [2,2] -> [1,3]; [1,3] -> [4] and [1,1,2] -> [1,1,1,1]; [2,2] -> [1,1,2]; [1,3] -> [1,1,2]; [1,3] -> [2,2]; [4] -> [1,3].

n=5:

partition number p=1 is [1,1,1,1,1], digits d(1,1)=1, d(2,1)=1 contribute 1;

partition number p=2 is [1,1,1,2], digits d(1,1)=1, d(2,2)=1 contribute 1, digits d(1,2)=2, d(4,2)=2 contribute 1;

partition number p=3 is [1,2,2], digits d(1,3)=1, d(2,3)=2 contribute 1, digits d(2,3)=2, d(3,3)=2 contribute 1;

partition number p=4 is [1,1,3], digits d(1,4)=1, d(2,4)=1 contribute 1, digits d(1,4)=1, d(3,4)=3 contribute 1;

partition number p=5 is [2,3], digits d(1,5)=2, d(2,5)=3 contribute 1;

partition number p=6 is [1,4], digits d(1,6)=1, d(2,6)=4 contribute 1;

partition number p=7 is [5], digits d(1,7)=5 contributes 0;

==> a(5)=2*9=18 (factor 2 if we accept up and down transitions).

a(5) = 18 because the 11 partitions of n=5+1=6 have the following sets of digits:

{1} contributes 0, {1, 2} contributes 2, {1, 2} contributes 2,

{2} contributes 0, {1, 3} contributes 2, {1, 2, 3} contributes 6,

{3} contributes 0, {1, 4} contributes 2, {2, 4} contributes 2,

{1, 5} contributes 2, {6} contributes 0,

which gives 0 + 2 + 2 + 0 + 2 + 6 + 0 + 2 + 2 + 2 + 0 = 18.

G.f. = 2*x^2 + 4*x^3 + 10*x^4 + 18*x^5 + 34*x^6 + 56*x^7 + 94*x^8 + ...

MAPLE

A093695 := proc(n::integer) local a, ndxp, ListOfPartitions, APartition, PartOfAPartition, SetOfParts, iverbose; with(combinat): iverbose:=1; ListOfPartitions:=partition(n+1); a:=0; for ndxp from 1 to nops(ListOfPartitions) do APartition := ListOfPartitions[ndxp]; SetOfParts := convert(APartition, set); a := a + nops(SetOfParts)^2 - nops(SetOfParts); if iverbose = 1 then print ("ndxp, SetOfParts, nops(SetOfParts)^2 - nops(SetOfParts): ", ndxp, SetOfParts, nops(SetOfParts)^2 - nops(SetOfParts)); fi; # End of do-loop *** ndxp ***. end do; print("n, a(n):", n, a); end proc;

# second Maple program

b:= proc(n, i) option remember; local j, f, g;

      if n=0 then [0]

    elif i=1 then [1]

    else f:= b(n, i-1);

         for j to floor(n/i) do f:= zip((x, y)-> x+y,

             f, `if`(n=i*j, [1], [0, b(n-i*j, i-1)[]]), 0)

         od; f

      fi

    end:

a:= n-> (l-> add(i*(i-1)*l[i], i=1..nops(l)))(b(n+1, n+1)):

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

MATHEMATICA

a[n_] := Block[{p = IntegerPartitions[n + 1], l = PartitionsP[n + 1]}, Sum[ Length[ Union[ p[[k]]]]^2 - Length[ Union[ p[[k]] ]], {k, l}]]; Table[ a[n], {n, 0, 40}] (* Robert G. Wilson v, Jul 13 2004, updated by Jean-Fran├žois Alcover, Jan 29 2014 *)

CROSSREFS

Cf. A093694, A089378.

Cf. A094533.

Column k=2 of triangle A322210.

Sequence in context: A005541 A045955 A182248 * A308529 A320098 A320968

Adjacent sequences:  A093692 A093693 A093694 * A093696 A093697 A093698

KEYWORD

nonn

AUTHOR

Thomas Wieder, Apr 10 2004

EXTENSIONS

More terms from Robert G. Wilson v, Jul 13 2004

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 April 13 11:56 EDT 2021. Contains 342936 sequences. (Running on oeis4.)