cp's OEIS Frontend

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

%I A320731 #11 Nov 16 2024 17:30:28
%S A320731 1,3,9,24,60,141,328,738,1647,3618,7893,17055,36619,78144,165888,
%T A320731 350619,738012,1548279,3237611,6752439,14046525,29157612,60396996,
%U A320731 124885167
%N A320731 Number of possible states when placing n tokens of 2 alternating types on 3 piles.
%C A320731 Piles start empty and have no height limit. A token can only be placed on top of a pile. The starting token is fixed.
%e A320731 With alternating symbols A and B on three piles (starting with A), the following states emerge after placing 3 symbols in all 3^3 possible ways:
%e A320731    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15
%e A320731   A                                                                 A
%e A320731   B    B    B    A     A        A           A  A     A         B    B    B
%e A320731   A__  AA_  A_A  AB_  AB_  ABA  A_B  AAB  A_B  BA_  BA_  BAA  AA_  _A_  _AA
%e A320731    16   17   18   19   20   21   22   23   24   25   26   27
%e A320731                                                            A
%e A320731         A     A  A           A        A     A    B    B    B
%e A320731   AAB  _AB  _AB  B_A  BAA  B_A  ABA  _BA  _BA  A_A  _AA  __A
%e A320731 3 pairs of states (numbered (6,22), (8,16) and (12,20)) are identical, all others are different, hence a(3)=24.
%o A320731 (Python)
%o A320731 def fill(patterns, state_in, ply_nr, n_plies, n_players, n_stacks):
%o A320731     if ply_nr>=n_plies:
%o A320731         patterns.add(tuple(state_in))
%o A320731     else:
%o A320731         symbol=chr(ord('A')+ply_nr%n_players)
%o A320731         for st in range(n_stacks):
%o A320731             state_out=list(state_in)
%o A320731             state_out[st]+=symbol
%o A320731             fill(patterns, state_out, ply_nr+1, n_plies, n_players, n_stacks)
%o A320731 def A320731(n):
%o A320731     n_plies, n_players, n_stacks = n, 2, 3
%o A320731     patterns=set()
%o A320731     state=[""]*n_stacks
%o A320731     fill(patterns, state, 0, n_plies, n_players, n_stacks)
%o A320731     return len(patterns)
%Y A320731 For 2 token types on 2 piles, see A320452.
%K A320731 nonn,more
%O A320731 0,2
%A A320731 _Bert Dobbelaere_, Oct 20 2018