|
|
A007075
|
|
Number of irreducible positions of size n in Montreal solitaire.
(Formerly M1441)
|
|
6
|
|
|
1, 2, 5, 13, 35, 95, 260, 714, 1965, 5415, 14934, 41206, 113730, 313958, 866801, 2393315, 6608473, 18248017, 50389350, 139144906, 384237186, 1061044865, 2930013158, 8091077148, 22343115337, 61699480866, 170380367189, 470497972866
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
a(n) is also the number of indecomposable permutations with exactly n inversions; there is one indecomposable permutation with no inversions. - David Bevan, Dec 19 2017
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
C. Cannings, J. Haigh, Montreal solitaire, J. Combin. Theory Ser. A 60 (1992), no. 1, 50-66.
|
|
FORMULA
|
The ordinary generating function is f(1), where f(v) satisfies the functional equation f(v) = v*(1 + f(1 + x*v) - f(1)). The variable x marks inversions and v marks left-to-right minima. - David Bevan, Dec 19 2017
|
|
EXAMPLE
|
a(3) = 5; five indecomposable permutations have three inversions: 321, 2341, 2413, 3142, 4123. - David Bevan, Dec 19 2017
|
|
MATHEMATICA
|
r[1, 1]=1; r[_, 0]:=0; r[n_, k_]:=r[n, k]=Sum[r[n-k, j]Binomial[j+1, k], {j, k-1, (Sqrt[8(n-k)+1]-1)/2}]; a[n_]:=Sum[r[n, k], {k, (Sqrt[8n+1]-1)/2}]; Array[a, 20] (* David Bevan, Dec 19 2017 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|