The adsorption at the air-water interface from mixed solutions of a non-surface-active anionic polyelectrolyte (polyacrylamide sulfonate, PAMPS) and a cationic surfactant (cetyltrimethylammonium bromide, CTAB) is investigated using various physicochemical methods: surface tensiometry, X-ray reflectivity, excited electrocapillary waves, compression isotherms, and Brewster angle microscopy (BAM). As in an earlier study on a polyacrylamide with a smaller degree of sulfonation, several features were observed: synergistic lowering of surface tension at very low surfactant concentrations due to the formation of polyelectrolyte-surfactant complexes at the air-water interface, monolayer thickness increase with increasing surfactant concentration, irreversible character of the adsorption and first-order phase transitions seen upon compression, followed by reversible multilayer formation. The layers formed by the polymer with higher charge density are thicker but less dense, and the inhomogeneities created upon compression lead to more spectacular patterns.