A138378 Number of embedded coalitions in an n-person game.

1, 3, 10, 37, 151, 674, 3263, 17007, 94828, 562595, 3535027, 23430840, 163254885, 1192059223, 9097183602, 72384727657, 599211936355, 5150665398898, 45891416030315, 423145657921379, 4031845922290572, 39645290116637023, 401806863439720943, 4192631462935194064

Offset

1,2

Comments

Same as A005493, apart from offset. - R. J. Mathar, Sep 23 2011

The strategic behavior of players depends crucially on the coalition structures of a game.

References

J. H. Conway and R. K. Guy, The Book of Numbers, Springer-Verlag, New York, 1995.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..575

E. T. Bell, Exponential numbers, Amer. Math. Monthly, 41 (1934), 411-419.

Gábor Czédli, Lattices with lots of congruence energy, arXiv:2205.02294 [math.RA], 2022.

A. L. L. Gao, S. Kitaev, and P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.

David W. K. Yeung, Recursive sequence identifying the number of embedded coalitions, International Game Theory Review 10(2008), 129-136.

Formula

a(1) = combination(1,0) = 1, a(2) = combination(2,1) + combination(2,0)= 3, a(n) = {SUM(i=2 to n-1) combination(n,i)} * {SUM(j=1 to i-1) a(n)} + SUM(i=0 to n-1) combination(n,i), for n > 2.

G.f.: 1/U(0) where U(k)= 1 - x*(k+3) - x^2*(k+1)/U(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 11 2012

G.f.: 1/(U(0)-x) where U(k)= 1 - x - x*(k+1)/(1 - x/U(k+1)); (continued fraction). - Sergei N. Gladkovskii, Oct 12 2012

G.f.: -G(0)/x^2 where G(k) = 1 - 1/(1-k*x)/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 08 2013

G.f.: Q(0)/x^2 -1/x^2, where Q(k) = 1 - x^2*(k+1)/( x^2*(k+1) - (1-x*(k+1))*(1-x*(k+2))/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 10 2013

a(n) = Bell(n+1)-Bell(n) = Sum_{k=1..n} k*Stirling2(n,k). - Alois P. Heinz, May 11 2017

E.g.f.: (exp(x) - 1) * exp(exp(x) - 1). - Ilya Gutkovskiy, Jan 26 2020

Example

a(1) = combination(1,0) = 1,
a(2) = combination(2,1) + combination(2,0)= 3,
a(3) = combination(3,2)* a(1) + combination(3,2) + combination(3,1) + combination(3,0)= 10,
a(4) = combination(4,3)* {a(1) + a(2)} + combination(4,2)* a(1) + combination7(4,3)combination(4,2) + combination(4,1) + combination(4,0)= 37,
a(5) = combination(5,4)* {a(1) + a(2) + a(3)} combination(5,3)* {a(1) + a(2)} + combination(5,2)* a(1) + combination(5,4) + combination(5,3) + combination(5,2) + combination(5,1) + combination(5,0)= 151.

Mathematica

a[n_] := Sum[Binomial[n, j] BellB[j], {j, 0, n-1}];
Array[a, 24] (* Jean-François Alcover, Aug 19 2018 *)

Prog

(Magma) [&+[k*StirlingSecond(n, k): k in [1..n]]: n in [1..25]]; // Vincenzo Librandi, May 18 2019

Crossrefs

Cf. A000110, A005493, A048993, A138379.

Column k=1 of A283424.

Sequence in context: A064613 A270789 A005493 * A250307 A363294 A289990

Adjacent sequences: A138375 A138376 A138377 * A138379 A138380 A138381

Keyword

nonn

Author

David Yeung (wkyeung(AT)hkbu.edu.hk), May 08 2008

Status

approved