A007075 - OEIS

%I M1441 #33 Dec 20 2017 04:12:10

%S 1,2,5,13,35,95,260,714,1965,5415,14934,41206,113730,313958,866801,

%T 2393315,6608473,18248017,50389350,139144906,384237186,1061044865,

%U 2930013158,8091077148,22343115337,61699480866,170380367189,470497972866

%N Number of irreducible positions of size n in Montreal solitaire.

%C 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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H David Bevan, <a href="/A007075/b007075.txt">Table of n, a(n) for n = 1..1000</a>

%H C. Cannings, J. Haigh, <a href="https://doi.org/10.1016/0097-3165(92)90037-U">Montreal solitaire</a>, J. Combin. Theory Ser. A 60 (1992), no. 1, 50-66.

%F a(n) = d(n, 1) where d(n, k) is defined in A007046. - _Sean A. Irvine_, Oct 06 2017

%F 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

%e a(3) = 5; five indecomposable permutations have three inversions: 321, 2341, 2413, 3142, 4123. - _David Bevan_, Dec 19 2017

%t 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 *)

%Y Cf. A007046, A007048, A007049, A007050, A007076.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, _Mira Bernstein_

%E More terms from _Sean A. Irvine_, Oct 06 2017