cp's OEIS Frontend

A320452 Number of possible states when placing n tokens of 2 alternating types on 2 piles.

%I A320452 #27 Apr 09 2025 15:13:37
%S A320452 1,2,4,8,15,28,52,96,177,326,600,1104,2030,3732,6858,12600,23144,
%T A320452 42504,78048,143296,263068,482904,886392,1626912,2985943,5480012,
%U A320452 10056946,18456056,33868851,62151788,114050884,209284710,384034660,704690938,1293071688,2372700708
%N A320452 Number of possible states when placing n tokens of 2 alternating types on 2 piles.
%C A320452 Piles start empty and have no height limit. A token can only be placed on top of a pile. The starting token is fixed.
%C A320452 Up to a(11) the terms are matching A008937(n+1).
%H A320452 Martin Fuller, <a href="/A320452/b320452.txt">Table of n, a(n) for n = 0..40</a>
%e A320452 With alternating symbols A and B on two piles (starting with A), the following states emerge after placing 4 symbols in all 2^4 possible ways:
%e A320452   B                                                            B
%e A320452   A   A   B       B            B  B            B       B   A   A
%e A320452   B   B   B   BB  A   AB  BA   A  A   AB  BA   A  BB   B   B   B
%e A320452   A_  AB  AA  AA  AB  AB  AB  AB  BA  BA  BA  BA  AA  AA  BA  _A
%e A320452 All states are different, except the 13th state is a duplicate of the 4th.
%e A320452 Hence a(4)=15.
%o A320452 (Python)
%o A320452 def fill(patterns, state_in, ply_nr, n_plies, n_players, n_stacks):
%o A320452     if ply_nr>=n_plies:
%o A320452         patterns.add(tuple(state_in))
%o A320452     else:
%o A320452         symbol=chr(ord('A')+ply_nr%n_players)
%o A320452         for st in range(n_stacks):
%o A320452             state_out=list(state_in)
%o A320452             state_out[st]+=symbol
%o A320452             fill(patterns, state_out, ply_nr+1, n_plies, n_players, n_stacks)
%o A320452 def A320452(n):
%o A320452     n_plies, n_players, n_stacks = n, 2, 2
%o A320452     patterns=set()
%o A320452     state=[""]*n_stacks
%o A320452     fill(patterns, state, 0, n_plies, n_players, n_stacks)
%o A320452     return len(patterns)
%Y A320452 For 2 token types on 3 piles, see A320731.
%K A320452 nonn
%O A320452 0,2
%A A320452 _Bert Dobbelaere_, Oct 20 2018
%E A320452 a(33) onwards from _Martin Fuller_, Apr 09 2025