Do we have any formula for counting the number of graphs with $n$ vertices, that has exactly $k$ vertices with degree $d$ and the other vertices have different and disjoint degrees?
(Different and disjoint are the same, $d_1$ is different or disjoint rather than $d_2$, iff $d_1\neq d_2$.)
For example, for $n=3, k=2, d=1$, we only have one graph($P_3$) with this property.
Also, for $n=4, k=2, d=2$, we have the only graph with degree sequence $1, 2, 2, 3$.
Best Answer
The two examples you mention have a very nice generalization but the general counting problem seems hopeless. Let me start with the nice result. It is a fun (and easy) exercise to show that in any simple graph there are at least two vertices with the same degree. Define a $g(n,k,d)$ to be a simple unlabeled graph with $n$ vertices and $n-k+1$ distinct degrees, The degree $d$ taken by exactly $k$ vertices and some other $n-k$ degrees taken once each. Also, let $N(n,k,d)$ be the number of $g(n,k,d)$.
You make two interesting remarks. That $N(4,2,2)=1$ the graph having degrees $1,2,2,3$ (this is true) and that $N(3,2,1)=1$ because of the path $P_3.$ However this number is actually $2$ because the complement (an edge and an isolated vertex) is another example.
It turns out that for each $n \ge 2$ there are exactly two $g(n,2,d)$ : a connected one with $d=\lceil (n-1)/2 \rceil$ and the complement which is not connected and has $d=\lfloor (n-1)/2 \rfloor.$
I'm sure that this is well known but didn't find it in a short bit of looking around. The ingredients of an induction proof are the following operations:
This leaves a few steps to fill in.
Mathscinet gives little information about On graphs having exact two vertices with the same degree. Nor about On graphs having exact three vertices with the same degree.
At the other extreme, the case $k=n$ of graphs regular of degree $d$ is reasonable but not trivial for $d=2.$ (In that it is the number of partitions of a certain type so at least has a name.) For larger $d$ it would be hopeless to get exact numbers for large $n$ . And the general case seems equally difficult. In a few isolated cases an answer might be fairly easy such as $k=n-2$ vertices of degree $1$ (or maybe $n-m$ for small $m$.)